HashMap的自问自答
用最自然的方式掌握HashMap~
带着疑问去了解HashMap，下面用一个个问题，来拆解HashMap
数据存放的载体是什么
这个问题，其实是最核心的，也是最基础的问题
其实知道答案之前，也大概猜到了吧，没错，数据的载体，是数组，并且数组的类型是Node，节点的意思
//真正存放key value的地方
transient Node<K,V>[] table;
Node代表是类型，[]代表是数组，K、V代表的存储的key跟value泛型
Node其实是一个class，本地变量有key、value，key的hash值，还有指向下个node的引用
class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
hashmap的本质，其实是一个node类型的数组
其实不管是hashmap，还是arraymap，存储的载体都是数组，数组是一块连续的内存空间，天生就非常适合来存储内容
了解了这个核心概念后，后续的问题就自然而然冒出来了
数组的长度
既然是数组，那就必须有一个初始的长度，通过源码，可以知道数组的初始长度是16
# 二进制1左移4位，刚好是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
然后每次扩容的时候，长度都是*2，就像16 -> 32 ->64这样
# java.util.HashMap#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 ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
其中newCap = oldCap << 1表示旧的容量左移一位，相当于乘2
为什么容量都是2的倍数
核心还是为了性能，在读跟取的时候，经常需要根据key的hash值，快速定位到数组对应的position，而当数组的长度是2的倍数的时候，就可以用位运算快速的计算出来，下面是示例代码
int hash = hash(key)
//n指数组的长度，固定2的倍数
int n = tab.length
//用位运算高效计算hash值对应的数组的位置
Node result = table[(n-1)&hash]
这样，在存或者读的时候，都可以快速定位到数组对应的位置，比如实际读的代码，根据key获取到对应的node
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) {
//hash代表key的hash值
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) {
//直接拿到数组对应位置的node
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
//如果hash一样，并且key相等，就是我们要的node
return first;
if ((e = first.next) != null) {
//hash一样，key不一样，代表hash冲突了，需要另行处理
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;
}
当定位到数组对应的位置，不代表找到的node就是我们要的node，因为不同的key，有可能hash值是相同的，所以引申了下面的问题
碰到hash冲突怎么办
hashmap有两种处理冲突的方式，一是用链表来存储，存储的时候，也是新建一个node，跟当前的node组成链表，不断有新的冲突，就不断的往这个链表后面添加
//一个无限循环，由内部条件控制退出循环
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//e==null，代表到了链表的最后一个位置，然后把新的node插入最后一个位置
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//触发链表转成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果链表中，有原来的key，说明找到对应node了，结束循环
break;
p = e;
}
理论上，链表可以无穷无尽的往后面不断的添加，不过看上面代码也知道，当链表比较长的时候，就不适合采用链表来存储，会被转成红黑树来存储；
从性能角度考虑，链表只能从头开始往后检索，算法的时间复杂度是O(n)，而红黑树的时间复杂度是O(log n)，所以在hash冲突数量比较多的地方，用红黑树可以提升性能
链表跟红黑树转换时机：当链表达到8条内容的时候，就转成了红黑树
另外，当红黑树的内容小于6的时候，也会被重新转成链表的形式
可以用这个图片，形象的来展示
数据扩容时机
我们知道，hashmap的容量扩容都是翻倍增加的，那什么时候触发扩容呢
在默认情况下，容量是16，扩容系数是12
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
存储的个数超过扩容系数，就会触发扩容，而且每次扩容，都是容量跟扩容系数一起翻倍
newCap = oldCap << 1
newThr = oldThr << 1; // double threshold
容量跟扩容系数的关系如下
容量 | 扩容系数 |
|---|---|
16 | 12 |
32 | 24 |
64 | 48 |
128 | 96 |
256 | 192 |
越到后面，容量跟扩容系数的差距越大，个人感觉，这里的设计不是很合理，扩容系数明显偏小了
那如果是自定义容量的情况下呢？
比如当知道hashmap就只保存五条内容，初始化的时候，就把容量定位5，保存完5几条后，会不会触发内部的扩容？
触发扩容的时机，还是由实际容量决定，关系就是上面的表格那样，不过实际容量并一定等于初始容量，因为实际容量都是2的指数，关系如下图
初始容量值 | 实际初始容量 |
|---|---|
4 | 4 |
5 | 8 |
8 | 8 |
9 | 16 |
15 | 16 |
这样一看，就明白关系了，源码里面，是通过位运算来得出这个结果的
//Returns a power of two size for the given target capacity
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;
}
所以初始容量是5，实际容量是8，扩容系数是8*0.75=6，保存五条内容不会触发扩容
不过当初始容量是14的hashmap，保存14条内容，情况是如何呢？
val map = HashMap<String, String>(14)
for (i in 1..14) {
map.put("key$i", "value$i")
}
上面的代码，初始的容量是14，实际申请的容量是16，可以得知扩容系数是12，当存储到第13条内容的时候，就触发了扩容，容量扩大到32，浪费了内存空间，同时也降低的性能
所以，对于保存固定数量的hashmap，建议同时设定loadFactor为1.0
val map = HashMap<String, String>(14, 1.0f)
for (i in 1..14) {
map.put("key$i", "value$i")
}
这样的话，扩容系数跟容量一样的了，实际可以保存16条不会扩容，避免了内存浪费
数组容量会自动缩小吗
不会，容量只会扩大，即使item全部remove掉了，hashmap的容量也不会缩小；如果想用更节约内存的key value组件，可以考虑用ArrayMap
扩容都做了什么
在上面代码可以知道，key都是通过它的hash值与数组长度-1做二级制的与计算，确定对应的value在数组的position
//用位运算高效计算hash值对应的数组的位置，n就是数组长度
Node result = table[(n-1)&hash]
扩容后，n变了，原来key对应的value的position全部都要重新计算，所以每次扩容，都会重新排序全部的key value，是一个比较重的操作，下面是扩容的代码，也可以看下作为参考
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//j位置，有可能没有value，所以需要做判空
oldTab[j] = null;
if (e.next == null)
//把e赋值到新的position
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;
}
}
}
}
如果是可以大概预估hashmap的长度的场景，应该在初始化的时候，就直接赋值进去，可以避免触发扩容，提升性能
val n = 100 //预估的容量不会超过100
val hashMap = HashMap<String, String>(n, 1.0f)
还有别忘了第二个参数要填1.0f
腾讯云开发者
