Java 常用集合类 HashMap(JDK1.8)

HashMap 整体设计(1.8)

HashMap 实现了 Map 接口,存储 key-value 的散列表。与 HashTable 类似相似,区别是:1.线程不安全;2.允许键或值为null。

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

HashMap 属性

DEFAULT_INITIAL_CAPACITY    默认初始化容量(2^4=16)
MAXIMUM_CAPACITY            最大的容量(2^30)
DEFAULT_LOAD_FACTOR         默认的载入因子(0.75f)
TREEIFY_THRESHOLD           当桶上的结点数大于这个值时转红黑树(8)
UNTREEIFY_THRESHOLD         当桶上的结点数小于这个值时转为链表(6)
MIN_TREEIFY_CAPACITY        最小的容量(64),并且为了避免扩容和转换树的冲突,至少是4*TREEIFY_THRESHOLD

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

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

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

HashMap 构造函数

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) 返回大于等于初始容量的的最小的二次幂数值,作为判断 resize 的阈值。

从构造函数可以看出,这时候并没有初始化哈希表(Node<K,V>[] table)。和JDK7的操作就不一样,其在构造方法中就初始化了哈希表。

另外一个重要的构造函数

transient Node<K,V>[] table;

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

其中 Node<K,V>[] table 是存储kv的结构,是一个 Node<K,V> 数组。

哈希桶

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),进行对应操作。最后再判断哈希表是否需要扩容。

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

其中 modCount 介绍过,记录 HashMap 内部结构发生变化的次数,主要用于 fast-fail 机制。但是 key 值对应的 value 被更新不会计数 modCount

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)
        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(树结构化的最小限制),不需要转换,table 需要 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(空的扩容后大小),如果自此有 put 方法调用,会写入新的空的 table,不会写入 oldTab。

为什么扩容两倍?

更加容易计算他们所在的新桶位置。如原桶长度是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。

当T1运行到 e.next=newTable[i] 时,T2运行到 Entry<K,V> next = e.next。

T1运行 newTable[i]=e, e=next,会产生的结果:newTable[i]=A,A.next=B,B.next=C,e=B。

T2运行 e.next=newTable[i],会产生的结果:B.next=A,同时 A.next=B,

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


Add a Comment

电子邮件地址不会被公开。 必填项已用*标注