Java 8 HashMap 详解

Myth丶恋晨 2024-04-17 17:24 70阅读 0赞

#### 文章目录 ####

*  1. HashMap 存储结构
 *   *   *  1.1 HashMap 底层结构
         *  1.2 HashMap 为什么采用数组 + 链表
         *   *   *  Reference: 解决hash冲突的四种方法：
         *  1.2 HashMap 数组结构可否被替代
         *  1.3 HashMap 为何不直接使用红黑树
         *  1.4 HashMap 红黑树什么时候退化为链表
 *  2. HashMap 存取过程
 *   *   *  2.1 HashMap put()方法
         *  2.2 HashMap get()方法
 *  3. HashMap 容量相关
 *   *   *  3.1 HashMap 初始化容量
         *  3.2 HashMap 扩容为什么是2的次幂
         *  3.3 HashMap 扩容机制
 *  4. HashMap 使用指南
 *   *   *  4.1 使用不可变类作为HashMap的Key
         *  4.2 实现自定义类作为HashMap的Key
         *   *  4.2.1 重写 hashcode 和 equals 方法
             *  4.2.2 如何设计一个不变类

## 1. HashMap 存储结构 ##

#### 1.1 HashMap 底层结构 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]  
JDK 1.8 的 HashMap 底层数据结构与 JDK1.7 时大致相同，主要为 数组+链表。它采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。但在1.8 版本中如果链表元素数量达到 8 ， 就会尝试进行树化操作（如果数组长度小于 64， 则进行扩容操作，而不是树化操作），将链表转化为 红黑树结构。故 HashMap 数据结构可作如下总结：

>  *  **JDK 1.7**：  数组+链表
>  *  **JDK 1.8**： 数组+链表+红黑树

