源码|jdk源码之HashMap分析(一)

hash表是应用最广泛的数据结构，是对键值对数据结构的一种重要实现。
它能够将关键字key映射到内存中的某一位置，查询和插入都能达到平均时间复杂度为O(1)的性能。
HashMap是java对hash表的实现，它是非线程安全的，也即不会考虑并发的场景。

1. HashMap实现思路

hash表是常见的数据结构，大学都学过，以前也曾用C语言实现过一个：
https://github.com/frapples/c-data-struct/blob/master/lib/hashtable.c

偷点懒，这里就大概总结一下了，毕竟这篇博文jdk代码才是重点。

在使用者的角度来看，HashMap能够存储给定的键值对，并且对于给定key的查询和插入都达到平均时间复杂度为O(1)。

实现hash表的关键在于：

1. 对于给定的key，如何将其对应到内存中的一个对应位置。这通过hash算法做到。
2. 通过一个数组保存数据，通过hash算法hash(K) % N来将关键字key映射数组对应位置上。
3. hash算法存在hash冲突，也即多个不同的K被映射到数组的同一个位置上。如何解决hash冲突？有三种方法。
   1. 分离链表法。即用链表来保存冲突的K。
   2. 开放定址法。当位置被占用时，通过一定的算法来试选其它位置。hash(i) = (hash(key) + d(i)) % N，i代表第i次试选。常用的有平方探测法，d(i) = i^2。
   3. 再散列。如果冲突，就再用hash函数再嵌套算一次，直到没有冲突。

2. HashMap代码分析

2.1. Node节点

先来看Node节点。这表明HashMap采用的是分离链表的方法实现。
Node为链表节点，其中存储了键值对，key和value。

不过实际上，HashMap的真正思路更复杂，会用到平衡树，这个后面再说。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    /* ... */
}

还能发现，这是一个单链表。对于HashMap来说，单链表就已经足够了，双向链表反而多一个浪费内存的字段。

除此之外，还能够注意到节点额外保存了hash字段，为key的hash值。
仔细一想不难明白，HashMap能够存储任意对象，对象的hash值是由hashCode方法得到，这个方法由所属对象自己定义，里面可能有费时的操作。

而hash值在Hash表内部实现会多次用到，因此这里将它保存起来，是一种优化的手段。

2.2. TreeNode节点

这个TreeNode节点，实际上是平衡树的节点。
看属性有一个red，所以是红黑树的节点。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    /* ... */
}

除此之外，还能发现这个节点有prev属性，此外，它还在父类那里继承了一个next属性。
这两个属性是干嘛的？通过后面代码可以发现，这个TreeNode不仅用来组织红黑树，还用来组织双向链表。。。

HashMap会在链表过长的时候，将其重构成红黑树，这个看后面的代码。

2.3. 属性字段

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;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

最重要的是table、size、loadFactor这三个字段：

1. table可以看出是个节点数组，也即hash表中用于映射key的数组。由于链表是递归数据结构，这里数组保存的是链表的头节点。
2. size，hash表中元素个数。
3. loadFactor，装填因子，控制HashMap扩容的时机。

至于entrySet字段，实际上是个缓存，给entrySet方法用的。
而modCount字段的意义和LinkedList一样，前面已经分析过了。

最后，threshold这个字段，含义是不确定的，像女孩子的脸一样多变。。。
坦诚的说这样做很不好，可能java为了优化时省点内存吧，看后面的代码就知道了，这里总结下：

1. 如果table还没有被分配，threshold为初始的空间大小。如果是0，则是默认大小，DEFAULT_INITIAL_CAPACITY。
2. 如果table已经分配了，这个值为扩容阈值，也就是table.length * loadFactor。

2.4. 构造函数

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
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);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

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

第一个构造函数是重点，它接收两个参数initialCapacity代表初始的table也即hash桶数组的大小，loadFactor可以自定义扩容阈值。

this.threshold = tableSizeFor(initialCapacity);

这里也用到了类似前面ArrayList的“延迟分配”的思路，一开始table是null，只有在第一次插入数据时才会真正分配空间。
这样，由于实际场景中会出现大量空表，而且很可能一直都不添加元素，这样“延迟分配”的优化技巧能够节约内存空间。
这里就体现出threshold的含义了，hash桶数组的空间未分配时它保存的是table初始的大小。

tableSizeFor函数是将给定的数对齐到2的幂。这个函数用位运算优化过，我没怎么研究具体的思路。。。
但是由此可以知道，hash桶数组的初始大小一定是2的幂，实际上，hash桶数组大小总是为2的幂。

2.5. get函数

2.5.1. hash二次运算

先从get函数看起。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

我们发现，调用getNode时：

return (e = getNode(hash(key), key)) == null ? null : e.value;

其中调用了hash这个静态函数：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

也就是说，用于HashMap的hash值，还需要经过这个函数的二次计算。那这个二次计算的目的是什么呢？
通过阅读注释：

• 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.

嗯。。。大概意思是说，由于hash桶数组的大小是2的幂次方，对其取余只有低位会被使用。这个特点用二进制写法研究一下就发现了：如1110 1100 % 0010 0000 为 0000 1100，高位直接被忽略掉了。

