写点什么

【数据结构】Java 常用集合类 HashMap（JDK 1.8）

用户头像
Alex🐒
关注
发布于: 2020 年 07 月 21 日

整体设计

HashMap 实现了 Map 接口，存储 key-value 的散列表。与 HashTable 类似相似，区别是：

  1. 线程不安全；

  2. 允许键或值为 null；



HashMap 采用“数组+链表/红黑树”的结构存储，数组可以扩容，链表可以转化为红黑树。能提供常量时间性能的基本操作 get() 和 put()。迭代器遍历的效率与容量和存储KV数量有关。HashMap 不保证存入的KV的次序。

HashMap 属性

DEFAULT_INITIAL_CAPACITY    # 默认初始化容量（1<<4=16）
MAXIMUM_CAPACITY            # 最大的容量（1<<30=2^30）
DEFAULT_LOAD_FACTOR         # 默认的载入因子（0.75f）
TREEIFY_THRESHOLD           # 当桶上的结点数（链表长度）大于这个值时转红黑树（8）
UNTREEIFY_THRESHOLD         # 当桶上的结点数（红黑树大小）小于这个值时转为链表（6）
MIN_TREEIFY_CAPACITY        # 桶进行转换的时，Map的最小的容量（64），为了避免扩容和转换的冲突，至少是4*TREEIFY_THRESHOLD

初始容量大小和载入因子会影响 HashMap 的性能。初始容量指的是桶的数量。载入因子是来衡量 HashMap 在其容量增加之前允许达到的完整度。当 HashMap 中的 key 数量超过了载入因子和当前容量，HashMap 就会扩容（resize），新的 HashMap 桶的数量变为原来的两倍。



通常载入因子设置成 0.75，超过这个值会减少空间开销，但是会增加查询开销。设置初始容量的时候需要考虑 HashMap 将容纳的数量和载入因子，这样可以减少 resize 次数，从而减少性能损耗。



HashMap 在 JDK8 与 JDK7 实现上比较大的不同在于，当桶上结点的数量过大的时候，会将结构改变成树结构。树结构在数量过多的时候查找效率会得到提升。

HashMap 构造函数

transient Node<K,V>[] table;			// 存储数据的桶
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
public HashMap(int initialCapacity, float loadFactor) {
    // ... 检查 initialCapacity 和 loadFactor
    
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    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;
}



tableSizeFor(initialCapacity) 返回大于等于初始容量的的最小的二次幂数值，threshold 作为判断 resize 的阈值。



从构造函数可以看出，这时候并没有初始化桶（Node<K,V>[] table）。这里和 JDK7 的操作不同，JDK7 HashMap 构造方法中就初始化了哈希表。



另外一个重要的构造函数，用一个 Map 初始化 HashMap

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
// 将 m 的所有元素存入当前 HashMap 实例中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

哈希桶

HashMap 采用哈希表存储数据，使用拉链法（链地址法）解决哈希值冲突，即每个哈希值对应存储一个链表。Node<K,V> 对象就是链表的实现。

static class Node<K,V> implements Map.Entry<K,V> {
    // 键的哈希值，定位在 Node[] 中的位置
    final int hash;
    final K key;
    V value;
    // 桶是一个链表，表示当前结点所在链表的下一个结点
    Node<K,V> next;
}

HashMap get() 方法

首先计算出 key 的 hashCode，找到 table 中的数组索引，即 Node<K, V> 对象，如果存在，判断该结点是否等于要查询的节点，如果不是，按照链表或者红黑树的查询方式查找。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    // 判断 table 是否存在，hashCode 所在的索引是有为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 查询 key，先查询第一个，然后在查询 Node
        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;
}



(n - 1) & hash 得到哈希值对应 table 的索引。如果桶是由树组成，Node 是子类 TreeNode 实现的。

HashMap put() 方法

put 相比 get 更复杂，会涉及到 table 的 resize() 和 treeify()。首先判断 table 是否存在，不存在就创建。



判断 hashCode 对应位置是否有值，没有值就直接存入。如果存在就判断这第一个键是否相等，最后才根据 onlyIfAbsent（是否覆盖）来决定是否更新 value。如果第一个不相同，根据链表或者树的对应插入方法插入或更新（如果 key 存在，根据 onlyIfAbsent 判断）。



如果插入数据成功并且 Node 是链表，判断当前数量是否达到转换成树结构的阈值（TREEIFY_THRESHOLD），进行 treeify() 操作。最后再判断哈希表是否需要扩容。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 初始化 table
    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;
        
        // 先判断 Node 一个元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
          	// 第一个元素的 key 和当前元素相同
            e = p;
        else if (p instanceof TreeNode)
            // 使用 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) { 
          	// 如果 key 存在
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
          	// Callbacks to allow LinkedHashMap post-actions
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        // 哈希表进行扩容
        resize();
	  // Callbacks to allow LinkedHashMap post-actions
    afterNodeInsertion(evict);
    return null;
}



modCount 记录 HashMap 内部结构发生变化的次数，主要用于 fast-fail 机制。但是 key 值对应的 value 被更新不会计数 modCount。afterNodeAccess() 和 afterNodeInsertion() 方法，提供了后置处理接口，子类可以实现该方法。

