Java HashMap 源代码分析

概述

　　HashMap是Java中的常用工具，位于java.util包里面。本文分析的Java SDK版本是1.8，在key冲突严重的时候，会使用红黑树进行优化。HashMap允许null作为key和value值，并且不是线程安全的，这是和HashTable不同的地方。如果需要线程安全的哈希表，推荐使用ConcurrentHashMap，而不是HashTable。另外，此实现不保证有序（如需要，请使用TreeMap）。

　　本文从常用的操作作为切入点，来分析HashMap的实现原理，着重分析几个重要的操作逻辑实现函数。对于红黑树的部分、iterator等部分不去展开论述。

　　HashMap的源代码大概有2000多行（1.8），但是，只要根据源代码中的注释，就可以清晰的分为：Static utilities, Fields, Public operations, iterators, spliterators, Tree bins等部分，我们会着重讨论Public operations部分，因为这里是其逻辑实现的核心。

实现原理简述

　　首先讲一下HashMap的基本实现原理。我们都知道HashMap是一个key、value构成的一个表，常用的两个操作是get和put。HashMap很依赖对象的hashcode方法：在进行任何操作之前，都会先用hashcode计算HashMap内部所对应的hash。HashMap内部有一个数组，在计算出hash之后会和数组的size（HashMap初始化时的capacity）进行位与操作，计算其在数组中的index，找到所在的桶。（桶一般是个list，如果比较长（默认大于8）会转化为红黑树。）如果是get，查找等于key的值返回；put则将值插入合适的位置。

几个概念说明

1. capacity: capacity是HashMap的容量，默认是16。其必须是2的幂，最大值是1<<30。
2. loadFactor: loadFactor是HashMap的负载因子，默认是0.75。capacity和loadFactor是影响HashMap性能的两个重要因素。
3. size: size是HashMap当前已经存储的key、value对的数目。
4. iterate: 遍历一个HashMap的时间复杂度是capacity + size。因此，不要将capacity设置的过大，或者将loadFactor设置的过小（通常默认的0.75就已经很合适了）。
5. structural modification: add、delete这种影响HashMap内部结构的修改称为“结构性修改”。如果只是set某个key的值，不是结构性修改。只有结构性修改，才需要同步。
6. fail-fast: 当一个HashMap的某个视图时（keySet、values、entrySet）创建后，如果有对其进行结构性修改，则会抛出ConcurrentModificationException。注意，同一个线程也可能发生这种情况。HashMap内部实现有一个modCount用来检查是否有这种修改。另外，这种机制并不保证一定会发生，所以并不能作为程序运行的某种条件，并不保证正确性。
7. treeify: 当映射到同一个hash的key过多时，Hashmap内部会进行“树化”，来提高查找效率。如果key的hashcode设计的足够好，理论上，每个hash值对应的链表长度服从泊松分布。长度超过8的概率只有千亿分之一。所以，树化的概率是很低的。

工具函数

1. hash函数

