【Java】HashMap原理及相关面试题

作者: littlefogcat | 来源:发表于2021-02-05 14:03 被阅读0次

HashMap与Hashtable两个类都是通过Key-Value对存储的数据结构。
根据官方的说法，二者唯二的区别是HashMap线程不安全而Hashtable线程安全，并且HashMap允许null值而Hashtable不允许。
Hashtable实现线程安全的方式是使用synchronized修饰方法，所以二者基本一致。由于Hashtable效率较低，所以Java官方不建议使用这个类了；单线程的情况下使用HashMap，多线程的时候使用ConcurrentHashMap。

一、数据结构

1. 结构

HashMap的本质是一系列的Key-Value对的集合，一个Key-Value对称为一个Entry。

HashMap的基本数据结构是数组。数组中的每个非空元素（被称为桶/箱）都存放了一个链表或者一棵红黑树（准确来说是它们的头节点，同时这也是一个Entry）。

一个节点放置在哪个格子里，是这么决定的：首先计算出这个节点key的哈希值h；h对数组长度取模，即是这个节点所在链表（或树）在数组对应的序号。

HashMap结构示意图

2. 扩容

数组长度初始值为16。当数组中大部分（默认是3/4）的格子中都存放了元素，说明此时哈希碰撞的几率较高了，那么就会进行扩容；每次扩容后的长度是旧长度的2倍，扩容后的长度必然是2的幂。

为什么长度要设计成2的幂？因为在哈希查找的过程中，需要对数组长度进行求模运算；而对于一个2的幂数的模数n，对其的求模运算%n可以转换为位运算&(n-1)，这样可以大大提高运算效率。

3. 链表和红黑树的转换

数组中的元素初始以链表的形式保存。
当链表的长度达到阈值（默认为8），这个链表就会转换为红黑树。
当红黑树的size低于阈值（默认为6），则会重新退化为链表。

二、增删改查

1. 增/改

HashMap通过put方法添加/修改元素。put最终会调用putVal方法：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

梳理一下往HashMap中放入K-V对的流程：

计算出key的哈希值hash并以数组长度为模求余，得到该K-V对应节点在数组中的存放位置；
如果这个格子里面没有元素，那么放入以该K-V对创建的节点作为链表的头节点；放入之后数组占用率如果达到了扩容的阈值，那么就进行扩容；
如果这个格子中已经有元素了（检测到哈希碰撞）：遍历这个链表或者红黑树，如果找到了key的哈希值与hash相等的节点，那么就直接更新这个节点的value（此处为修改元素）；否则就将这个新节点插入到链表或者红黑树中，其中链表插入到尾部，红黑树插入到适当的位置并进行重平衡。

2. 删

删除的过程比较简单，首先计算出待删除key的哈希值hash并以数组长度为模求余，找到对应的链表/红黑树，遍历其节点；如果找到哈希值等于hash的节点，那么就删除这个节点，删除方式与链表/红黑树删除节点相同。

3. 查

计算出待查找key的哈希值，并对数组长度取模，找到对应链表或红黑树；遍历链表或搜索红黑树找到节点并返回。

4. 注意

这里对key求哈希值，并不是直接调用key.hashCode()，而是通过HashMap的hash(key)来计算的。
hash方法如下：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这样比起直接调用hashCode()能增强随机性，减少哈希碰撞的发生。
例如，对于浮点数，如果直接调用hashCode()会造成，一个浮点数x与2x、4x……2^n*x的哈希值末22位都相同，这样显然是不愿意看到的。所以HashMap使用了这个机制来保证更高的随机性。

以下代码输出都相同：
System.out.println(new Float(1.2f).hashCode() & 0x3FFFFF);
System.out.println(new Float(2.4f).hashCode() & 0x3FFFFF);
System.out.println(new Float(4.8f).hashCode() & 0x3FFFFF);
System.out.println(new Float(9.6f).hashCode() & 0x3FFFFF);

三、相关面试题

1. HashMap的特点？结构？插入过程是什么？

HashMap的特点是使用Key-Value对存储数据，无序，增删改查很快，平均时间复杂度均为O(1)。

结构是数组+链表/红黑树，数组中的每个元素保存了链表/红黑树的头节点。

插入流程：

计算出key的哈希值hash并以数组长度为模求余，得到该K-V对应节点在数组中的存放位置；
如果这个格子里面没有元素，那么放入以该K-V对创建的节点作为链表的头节点；放入之后数组占用率如果达到了扩容的阈值，那么就进行扩容；
如果这个格子中已经有元素了（检测到哈希碰撞）：遍历这个链表或者红黑树，如果找到了key的哈希值与hash相等的节点，那么就直接更新这个节点的value；否则就将这个新节点插入到链表或者红黑树中，其中链表插入到尾部，红黑树插入到适当的位置并进行重平衡。

2. HashMap与Hashtable的区别是什么？

HashMap线程不安全，Hashtable线程安全。原因是Hashtable的方法都用synchronized修饰了。
HashMap允许null值而Hashtable不允许。
HashMap继承自AbstractMap，Hashtable继承自Dictionary。

3. HashMap的扩容（resize）机制讲一下？

