9.4HashMap源码设计思想

目录介绍

  • 01.HashMap内部结构
  • 02.HashMap构造函数
  • 03.成员变量
  • 04.put(K key, V value)
  • 05.get(Object key)
  • 06.remove(Object key)
  • 07.resize()扩容
  • 08.Hash函数实现

00.一些常见问题思考

  • HashMap有哪些特点，简单说一下？HashMap内部的结构是怎样的？简单说一下什么是桶，作用是什么？
  • HashMap和Hashtable的区别？HashMap在put、get元素的过程？体现了什么数据结构？
  • 当有键值对插入时，HashMap会发生什么 ? 对于查找一个key时，HashMap会发生什么 ?
  • 如何保证HashMap线程安全？底层怎么实现的？HashMap是有序的吗？如何实现有序？
  • HashMap存储两个对象的hashcode相同会发生什么？如果两个键的hashcode相同，你如何获取值对象？
  • 为什么HashMap中String、Integer这样的包装类适合作为K？如果要用对象最为key，该如何操作？
  • HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
  • HashMap是如何扩容的？如何理解HashMap的大小超过了负载因子定义的容量？重新调整HashMap大小存在什么问题吗？
  • HashMap是线程安全的吗？多线程条件下put存储数据会发生什么情况？如何理解它并发性？

01.HashMap内部结构

  • HashMap内部的结构是怎样的
    • HashMap 内部的结构，它可以看作是数组（Node[] table）和链表结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储，你可以参考下面的示意图。
    • 这里需要注意的是，如果链表大小超过阈值（TREEIFY_THRESHOLD, 8，图中的链表就会被改造为树形结构。
  • 结构图如下所示
    • image
      image

02.HashMap构造函数

  • HashMap构造函数如下所示
    public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

03.成员变量

  • 成员变量如下所示
    //哈希桶数组，在第一次使用时才初始化
//容量值应是2的整数倍
transient Node<K, V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K, V>> entrySet;

//Map的大小
transient int size;

//每当Map的结构发生变化时，此参数就会递增
//当在对Map进行迭代操作时，迭代器会检查此参数值
//如果检查到此参数的值发生变化，就说明在迭代的过程中Map的结构发生了变化，因此会直接抛出异常
transient int modCount;

//数组的扩容临界点，当数组的数据量达到这个值时就会进行扩容操作
//计算方法：当前容量 x 装载因子
int threshold;

//使用的装载因子值
final float loadFactor;

04.put(K key, V value)

  • put函数大致的思路为：
    • 1.对key的hashCode()做hash，然后再计算index;
    • 2.如果没碰撞直接放到bucket里；
    • 3.如果碰撞了，以链表的形式存在buckets后；
    • 4.如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
    • 5.如果节点已经存在就替换old value(保证key的唯一性)
    • 6.如果bucket满了(超过load factor*current capacity)，就要resize。
  • put源码如下所示
    public V put(K key, V value) {
    // 对key的hashCode()做hash
    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;
    // tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算index，并对null做处理
    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;
    // 超过load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
  • put源码解析大概如下所示
    • 如果表格是 null，resize 方法会负责初始化它，这从 tab = resize() 可以看出。
    • resize 方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候，进行扩容（resize）。
    • 在放置新的键值对的过程中，如果发生if (++size > threshold)条件，就会发生扩容。
    • 具体键值对在哈希表中的位置（数组 index）取决于下面的位运算：i = (n - 1) & hash
    • 仔细观察哈希值的源头，我们会发现，它并不是 key 本身的hashCode，而是来自于 HashMap 内部的另外一个 hash 方法。注意，为什么这里需要将高位数据移位到低位进行异或运算呢？这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。
  • 当有键值对插入时，HashMap会发生什么 ?
    • 首先，键的哈希值被计算出来，然后这个值会赋给 Entry 类中对应的 hashCode 变量。
    • 然后，使用这个哈希值找到它将要被存入的数组中“桶”的索引。
    • 如果该位置的“桶”中已经有一个元素，那么新的元素会被插入到“桶”的头部，next 指向上一个元素——本质上使“桶”形成链表。

05.get(Object key)

  • 在理解了put之后，get就很简单了。大致思路如下：
  • 具体代码的实现如下：
    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) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
  • 大概的意思是
    • bucket里的第一个节点，直接命中；
    • 如果有冲突，则通过key.equals(k)去查找对应的entry
      • 若为树，则在树中通过key.equals(k)查找，O(logn)；
      • 若为链表，则在链表中通过key.equals(k)查找，O(n)。
  • 对于查找一个key时，HashMap会发生什么 ?
    • 键的哈希值先被计算出来
    • 在 mHashes[] 数组中二分查找此哈希值。这表明查找的时间复杂度增加到了 O(logN)。
    • 一旦得到了哈希值所对应的索引 index，键值对中的键就存储在 mArray[2index] ，值存储在 mArray[2index+1]。
    • 这里的时间复杂度从 O(1) 上升到 O(logN)，但是内存效率提升了。当我们在 100 左右的数据量范围内尝试时，没有耗时的问题，察觉不到时间上的差异，但我们应用的内存效率获得了提高。

