Java Collections Framework - 深入HashMap

落日映苍穹つ 2022-06-15 05:45 159阅读 0赞

HashMap作为面试中被问道频率最高的问题，这篇文章就已面试的角度来说明HashMap的底层原理。

--------------------

# **HashMap原理** #

**HashMap的初始值都是Null的，储存的都是键值对（Entry）**

众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。  
![这里写图片描述][70]

**HashMap的Put方法**

调用 hashMap.put(“apple”, 0) ，插入一个Key为“apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）：我们先对Ke’y调用hashCode()方法

index = Hash（“apple”）

假定最后计算出的index是2，那么结果如下：  
![这里写图片描述][70 1]  
但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样：  
![这里写图片描述][70 2]  
这时候该怎么办呢？我们可以利用链表来解决。  
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可：需要注意的是，新来的Entry节点插入链表时，使用的是“头插法”。  
![这里写图片描述][70 3]

//HashMap中的put方法源码
     public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value); //null总是放在数组的第一个链表中
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            //遍历链表
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //如果key在链表中已存在，则替换为新value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(hash, key, value, i);
            return null;
     }

注意：如果Key值相同，那么对应的value值则会被替换成新的。如果key不同，则会插入到链中。

**HashMap的Get方法**  
使用Get方法根据Key来查找Value的时候，发生了什么呢？首先会把输入的Key做一次Hash映射，得到对应的index：

index = Hash（“apple”）

由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”：  
![这里写图片描述][70 4]  
第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。  
第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。  
之所以把Entry6放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

> 如果有冲突，则通过key.equals(k)去查找对应的entry  
> 若为树，则在树中通过key.equals(k)查找，O(logn)；  
> 若为链表，则在链表中通过key.equals(k)查找，O(n)

//HashMap get方法
     public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            //先定位到数组元素，再遍历该元素处的链表
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            return null;
    }

--------------------

# **HashMap Bucket大小问题** #

**HashMap 什么时候开辟bucket数组占用内存？HashMap 默认bucket数组多大？**  
第一次 put 时，而不是第一次new的时候。  
默认的bucket数组大小为16.

**如果new HashMap<>(19)，bucket数组多大？**  
答案是32，HashMap 的 bucket 数组大小一定是2的幂，如果 new 的时候指定了容量且不是2的幂，实际容量会是最接近(大于)指定容量的2的幂，比如 new HashMap<>(19)，比19大且最接近的2的幂是32，实际容量就是32。

**如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？**  
HashMap默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehash，因为它调用hash方法找到新的bucket位置。这时，需要创建一张新表，将原表的映射到新表中。

**为什么bucket数组的大小一定要是2的幂？**  
Bucket的初始大小设置成16以及每次手动或者自动扩展是都一定扩展成2的幂。  
这样主要时为了服务于Key映射到index的哈希算法。这样设计更符合Hash算法均匀分布的原则。

**什么是Rehash**  
当HashMap.Size >= HashMap的当前长度 \* HashMap负载因子时，HashMap就会进行Resize  
Resize要进行以下两个步骤

> 1.扩容  
> 创建一个新的Entry空数组，长度是原数组的2倍。  
> 2.ReHash  
> 遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

让我们回顾一下Hash公式：

index = HashCode（Key） & （Length - 1）

Resize前的HashMap：  
![这里写图片描述][70 5]  
Resize后的HashMap：  
![这里写图片描述][70 6]  
ReHash在多线程的时候可能会引发线程安全问题，可能会让链表出现了环形，出现死循环  
![这里写图片描述][70 7]

--------------------

# **Entry链的问题** #

**针对HashMap中某个Entry链太长，查找的时间复杂度可能达到O(n)，怎么优化？”**  
Entry\[\]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，HashMap里面设置一个因子，随着map的size越来越大，Entry\[\]会以一定的规则加长长度。目前在jdk1.8中，采用了新的红黑树的结构来实现，当链表的数量大于8的时，就会将冲突的节点保存在红黑树里。

void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
        //如果size超过threshold，则扩充table大小。再散列
        if (size++ >= threshold)
                resize(2 * table.length);
    }

--------------------

## **总结** ##

**HashMap的工作原理**  
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了就调用equlas方法比较Key，如果key相同就会覆盖掉以前的value，如果Key不相同对象将会储存在链表的头节点中。**也就是说数组中存储的是最后插入的元素**。 HashMap在每个链表节点中储存键值对对象。  
![这里写图片描述][SouthEast]

[70]: /images/20220615/93c0308d7d7542dab46efee378406029.png
[70 1]: /images/20220615/e2ed9519ab5c45edb57e511b430f0977.png
[70 2]: /images/20220615/32d72643b5e946a09720f8ace4bef465.png
[70 3]: /images/20220615/ea32706ab7264072bfa843fc5ea77495.png
[70 4]: /images/20220615/c01610951c004244a1d6ef9c056344c9.png
[70 5]: /images/20220615/001e50585bc14798a8d12bbb319f4c1d.png
[70 6]: /images/20220615/9d94c280df3b41849adf8f018b5a07a0.png
[70 7]: /images/20220615/9b304bc06e5a4a1a995650742d1e3dad.png
[SouthEast]: /images/20220615/581f44087e1041e4aa9a45c50a53b999.png