在没有特殊设置的情况下，HashMap内部数组table的初始长度为16。当table中超过3/4（即负载因子，默认值为0.75即3/4，可以修改）的元素已经存放了节点，这时表明再添加元素就比较容易产生哈希碰撞了，这个时候table数组就需要扩容，通过resize()方法。
新的table数组为大于原数组长度的最小的2的幂数。由于table数组长度必然是2的幂，所以新数组的长度是原数组长度的2倍。

以上为简单回答，以下为加餐：

扩容之后，节点的位置需要重新排布，放到正确的位置组成新的链表/红黑树，那么这些节点应该放在什么地方呢？
这里使用i表示这个节点在原数组中的序号，newI表示节点在新数组中的序号。
从原理上来说，假设旧的数组长度为oldCap，新的数组长度为newCap且为旧长度的2倍。那么对于一个Entrye来说，其在新数组中的坐标newI = e.hash % newCap。一般情况下，问题本应该就此解决了，但是由于求模运算的效率不高，为了避免取模运算，Java采用了一种精妙的方式……
由求模运算的原理可以知道，i和newI二者之间的关系是：newI == newI < oldCap ? i : i + oldCap；
所以，newI = e.hash % newCap等价于：

if(e.hash % newCap < oldCap) {
    newI = i;
} else {
    newI = i + oldCap;
}

以旧长8，新长16为例。
假设两个节点e1和e2，哈希值分别为17和25。因为对8的余数都是1，所以它们被保存在了旧数组坐标为1的元素中。当数组扩容到16时，二者对16的余数变成了1和9，所以二者在新数组中的坐标变成了1和9，相当于e1留在原地，e2往右移动了8位。

而由于oldCap和newCap是2的幂数，所以e.hash % newCap又等价于e.hash & (newCap - 1)。到了这里，就把效率低的求模运算替换为了效率极高的位运算：

if((e.hash & (newCap - 1)) < oldCap) {
    newI = i;
} else {
    newI = i + oldCap;
}

又由于newCap是oldCap的2倍，也即是oldCap左移一位，e.hash & (newCap - 1)表示了e.hash末尾n位的值，其中n为oldCap的二进制位数。
又由于oldCap是二进制长度为n的最小数，如果e.hash二进制倒数第n位是1的话，那么它必然大于等于oldCap；故而(e.hash & (newCap - 1)) < oldCap等价于：e.hash二进制倒数第n位为0。而e.hash的倒数第n位为0，又等价于e.hash & oldCap == 0，所以上面的代码等价于：

if((e.hash & oldCap) == 0) {
    newI = i;
} else {
    newI = i + oldCap;
}

这就是Java源码中的算法。
总结来说一句话，如果节点哈希值对新数组长度求模小于旧数组长度的话，那么节点就在原地不动；否则，节点往右移动旧数组长度位。

杠精面试官：为什么负载因子是0.75而不是0.7、0.8？为什么扩容是2倍而不是1.5、2.5？

答：0.75是随手瞎jb设的，扩容2倍为了方便求模转换为位运算，如果数组长度不是2的幂，e.hash & oldCap这一步就不成立了。

4. 哈希值相同的两个对象equals一定返回true吗？反之呢？

Object类的 hashCode 是一个 native 方法。其包含三个约定：

在一次程序执行期间，如果一个对象 equals 中所比较的信息没有改变，那么 hashCode 必须返回相同值；

如果两个对象 equals 返回 true，那么 hashCode 必须相等；

如果两个对象 equals 返回 false，那么 hashCode 不需要不相等；但是为了提高 HashMap 的效率，最好不要让不同对象返回相同哈希值。

对于Object的默认实现来说，哈希值相同的两个对象，equals不一定返回true，这表明产生了哈希碰撞；equals返回true的两个对象，哈希值一定相等。
对于自行实现了equals或hashCode方法的类，以实现方法为准。比如我非要把equals方法重写为return o != null && hashCode() == o.hashCode()，虽然这违反了推荐的规范，但是是可行的。

5. 为什么Java8引入了红黑树？它的优缺点是什么？

哈希碰撞是无可避免的。当最坏情况发生时，大量的节点累计在一个桶——即数组中的同一项——内。这时，HashMap的增删改查效率退化到O(n)，n为链表的长度。
在链表的长度达到8时，链表会转换为红黑树。红黑树的优势为查找效率为O(logn)，在冲突数据量大时效率优于链表。劣势为在建树和拆分的时候需要额外的时间、操作小步骤多、占用内存空间大，所以只有在链表长度长到足以抵消红黑树的劣势时，才进行转换。
当数组长度小于64时，即使链表长度达到8，HashMap也会优先考虑扩容而不是转红黑树。

事实上，根据概率论，在正常情况下，如果哈希值分布比较均匀，几乎不可能出现链表转为红黑树的情况。红黑树只是为了针对由于失误或者故意等情况造成的哈希分布不均，比如类的hashCode()方法直接返回常数。

6. HashMap线程安全吗？为什么？如何解决？

HashMap线程不安全。
原因和其他线程不安全相同，多线程操作会导致读写数据异常。
使用ConcurrentHashMap代替，或使用Collections.synchronizedMap(hashMap)包装类，或者操作时加锁，或者使用Hashtable。

7. Java7和Java8中HashMap的不同点？

Java8中加入了红黑树；
Java7链表插入方式为头插法，Java8为尾插法。
扩容时，Java7对每个元素都重新放置，Java8只对e.hash & oldCap不为0的元素移动位置。