06.remove(Object key)

  • 从 Map 中移除键值对的操作，在底层数据结构的体现就是移除对某个结点对象的引用，可能是从数组中、也可能是链表或者红黑树。
    public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}

/**
 * Implements Map.remove and related methods
 *
 * @param hash       key 的哈希值
 * @param key        the key
 * @param value      key对应的值，只有当 matchValue 为 true 时才需要使用到，否则忽略该值
 * @param matchValue 如果为 true ，则只有当 Map 中存在某个键 equals key 且 value 相等时才会移除该元素，否则只要 key 的 hash 值相等就直接移除该元素
 * @param movable    if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K, V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, index;
    //只有当 table 不为空且 hash 对应的索引位置存在值时才有可移除的对象
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K, V> node = null, e;
        K k;
        V v;
        //如果与头结点的 key 相等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) { //存在哈希冲突
            //用红黑树来处理哈希冲突
            if (p instanceof TreeNode)
                //查找对应结点
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
            else { //用链表来处理哈希冲突
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //node != null 说明存在相应结点
        //如果 matchValue 为 false ，则通过之前的判断可知查找到的结点的 key 与 参数 key 的哈希值一定相等，此处就可以直接移除结点 node
        //如果 matchValue 为 true ，则当 value 相等时才需要移除该结点
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) //对应红黑树
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p) //对应 key 与头结点相等的情况，此时直接将指针移向下一位即可
                tab[index] = node.next;
            else //对应的是链表的情况
                p.next = node.next;
            ++modCount;
            --size;
            //用于 LinkedHashMap ，在 HashMap 中是空实现
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

07.resize()扩容

  • 初始化或加倍表大小。
    • 如果为NULL，则按照在字段阈值中保持的初始容量目标分配。否则，由于我们使用的是二次幂展开，每个bin中的元素要么保持在相同的索引中，要么在新表中以两个偏移的幂移动。
  • 依据 resize 源码，不考虑极端情况（容量理论最大极限由MAXIMUM_CAPACITY 指定，数值为1<<30，也就是 2 的 30 次方），可以归纳为：
    • 门限值等于（负载因子）x（容量），如果构建 HashMap的时候没有指定它们，那么就是依据相应的默认常量值。
    • 门限通常是以倍数进行调整 （newThr = oldThr << 1），我前面提到，根据 putVal 的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
    • 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源。
  • resize()源码如下所示
    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; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        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;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
  • 当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。
    • 在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。resize的注释是这样描述的：

    • Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must eitherstay at same index, ormove with a power of two offsetin the new table.

    • 大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
  • 例如我们从16扩展为32时，具体的变化如下所示：
    • rehash
    • 因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
    • resize
    • 因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
    • resize16-32
    • 这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

08.Hash函数实现

  • 首先看下存储put代码
    public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


static final int hash(Object key) {
    int h;
    //高位运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。其中代码注释是这样写的：
    /**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
  • 在get和put的过程中，计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：
    • hash
  • 在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用&位操作，而非%求余)：
    (n - 1) & hash
  • 设计者认为这方法很容易发生碰撞。为什么这么说呢？
    • 不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。
    • 因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
  • 如果还是产生了频繁的碰撞，会发生什么问题呢？
    • 作者注释说，他们使用树来处理频繁的碰撞(we use trees to handle large sets of collisions in bins)，在JEP-180中，描述了这个问题：

    • Improve the performance of java.util.HashMap under high hash-collision conditions byusing balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

  • 之前已经提过，在获取HashMap的元素时，基本分两步：
    • 1.首先根据hashCode()做hash，然后确定bucket的index；
    • 2.如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。
  • 在Java 8之前的实现中是用链表解决冲突的
    • 在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
    • 因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题。
  • 为什么要这样实现hash？
    • 在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
贡献者: yangchong211