HashMap 源码解读

为了控制篇幅，只简单概括一下扩容机制，至于源码就不搬上来了，写写真的很费劲

构成

Map 使用 Entry<K,V> 来记录一个键值对，HashMap中的链表节点 Node<K, V> 正是继承了这个类。其中包含了key、value、hash和对下一个节点的引用next。几个节点链接在一起形成了一条链表。

另外还有一种树上节点 TreeNode<K, V> 则是继承了 Node<K, V> 。

HashMap 底层维护了一个数组，数组中的元素则是由以上的链表或者红黑树构成。简单理解就是节点较少时使用链表，节点较多时使用红黑树以提高查询效率。

扩容

存放数据的数组不是固定不变的，默认的初始大小是16。

HashMap 中有一个默认的加载因子 0.75，通过当前的数组大小 * 加载因子能够得到一个【扩容阈值】。当键值对数量到达该阈值，HashMap 会对它的数组进行两倍扩容。

添加

往 HashMap 中添加一对映射关系，即往数组中添加一个节点。如果数组中已经存在 key，可以选择对已有的 value 进行替换或者保留；如果不存在，将创建一个新的节点加入到数组中。

替换或保留

此次添加的映射关系，可能在数组中已经存在了相同的key。可以根据需要，用新的value替换/覆盖原来的value；或是选择保留原来的value都行。

// 如果存在key，选择替换原来的value
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 如果存在key，选择保留原来的value
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

节点

一对映射关系就是一个节点，创建之初的节点只是一个普通的链表节点。当有需要时才会转换成红黑树的节点、或者从红黑树的节点退化成链表节点。

位置

添加一对映射关系，会根据 key 计算得到一个 hash，再通过数组的大小计算一个索引表示这个节点应该存放的位置：

index = hash & (table.length - 1)

hash & (table.length - 1)

为什么是这么个算法，根据规律，当这个 length 是2的幂次的时候满足如下等式

hash % table.length = hash & (table.length - 1)

hash % table.length 其实很好理解，就是根据hash，将各种节点在数组中依次排放。但是上面的位运算在计算速度上更具优势，因此会可以保证数组的大小是2的幂次，以此来加快每个节点存放位置的计算。

删除

可以从数组中删除一个节点，即删除了这对映射关系。可以选择含有 key 的映射关系，也可以选择严格相等的 key-value 键值对。

链表的树化

1. 节点的添加通常添加到对应链表的末尾。当满足以下两个条件时，则会将该链表，升级成红黑树：

   • 数组的大小不小于64

   • 链表中节点个数不小于8

2. 当链表需要树化的时候，但碍于数组大小太小，会暂不树化，先对数组进行扩容。

红黑树的退化

1. 在数组扩容的时候，会对原先的所有链表和红黑树，将其中所有的节点进行重新分布。

   因为数组大小的改变，每个 key 在数组中的索引位置也会发生变化。有些红黑树在重新分布之后，节点数量会减少，当这个数量减少到6的时候，则会将该红黑树退化成链表。

2. 在删除红黑树中的节点的时候，当节点数量少到一定程度，也会将该红黑树退化成链表