源代码如下：
```
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
可以看到，HashMap是支持null作为key值的，其hash为0。正常情况：使用hashcode的高16位bits和低16位bits进行异或运算。这样做的好处在于，既保证了充分利用hashcode的全部信息，又容易计算，是效率、易用性等综合因素的一个平衡，可以参考作者的注释里的解释。
2. tableSizeFor函数

源代码如下：
```
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;
}
```
这个函数是用来计算内部使用的桶数组初始capacity的。因为capacity必须是2的幂（bit表示是一个1后面全是0），这样才能与上面计算出来的hash异或，快速定位key所在的index。因此，我们需要一个数大于等于传入的参数cap，且是2的幂。上面的代码使用位运算能够快速的得到这个值。

算法思路：
- 1. 找到cap的bit位表示中的最左边1的位置i；
- 2. 将i后面的所有位置为1，转化为00011111111这种模式；
- 3. 加上1得到结果00100000000。
具体实现：简单期间，我们使用16个bits表示一个int。假设在n = cap - 1后n的bit位表示为0000001xxxxxxxxx这种形式：前面是几位0，接着是1，后面是其他位，用x代替，因为我们不用关心它是啥。

接下来，我们来演示算法的步骤：

0000001xxxxxxxxx => 00000011xxxxxxxx　　　　一个1变成2个1 00000011xxxxxxxx => 0000001111xxxxxx　　　　2个1变成4个1 0000001111xxxxxx => 00000011111111xx　　　　4个1变成8个1 00000011111111xx => 0000001111111111　　最终末尾全部变成1 0000001111111111 => 0000010000000000　　加上1得到最终结果

说明：为什么在开始时先给cap减1呢？是为了防止传入的cap刚好就是2的幂这种情况。先减去1再按照通常的情况计算。最后返回时，需要检查是否小于0，保证正确性。

重要函数

1. getNode函数
```
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) {   // 1.得到key所在的痛
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))   // 2. 始终先检查第一个node，如果是直接返回
            return first;
        if ((e = first.next) != null) {   // 3. 根据第一个node的类型，确定从树中找，还是链表中找
            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;
}
```
这个函数是HashMapget操作的实际实现逻辑函数。传入的参数hash和key，hash是通过上面介绍的hash计算而来。看源代码会发现很多内部函数都有这个参数。注意，第二个参数的类型为Object，并不是范型类型K。因为，这里并不需要关心其类型，只需要用到它的hashcode和equals两个函数（因此，如果key对象的实现，一定要保证这两个函数一致，否则，会得到意想不到的结果）。

实现逻辑：
- 1. 先通过first = tab[(n - 1) & hash]得到key所在桶的第一node，如果为null，证明这个key不存在。
- 2. 检查第一个node是否就是需要的，如果是直接返回。
- 3. 根据第一个node的类型（通过instanceof来判断），来决定是从树中，还是链表中遍历找。
说明：判断是否是目标key，其实最终是通过equals函数来决定的（key为null，通过==操作确定）。但是hash却是通过hashcode函数来决定的，所以，key对象一定要保证这两个函数一致。

2. putVal函数

 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) // 1. 检查是否HashMap刚初始化，没有分配内部数组，
        n = (tab = resize()).length;                    // 或者数组长度为0，如果是，执行resize
    if ((p = tab[i = (n - 1) & hash]) == null)    // 2. 得到要插入的目标桶，如果为空（null），则直接赋值
        tab[i] = newNode(hash, key, value, null);
    else {     // 3. 找到key在桶中（在树中）的位置，如果key存在，赋值给e，如果不存在，则e是null
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))  // key已经存在且是第一个
            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)   // 已经存在映射了，根据onlyIfAbsent决定是否覆盖
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;    // 下面的逻辑表示，这是一次新增，记录修改次数，并且检查是否需要resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这个函数，是put操作的实际实现逻辑函数。参数通过名字就可以明白，onlyIfAbsent表示是否只有没有这个key时才插入，evict参数时为LinkedHashMap用的，这里没有用到，不做介绍。

实现逻辑：

1. 检查是否HashMap刚新建或者刚初始化，如果是，先resize分配数据
2. 计算key所应该在的桶：如果桶为空（null），直接赋值（新增）；如果不为空，查找key所在桶的链表或者树中的位置。
3. 如果在第2步中找到，则表示之前已经有值存在，需要决定是否覆盖（覆盖）；反之，则赋值（新增）。
4. 如果是新增，则检查是否需要树化（treeify），并记录修改次数（modCount），递增size，并判断size是否超过阈值，是否需要resize。返回null。
5. 如果是覆盖，则根据参数决定是否覆盖，返回已经存在的值。

说明：

1. HashMap在new的时候，并没有分配内部数组对应的内存，只有在第一次插入key的时候，才会触发。算是延迟初始化优化。
2. 代码中的afterNodeAccess、afterNodeInsertion等hook函数是给LinkedHashMap用的。

3. 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;
    // 先计算新的capacity和threshold
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {  // 如果已经是最大容量了，阈值设为int最大值，返回
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  // 可以看到大部分情况是2倍的容量增加
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold 
                        // 这里的条件其实是：oldCap=0 && oldThr>0，这种情况应该是新建的HashMap
        newCap = oldThr;  // capacity被存储在threshold，可以参看源代码HashMap构造函数部分，这里使用的是有参构造函数
    else {               // zero initial threshold signifies using defaults 
                        // 这里的条件是：oldCap=0 && oldThr=0，这是使用无参构造函数
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 检查threshold是否没有设置，使用有参数的构造函数时会进入这步
    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) {  // 如果之前有值存在，则需要copy到新数组
        for (int j = 0; j < oldCap; ++j) {  // 遍历之前的数组
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // 为了垃圾回收？
                if (e.next == null) // 只有一个node，直接copy
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)  // 原来是用树存储的，分裂成两个树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order 保持之前node链表的顺序
                    Node<K,V> loHead = null, loTail = null; //低位的部分，左边的一位bit为0
                    Node<K,V> hiHead = null, hiTail = null; //高位的部分，左边的一位bit为1
                    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;
}

这个函数会在新hashmap第一次插入时调用，或者插入新值时，size超过阈值时触发。

实现逻辑

1. 先计算新的capacity和threshold，可以分为：新new的hashmap和已经有值的hashmap两类情况。新建的hashmap又可以分为使用无参构造器和有参构造器初始化两种。参见上面注释。
2. 分配新数组，设置新阈值。
3. 从旧数组copy值到新数组：依次遍历旧数组，如果只有一个值，直接copy；否则：
- 如果原来是用树存储的，分裂之前的树（不做深入介绍）；
- 如果链表存储，遍历链表分成两部分（根据高bit位是否为1）

说明

1. 容量达到最大时，不会进行任何操作了。
2. 扩容后需要copy数组，对于树形和链表两种桶，都要分成两部分：根据其hash & capacity为1还是0决定。

4. removeNode函数

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;
    // 查找key所在位置
    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;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;  // 第一个node就是所要的
        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
        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)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

该函数在remove key、value、entry的时候触发。参数matchValue表示只有在map值也相等时才删除，movable在树中删除node时才会使用，不做讨论。

实现逻辑

1. 查找key所在的位置
2. 如果找到，删除相应的node
3. 记录修改次数modCount，并递减size

总结

　　本文分析了Java1.8 HashMap源代码实现，着重对其设计思想、实现逻辑进行介绍。其中，对put、get、remove等基本操作的内部实现函数进行了详细剖析。但是，对于红黑树部分没有做任何介绍，因为红黑树本身实现比较繁琐，我们这里只需要它是个平衡二叉树即可（对于其实现细节的旋转、插入、删除需要单独做介绍，不是本文的重点）。另外，1.8版本的代码中加入了spliterator遍历器，以及加入了Function接口。对于这部分本文也没有涉及（比较简单，看代码很容易明白，也非核心逻辑）。