treeify 转换

链表转换为树结构，当该链表的长度超过8时执行。（扩展：为什么Map桶中个数超过 8 才转为红黑树？）

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)
        // tab 容量小于 MIN_TREEIFY_CAPACITY 优先扩容 
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        
        // Node 转换 TreeNode
        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);
        
        // 把转换后的 TreeNode，替换原来位置上的 Node
        // 此时 TreeNode 还是双向链表的结构
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}



如果 table 大小小于 MIN_TREEIFY_CAPACITY（树结构化的最小限制），优先进行 resize 的效果更好，因为当 table 某个位置上集中了多个键值对，是因为这些 key 的 hashCode 和数组长度取模之后结果相同（并不是因为这些 key 的 hashCode 相同，hashCode 相同的概率比较低），所以可能是 table 数组的数量比较小造成的，可以通过扩容的方式，使得这些 key 分散到多个数组位置上。

treeify 方法

遍历双向链表，转换为红黑树结构。

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next; 
        x.left = x.right = null; 
        if (root == null) {   
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;  
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;   
                K pk = p.key;
                
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

resize 扩容

每次 resize，新的数组是原数组大小的两倍。resize 过程：

  1. 初始化过程，包括 oldTab（原表），oldCap（原表长度），newCap（新表长度）和 newThr（新表扩容阈值）。

  2. 根据计算出来的新表大小生成新表 newTab

  3. 如果 oldTab 不为空，遍历 oldTab 的每个桶，放入 newTab。

  4. 返回 newTab。

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;
        }
        // 扩容一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {              
        // 使用默认容量（16）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建新的表，并且覆盖 table
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍历 oldTable 的每个桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 如果桶中只有一个元素，直接放入 newTab
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 如果桶中是 TreeNode
                    // 将树的数据重新散列到 newTab 中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 如果桶中是链表 Node 
                    // 这里就看出了为什么要扩容为两倍
                    // 扩容两倍之后，数据在新桶中的位置只有两个 lo 和 hi
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        
                        // 新桶中位置不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                // 首先给链表头赋值
                                loHead = e;
                            else
                                loTail.next = e;
                            // 设置链表尾
                            loTail = e;
                        }
                        // 新桶中位置为 old + oldCap
                        else {
                            // 逻辑与上面相同
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 转换为两个新的链表（或一个），放入 newTab
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在扩容开始的时候，table 就被覆盖为 newTab（空的扩容后大小），<u>如果自此有 put 方法调用，会写入新的空的 table，不会写入 oldTab</u>。



为什么扩容两倍？

更加容易计算他们所在的新桶位置。如原桶长度是 4，现在桶长度是 8，那么：桶0中的元素会被分到桶0和桶4中，桶1中的元素会被分到桶1和桶5中，以此类推。



oldCap 假如是16（二进制为10000），扩容变成32（二进制为100000）。当 hashCode & 10000 ==0，那么 hashCode 的右起第五位肯定也是0，所以 hashCode & 100000 还是0，反之亦然。

与 JDK7 的区别

JDK7 种扩容的实现

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 创建一个新的 Entry 数组
    Entry[] newTable = new Entry[newCapacity];
    // 将数据转移到新的 Entry 数组里
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 覆盖 table 和 threshold
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 重点全在这个函数中
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 元素在新数组中的位置
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}



函数 transfer() 是链表重新散列方法，也是导致 HashMap 死锁问题的关键：

  1. 对原数组中的元素遍历，并计算出元素 e 在新数组中的位置 i

  2. e 放入新数组 i 对应链表 Entry 的头部，因为 Entry 可能有元素存在，所以先将 e.next 指向 Entry 第一个元素（如果 Entry 是空，则 e.next = null)，这时候 Entry 第一个元素是 e，newTable[i] 指向的是原 Entry 的第一个元素，所以设置 newTable[i] = e

  3. 循环2，直到链表节点全部转移

  4. 循环1，直到所有索引数组全部转移



在多线程场景下会出现同时 put 操作，并进入了 transfer。假设现在有三个线程：T1、T2， oldTable[i]=A，newTable[i]=B（B.next=C），A 在 newTable 的位置还是 i，当前 e 引用 A。 

1. 当T1运行到 e.next=newTable[i] 时，T2运行到 Entry<K,V> next = e.next。
2. T1运行 newTable[i]=e, e=next，会产生的结果：newTable[i]=A，A.next=B，B.next=C，e=B。
3. T2运行 e.next=newTable[i]，会产生的结果：B.next=A，同时 A.next=B，



JDK8 改进算法后不会再出现环状链表的情况，但并发时仍然不建议使用 HashMap。





划线
评论
复制
发布于: 2020 年 07 月 21 日阅读数: 55

版权声明: 本文为 InfoQ 作者【Alex🐒】的原创文章。

原文链接:【http://xie.infoq.cn/article/3e04311a649696993b3b8a051】。

本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。

Java源码数据结构
用户头像

Alex🐒

关注

还未添加个人签名 2020.04.30 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
【数据结构】Java 常用集合类 HashMap（JDK 1.8）