static final int MIN_TREEIFY_CAPACITY = 64;
    
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize(); // 如果数组长度小于 64， 则进行扩容操作，而不是树化操作
            else if ((e = tab[index = (n - 1) & hash]) != null) {
        
                TreeNode<K,V> hd = null, tl = null;
                do {
        
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
        
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

#### 1.2 HashMap 为什么采用数组 + 链表 ####

>  *  数组结构简单，利用元素 key的hash值对数组长度取模可以快速定位到数组下标 index，效率极高
>  *  链表是用来解决hash冲突问题，当出现 hashCode 值一样的情形，就在数组相应下标位置形成一条链表。这是解决hash冲突的**链地址法**

###### Reference: 解决hash冲突的四种方法： ######

>  *  **链地址法**  
>     基本思想是将所有哈希地址为 i 的元素构成一个单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在链表中进行。链地址法适用于经常进行插入和删除情况。
>  *  **开放定址法**  
>     也称再散列法，基本思想是当关键字key的哈希地址p=H（key）出现冲突时，以p为基础产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
>  *  **再哈希法**  
>     同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key），直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
>  *  **公共溢出区域法**  
>     将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

#### 1.2 HashMap 数组结构可否被替代 ####

能否用LinkedList 代替

>  *  答案是可以，但是用数组效率最高。 在HashMap中定位数组下标利用元素的key的哈希值对数组长度取模就可以，显然数组的查找效率比LinkedList高。

ArrayList底层是数组查找也快，能否用ArrayList

>  *  采用基本数组结构扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。而ArrayList的扩容机制是1.5倍扩容，默认容量为10，不利于高效定位。

private void grow(int minCapacity) {
        
         // overflow-conscious code
         int oldCapacity = elementData.length;
         int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容，默认为10
         ......
     }

#### 1.3 HashMap 为何不直接使用红黑树 ####

> 1.  当元素小于8个时，做查询操作链表结构已经能保证查询性能。
> 2.  当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，这些都是性能损耗。

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑是浪费性能。

#### 1.4 HashMap 红黑树什么时候退化为链表 ####

从源码看，节点数量为6的时候退转为链表,中间有个差值7可以防止链表和树之间频繁的转换。如果设计成链表个数超过8则链表转换成树结构，小于8则树结构转换成链表，如果一个HashMap不停插入删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率很低。

static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        
               ......
                if (loHead != null) {
        
                    if (lc <= UNTREEIFY_THRESHOLD)
                        tab[index] = loHead.untreeify(map); // 解除树化
                 ......
            }

## 2. HashMap 存取过程 ##

#### 2.1 HashMap put()方法 ####

存储元素的过程如下：

1.  对key 做hash() 运算，获取其hashCode 值, 可看到有对 key==null 返回 0 的处理，这就是HashMap允许 null 键的原因。 另外 `hash()` 中 将 hashCode 与 hashCode 无符号右移16位的值进行异或处理，是出于减少哈希冲突的目的，因为这个操作把原 hashCode 中没有使用到的高位数据也利用起来参与到运算中了。
    
    > Hash函数是指把一个大范围映射到一个小范围，目的是节省空间，使得数据容易保存。比较出名的有MurmurHash、MD4、MD5等等。
    
        static final int hash(Object key) {
              
             int h;
             // 此处 h与其低16位 异或 操作，目的是减少index定位时的 hash碰撞
             return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
         }
2.  懒加载策略，如果当前 Entry\[\] 数组尚未初始化，则调用 resize（）方法初始化。
3.  使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组 index，如果该位置上没有元素则插入。
4.  如果碰撞了，【1】首先通过 equals（）比较 key，如相同则使用新的 value 覆盖旧 value，从此可知 HashMap 只允许一个Key为null的键值对；【2】不符合前一条则首先判断碰撞的元素是否是树节点，即该位置链表是否已经转化成红黑树，如是则将新元素转化为 树节点插入；【3】不符合前两条，遍历该数组下标的链表，将新元素添加到链表尾部后判断链表长度是否达到 8，达到 8 则将链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作，遍历过程中若发现 key 已经存在直接覆盖 value 即可。
5.  插入成功后，判断数组实际存在的键值对数量size是否超过了最大容量threshold，如果超过则进行扩容。

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

#### 2.2 HashMap get()方法 ####

获取value的过程也很简单：

1.  对key 做hash() 运算,获取用于定位数组下标的值。
2.  使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组下标index，取该位置上第一个节点 first，如其直接命中则直接返回。
3.  如果有冲突，则通过key.equals(k)去查找对应的Entry：若为树，则在树中通过key.equals(k)查找，O(logn)；如果是链表，则在链表中通过key.equals(k)查找，O(n)。

public V get(Object key) {
        
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
    final Node<K,V> getNode(int hash, Object key) {
        
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
        
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
        
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
        
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

## 3. HashMap 容量相关 ##

#### 3.1 HashMap 初始化容量 ####

HashMap默认容量为 16，最大容量为 1<<30 。扩容负载因子为 0.75，也就是默认容量下数组中实际存储的元素数量达到 16 \* 0.75 = 12，就会触发扩容。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

一般建议使用 HashMap 的时候指定初始容量大小，因为随着元素的不断增加，如果实际容量与初始容量相差太大，HashMap会发生多次扩容，而其扩容机制决定了每次扩容都需要重建hash表，非常影响性能。

另外即便通过 HashMap(int initialCapacity) 设置初始容量的时候，HashMap也不一定会直接采用传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。 从以下代码看，经过无符号右移和按位或运算, HashMap的容量最终会被设置成 大于传入参数的最小的2的次幂（7–>8, 10–>16）。

static final int tableSizeFor(int cap) {
        
            int n = cap - 1; // 参数值 -1 是为了处理传入参数值恰好是 2 的次幂的情况
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

#### 3.2 HashMap 扩容为什么是2的次幂 ####

HashMap为了存取高效就要尽量减少碰撞，也就是尽量把数据分配均匀，每个index下标上的链表(也可能是红黑树)长度需要大致相同, 这个算法实际就是取模，hash%length。

但是取模运算不如位移运算快。因此源码中优化为 hash()&(length-1),也就是hash%length 等价于 hash()&(length-1).

之所以取数组长度为 2 的n 次方,是因为2的n次方用二进制表示实际就是1后面n个0，而2的n次方-1，实际就是n个1。

*  例如长度为8时候，**3&(8-1)–>(11 & 111)=3, 2&(8-1)–>(10 & 111)=2** ，下标不同，不碰撞。
 *  而长度为5的时候，3&(5-1)=0, 2&(5-1)=0，都在0上，出现碰撞了。

所以，保证容积是2的n次方，是为了保证在做 hash&(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算, 尽量减少哈希冲突.

#### 3.3 HashMap 扩容机制 ####

HashMap 扩容为原来2倍，所以链表中节点的位置要么是在数组原位置，要么是在数组原位置再移动2次幂的数组位置，且链表元素的顺序不变。

*  JDK1.7中 HashMap旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置。1.8的优化解决了 1.7 版本 HashMap多线程扩容出现链表中两个节点 next 指针互相指向对方的 死循环（HashMap Infinite Loop）问题。

以下代码中已经添加了注释，JDK1.8中HashMap 不需要像JDK1.7的实现那样重新计算hash值，而是复用原 hash 值，将其与原容量进行与操作，进而确定其数组下标是否需要改变。

*  例如原容量 oldCap = 16，二进制表示为： 00001 0000  
    则 key1=0001 1001, key2 = 0000 1001, 扩容前两个 key&(oldCap-1) 都在下标 9 位置  
    扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]

final Node<K,V>[] resize() {
        
          Node<K,V>[] oldTab = table;
          int oldCap = (oldTab == null) ? 0 : oldTab.length;
          int oldThr = threshold;
          int newCap, newThr = 0;
          if (oldCap > 0) {
        
              // 超过最大值就不再扩充
              if (oldCap >= MAXIMUM_CAPACITY) {
        
                  threshold = Integer.MAX_VALUE;
                 return oldTab;
             }
             // 没超过最大值，扩充为原来的2倍
             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                      oldCap >= DEFAULT_INITIAL_CAPACITY)
                 newThr = oldThr << 1; // double threshold
         }
        ......
         threshold = newThr;
         @SuppressWarnings({
        "rawtypes"，"unchecked"})
             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
         table = newTab;
         if (oldTab != null) {
        
             // 把每个bucket都移动到新的buckets中
             for (int j = 0; j < oldCap; ++j) {
        
                 Node<K,V> e;
                 if ((e = oldTab[j]) != null) {
        
                    ......
                     else {
         // 重点，重新处理链表节点位置代码块
                         Node<K,V> loHead = null, loTail = null;
                         Node<K,V> hiHead = null, hiTail = null;
                         Node<K,V> next;
                         do {
        
                             next = e.next;
                             // 复用原 hash 值与 原容量与操作，若原容量为oldCap = 16 = 00001 0000
                               // 则 key1=0001 1001, key2 = 0000 1001, 扩容前两个[key&(oldCap-1)]都
                               // 在下标 9 位置
                               // 扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变
                             if ((e.hash & oldCap) == 0) {
        
                                 if (loTail == null)
                                     loHead = e;
                                 else
                                     loTail.next = e;
                                 loTail = e;
                             }
                             // 其他则需移动位置
                             else {
        
                                 if (hiTail == null)
                                     hiHead = e;
                                 else
                                     hiTail.next = e;
                                 hiTail = e;
                             }
                         } while ((e = next) != null);
                         // 放到new bucket里 位置与原索引相同
                         if (loTail != null) {
        
                             loTail.next = null;
                             newTab[j] = loHead;
                         }
                         // 放到new bucket里，下标位置为 原索引 + oldCap 
                         if (hiTail != null) {
        
                             hiTail.next = null;
                             newTab[j + oldCap] = hiHead;
                         }
                     }
                 }
             }
         }
         return newTab;
     }

## 4. HashMap 使用指南 ##

#### 4.1 使用不可变类作为HashMap的Key ####

一般用Integer、String这种不可变类当HashMap当key，最常用String。

1.  因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。
2.  HashMap 存取值的时候要用到 equals()和 hashCode()方法，键对象正确地重写这两个方法是非常重要的，通常不可变类已经很规范的覆写了hashCode()以及equals()方法。

**使用可变类（如List）作为 HashMap 的key 的问题**

*  例如把List 作为键，那么当这个 List 对象添加删除元素的时候 hashcode可能发生改变， 这样可能会导致其在HashMap中数组 index下标定位不准，也就无法取出存储的value。

#### 4.2 实现自定义类作为HashMap的Key ####

主要涉及两个关键点：

*  **重写 hashcode 和 equals 方法**
 *  **设计一个不变类**

##### 4.2.1 重写 hashcode 和 equals 方法 #####

需要遵守以下四个原则：

1.  两个对象相等，hashcode一定相等
2.  两个对象不等，hashcode不一定不等
3.  hashcode相等，两个对象不一定相等
4.  hashcode不等，两个对象一定不等

##### 4.2.2 如何设计一个不变类 #####

1.  类添加final修饰符，保证类不被继承  
    如果类可被继承就会破坏类的不可变性机制，只要子类覆盖父类的方法（如equals 和 hashCode）并且子类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。
2.  所有成员变量必须私有，并且加上final修饰  
    通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为对象成员变量有可能在外部改变其值，所以第5点弥补这个不足。
3.  不提供改变成员变量的方法，包括setter  
    避免通过其他接口改变成员变量的值，破坏不可变特性。
4.  在getter方法中，不要直接返回对象本身，而是克隆对象并返回对象的拷贝  
    这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。
5.  通过构造器初始化所有成员，进行深拷贝(deep copy)  
    如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改达到改变内部变量的效果。例如：

public final class Table {
          
        private final int[] myArray;  
        public Table (int[] array) {
          
            this.myArray = array; // myArray和array指向同一块内存地址
                               //修改传入的array对象的值可改变myArray内部的值
        }  
    }

为了保证内部的值不被修改，可采用深度copy来创建一个新内存保存传入的值。正确做法：

public final class Table {
          
        private final int[] myArray;  
        public Table (int[] array) {
          
            this.myArray = array.clone();   
        }   
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/3b6b9e5fa5ff40b0af91520aacbe1bd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/adc8a64212614301ad96ce6ff96af36f.png