首先
平时开发的时候，HashMap的使用一定是非常多的，它实现了对键值对的操作，让我们可以很方便的存储和检索键值对。对于它的名称，是这样去理解的：
Map，中文有映射意思，从key--->value是一种映射。
另外，其内部实现用到了取hash的方法
相信大家都能把 HashMap用得很溜，所以这里就不去对它的使用方法进行叙述了。这里主要讲一下其内部实现，另外找几处个人觉得设计得十分巧妙的代码来分析一下。
内部实现
首先我们来认识一下Node ，它继承自Map.Entry：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
一个 Node 对象即是一个 kv对（key value 键值对）。
HashMap内部定义了一个Node<K,V>[] table，这个数组用于存储kv对。table形如：
table
那么这些kv对 是怎么找到自己在table中的位置的呢？
image.png
首先是求得键的 hashcode，然后通过 index = (n-1) & hashcode 计算获取到这个 kv对 在数组中的下标（n是数组table的size）。这时候，问题来了。现实情况存在不同的 key 的 hashcode 相同，那么数组 table 中的每个元素需要存储多个 kv对。正是这样，table 中的每个元素也称作为 bucket（桶），一个 bucket 中存储了多个 kv对。
一个 bucket 也就是一个 Node 对象，bucket 其实是一个链表，我们看到了 Node 对象中有这样一个字段：
Node<K,V> next;
正是 next 字段实现了链表的效果，可以让一个 Node 指向另一个 Node。所以每个 bucket 是长这样的：
bucket
这里补充一下，其实 bucket 的形态是有两种，链表和红黑树，这里先不对红黑树的形态进行讨论。
了解了HashMap的内部结构之后，下面我们看看通过key查询value的步骤：
- 通过key计算得到index，由而得到bucket的位置。
- 遍历bucket中的每个Node，若找到一个Node，并且该Node的键与key相等，则该Node的value就是我们需要查找的value；否则，则返回null。
一般而言，每个桶中的kv对的数量不会很大，从而在查找的过程中避免了大量的循环操作，这也是HashMap高效的原因所在。可是，假若发生了一个bucket中有大量的kv对，那么在查询时应该怎么去避免较多的循环呢？
此时，HashMap就会把这个bucket从链表转化为红黑树，从而提高查询效率。
红黑树
在源码中，是这样判断的：
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
TREEIFY_THRESHOLD是预先设定的阈值，若当前的bucket中kv对的数量达到阈值之后，就会调用treeifyBin方法将链表变成红黑树。
从整体上来讲，HashMap的内部结构就是这些了。下面的内容是对源码中一些巧妙的代码细节进行分析。
巧妙的细节
table的size总是为2^n，并且HashMap的最大容量是 1<<30
table是HashMap中的数组。随着Map中的kv对越来越多的时候，table的size是需要不断变大的，但是table的size总是为2^n。
在上面，我们讲过，下标的计算方式是index = (n-1) & hashcode，n即table的长度，table的长度总是2的整数倍。那么就可以保证 n-1 的二进制位全部为1，进一步可以保证公式index = (n-1) & hashcode计算出的下标均匀分布。
其实，table的size总是为2^n就是HashMap的最大容量为1<<30的原因。
1<<31 = -2147483648，是一个负数，显然不能作为table的长度。
Map初始化容量大小
我们可以通过这个构造方法初始化HashMap并指定Map的容量：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
可是Map的容量大小必须是2的整数倍，所以啊，初始容量大小并不能直接设置为initialCapacity，而应该设置为2^n，并且满足：
- 2^n大于等于initialCapacity。
- 2^n尽量小。
源代码中是通过如下方法找到这个真正的初始容量的：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Integer.numberOfLeadingZeros这个方法计算bit位前面0的个数，如整数2的bit位为：00000000 00000000 00000000 00000010,它从左到右有连续的30个0，那么Integer.numberOfLeadingZeros(2)=30。
可以结合下图对tableSizeFor方法进行理解，首先cap前面有x个0，那么cap-1前面就有x个或者x+1个0；对-1进行右移操作之后，就得到图中a，b两种情况。
1过程计算
我们可以看到tableSizeFor方法，在对-1进行>>>之后还+1处理了，因为a，b满足前面都是0，后面都是1，在对其+1处理之后就会变成2的倍数。所以cd一定为2^n。下面对c，d分别进行说明：
- cap前面有x个0，而c前面有x-1个0，那么c一定满足大于cap。
- d前面0的个数和cap一样，都是x个。我再回顾一下b这种情形：当cap-1之后前面0的个数增加了1，发生这种情况就说明cap本身就是2的倍数。cap和d前面0的个数一样，进一步说明d一定等于cap。
最后c，d就是我们在找的那个大于等于initialCapacity最小的2^n了。
2过程计算
table的size进行double时，需要重新计算table数组里面元素的下标
HashMap对table的size进行调整的方式是进行Double，由于kv对的下标计算方式与size有关，所以size调整之后下标也需要跟着一起做调整。
当桶中只有一个节点时，做法很简单，根据公式index = (n-1) & hashcode计算即可得到新的下标。
当桶中有多个元素时，也可以用同样的方法遍历计算它们的下标。但是，源代码中并没有这样去处理，而且找到了另一种较高效的方法：
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;
}
下图中的cap即数组table的size，对cap double之后，发现它们两者唯一的区别就是：
cap -1 第 x-1 位是0，2xcap-1 第 x-1 位是1
double cap
此时我们结合下标计算公式能够想到下面两种情况：
- 若hash的第 x-1 位是0，那么hash & (2xcap-1)计算出的下标和hash & (cap-1)计算出的下标一样。
- 若hash的第 x-1 位是1，那么新下标的第 x-1 位也是1，进一步我们可以得到新下标=老下标+cap。
通过上面的分析来理解这段代码就比较简单了，是通过(e.hash & oldCap) == 0来判断hash的第 x-1 位是0还是1，如果是0即加到loHead链表中，否则就加到hiHead链表中。
最后loHead的下标是老下标j，然后hiHead的新下标即j+oldCap。
最后
HashMap的作者对二进制操作的贼流畅，膜拜膜拜膜拜～
网友评论