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

前言

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

正文

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

解释几个重点的变量

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));
}

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

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

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

 @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