深入理解HashMap及面试相关问答

冷不防 2022-05-04 05:56 198阅读 0赞

## 前言 ##

HashMap是面试必备的一个知识点，无论你是初级中级还是高级，基本上逃不过这个问题，下面的内容很简单，只要你理解了其中的含义，这对你使用hashmap和面试都是很有帮助的。

## 正文 ##

首先打开HashMap，看看中都定义了哪些成员变量。

![paramInMap][]

解释几个重点的变量

transient int size：记录了Map中KV对的个数

loadFactor 装载因子，用来衡量HashMap满的程度。loadFactor的默认值为0.75f（static final float DEFAULT\_LOAD\_FACTOR = 0.75f;）

int threshold; 临界值，当实际KV个数超过threshold时，HashMap会将容量扩容，threshold＝容量（capacity）\*加载因子（loadFactor）

一个重要的概念，容器的容量，capacity：DEFAULT\_INITIAL\_CAPACITY= 1 << 4; // aka 16

### size 和 capacity ###

HashMap中的size和capacity之间的区别其实解释起来也挺简单的。我们知道，HashMap就像一个“桶”，那么capacity就是这个桶“当前”最多可以装多少元素，而size表示这个桶已经装了多少元素。当达到扩容条件的时候，就需要进行扩容了，会从16扩容成32，依次都是2的幂。如下代码

@Test
        public  void  test19() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
            Map<String, String> map = new HashMap<String, String>();
            map.put("key", "value");
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map));
    
            Field size = mapType.getDeclaredField("size");
            size.setAccessible(true);
            System.out.println("size : " + size.get(map));
    }

![70][]

我们定义了一个新的HashMap，并向其中put了一个元素，然后通过反射的方式打印capacity和size。**输出结果为：capacity : 16、size : 1 **

一个HashMap默认的容量（capacity）是16，原因是可以使用按位与替代取模来提升hash的效率。

**下面我来通过构造方法指定容量大小，大家在看一看这个“桶”的实际大小是多少。**

![70 1][]

@Test
        public  void  test19() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
            Map<String, String> map = new HashMap<String, String>(7);
            map.put("key", "value");
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
                    capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map));
    }

分别把7改成10 和63，然后运行

控制台分别输出capacity : 8、capacity : 16、capacity : 64。

我来解释一下为什么是这三个容量

**通过构造函数指定了一个数字作为容量，那么Hash会选择大于该数字的第一个2的幂作为容量**

**Map<String, String> map = new HashMap<String, String>(7);**

**就是最接近7以上还有谁是2的幂，肯定是8啊，2\*2\*2=8 ，假如是63就是capacity=64，因为64是63 下一个2次方的数。所以啊，如果各位同学想指定这个“桶”的大小时最好你就直接指定2的次方数，免得你还的算。**

### **下面讲HashMap扩容机制** ###

**首先就是时候扩容，扩容的条件是什么**

扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容。

**threshold（临界值） = loadFactor（装载因子默认值为0.75f） \* capacity（容量）。**

默认情况下，当其size大于12(16\*0.75)时就会触发扩容。

Map<String, String> map = new HashMap<String, String>(7,0.7f);

HashMap中还提供了一个支持传入initialCapacity,loadFactor两个参数的方法，来初始化容量和装载因子。不过，一般不建议修改loadFactor的值

### **下面给读者一些死记硬背的套话，面试基本上是这个问答套路** ###

1.Hashtable是线程安全的，它的每个方法中都加入了Synchronize方法

2.HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口

3.当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定

4.HashMap的get过程是先得到key的hash值，再把这个hash值与length-1按位与（取余），得到table数组的下标。取出这个下标值的key，与传入的key比较，如果相同那就是这个了。如果不同呢，那就沿着这个单向链表向后找，直到找到或找到结束也找不到。这里的length是有特点的，是2的n次方。

5.HashMap扩容机制是在put时，容量不够用的时候。因为每个元素都是一个单向链表，所以map里放的实际数量总是大于等于申请的空间。

6.HashMap可以接受null键值和值，而Hashtable则不能。

7.HashMap是非synchronized所以HashMap很快。

8.hashcode相同，所以两个对象是相等的，HashMap将会抛出异常，或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法，并告诉他们两个对象就算hashcode相同，但是它们可能并不相等。一些面试者可能就此放弃，而另外一些还能继续挺进，他们回答“因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理，虽然有很多种处理碰撞的方法，这种方法是最简单的，也正是HashMap的处理方法  
9.当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置  
。

10.当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？

任何一个小小的知识点都可以无限延伸，都可以追溯到硬件、计算机底层原理。

大多数问题都在这，有些面试官非要问到你不会为止，一直追问到底，最后都问到硬件了，你就说不会吧，给他点面子，万一答上来他会很没面子。

注：对本文有异议或不明白的地方微信探讨，wx：15524579896

[paramInMap]: /images/20220504/5633b561e17346d787ec5bdaa26e2a00.png
[70]: /images/20220504/289b8785b8494afdb16c368c5c79a7bb.png
[70 1]: /images/20220504/90d934546d3d4cf697b62676e6f8924a.png