也即高位的信息没有被利用上，会加大hash冲突的概率。于是，一种思路是把高位的信息混合到低位上去，提高区分度。就是上面这个hash函数了。

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

get函数调用了getNode，它接受给定的key，定位出对应的节点。这里检查了table为null的情况。此外first = tab[(n - 1) & hash]实际上就是first = tab[hash % n]的优化，这个细节太多，等会再分析。

代码虽然有点多，但是大部分都是一些特别情况的检查。首先是根据key的hash值来计算这个key放在了hash桶数组的哪个位置上。找到后，分三种情况处理：

1. 这个位置上只有一个元素。
2. 这个位置上是一个链表。
3. 这个位置上是一棵红黑树。

三种情况三种不同的处理方案。比较奇怪的是为什么1不和2合并。。。

如果是红黑树的话，调用红黑树的查找函数来最终找到这个节点。
如果是链表的话，则遍历链表找到这个节点。值得关注的是对key的比较：

if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))

类似于hashCode方法，equals方法也是所属对象自定义的，比较可能比较耗时。
所以这里先比较Node节点保存的hash值和引用，这样尽量减少调用equals比较的时机。

2.5.3. 模运算的优化

回到刚才的位运算：

first = tab[(n - 1) & hash]

这个位运算，实际上是对取余运算的优化。由于hash桶数组的大小一定是2的幂次方，因此能够这样优化。

思路是这样的，b_i是b二进制第i位的值：

b % 2ⁱ = (2^Nb_N + 2^N-1 b_N-1+ … + 2ⁱb_i + … 2⁰b₀) % 2ⁱ

设x >= i，则一定有2^xb_x % 2ⁱ = 0

所以，上面的式子展开后就是：
b % 2ⁱ = 2^i-1b_i-1 + 2^i-2b_i-2 + … 2⁰b₀

反映到二进制上来说，以8位二进制举个例子：

1. 显然2的幂次方N的二进制位是只有一个1的。8的二进制为00001000，1在第3位。
2. 任何一个数B余这个数N，反映二进制上，就是高于等于第3位的置0，低于的保留。如10111010 % 00001000 = 00000010

这样，就不难理解上面的(n - 1) & hash了。以上面那个例子，
00001000 - 1 = 00000111，这样减一之后，需要保留的对应位为全是1，需要置0的对应位全都是0。把它与B作与运算，就能得到结果。

2.6. put函数

没想到写这个比想象中的费时间。。。还有很多其他事情要做呢
这个put函数太长了，容我偷个懒直接贴代码和我自己的注释吧

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// onlyIfAbsent含义是如果那个位置已经有值了，是否替换
// evict什么鬼？table处于创造模式？先不管
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为null或者没有值的时候reisze()，因此这个函数还负责初始分配
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 定位hash桶。如果是空链表的话（即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)
            // 如果hash桶挂的是二叉树，调用TreeNode的putTreeVal方法完成插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果挂的是链表，插入实现
            // 遍历链表，顺便binCount变量统计长度
            for (int binCount = 0; ; ++binCount) {
                // 情况一：到尾巴了，就插入一条
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入会导致链表变长
                    // 可以发现，TREEIFY_THRESHOLD是个阈值，超过了就调用treeifyBin把链表换成二叉树
                    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;
    // 如果hash桶数组的大小超过了阈值threshold，就resize()，可见resize负责扩容
    if (++size > threshold)
        resize();
    // evice的含义得看afterNodeInsertion函数才能知道
    afterNodeInsertion(evict);
    return null;
}

思路大概是这样的逻辑：

1. 判断table是否分配，如果没有就先分配空间，和前面提到的“延时分配”对应起来。
2. 同样，根据hash值定位hash桶数组的位置。然后：
   1. 该位置为null。直接创建一个节点插入。
   2. 该位置为平衡树。调用TreeNode的一个方法完成插入，具体逻辑在这个方法里。
   3. 该位置为链表。遍历链表，进行插入。会出现两种情况：
      1. 遍历到链表尾，说明这个key不存在，应该直接在链表尾插入。但是这导致链表增长，需要触发链表重构成平衡树的判断逻辑。
      2. 找到一个key相同的节点，单独拎出来处理，得看onlyIfAbsent的参数。
   4. 完毕之后，这个时候hash表中可能多了一个元素。也只有多了一个元素的情况下控制流才能走到这。这时维护size字段，并且触发扩容的判断逻辑。

在这里我有几点疑惑：

1. 为什么null的情况、一个节点的情况、单链表的情况不合并在一起处理？因为性能？
2. 为什么采用尾插法不用头插法？头插法根据局部性原理岂不是更好吗？

在遍历链表时会同时统计链表长度，然后链表如果被插入，会触发树化逻辑：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

TREEIFY_THRESHOLD的值是8，也就是说，插入后的链表长度如果超过了8，则会将这条链表重构为红黑树，以提高定位性能。

在插入后，如果hash表中元素个数超过阈值，则触发扩容逻辑：

if (++size > threshold)
    resize();

记得前面说过，threshold在table已经分配的时候，代表是扩容阈值，即table.length * loadFactor。

3. 最后

考虑到篇幅够长了，还是拆分成两篇比较好，剩下的留到下一篇博文再写吧。