HashMap实现原理
源码详解
1. 构造函数
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity,float loadFactor)
HashMap(Map<? extends K, ? extends V> m)
2. 常量
DEFAULT_INITIAL_CAPACITY = 1 << 4 // 初始化容量 16
MAXIMUM_CAPACITY = 1 << 30 // 最大容量 1 073 741 824
DEFAULT_LOAD_FACTOR = 0.75f // 负载因子， 超过 ‘容量*负载因子’，开始扩容 *2
TREEIFY_THRESHOLD = 8 // 一个桶树化的阀值，当key.hashcode,相同超过8，会转成红黑树
UNTREEIFY_THRESHOLD = 6 //一个桶链表化的阀值，当key.hashcode,相同低于6，会转成链表
MIN_TREEIFY_CAPACITY = 64 //哈希表最小树形化容量，<64,即使key.hashcode超过8也不会树化
3. 核心函数
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1、初始化hash表，由此可见 hashMap的初始化是在调用时，不是在调用构造函数时
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2、计算key存放下标：当前数组大小-1 & 当前hash值。如果此下标下没有元素，直接放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//3、如果节点存在直接替换旧值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4、红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//5、链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8转为红黑树处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 存在直接覆盖旧值
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;
//allbacks to allow LinkedHashMap post-actions
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//6、超过容量，就扩容
if (++size > threshold)
resize();
//allbacks to allow LinkedHashMap post-actions 为linkedHashMap服务的，输入和输出有序
afterNodeInsertion(evict);
return null;
}
get
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) {
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) {
//先判断头节点，算法和插入时一致 (n-1)&hash
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);
//递归查找与key相同桶的节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4. 总结
1、initialCapacity默认16，元素达到容量的0.75倍时扩容；扩容在原来的容量*2
2、当key.hashcode相同时，会在当前节点上维护一个链表结构，当链表个数大于8且当前hash表中容量不小于64，会将链表转换成红黑树结构；相反如果树的个数低于6，会在转回链表
3、hashmap的初始化在调用put的时候执行
4、initialCapacity值为2的幂次方
5、hashmap在并发中会造成死循环，节点回环
5. 源码解惑
- 默认值为什么是16，负载因子为什么是0.75？
看下源码，注释上说 ：Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity。
在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素个数和概率的对照表。
从上面的表中可以看到当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。
为什么是16，不是15或者18 参考问题2。
- 为什么容量要是2的幂次方？
The default initial capacity - MUST be a power of two.
原因是减少hash碰撞的概率。计算元素下标的方式：(n - 1) & hash.
举个栗子：如果一个容量是15，两个元素hash值分别是8、9。根据(n-1)&hash 计算 (15-1)&8 = 1110&1000 =1000; (15-1)&9=1110&1001=1000。14的最后一位是0，&上0、1都是0，所以1的位置永远不能存储数据。所以0001、0011、0101、0111这些都是无法存储数据的，增加了hash碰撞的几率.
-
hashmap在多线程下为什么会死循环？
原因是hashmap是线程不安全的，在put的时候会造成节点回环。
节点回环形成的原因：
hashMap扩容的时候，会重新计算下标，放入新Node中，摘取resize()关键代码，在多线程下，T1在44行的时候被挂起，由T2执行扩容操作，例如，在容量为2的hashMap中，存放3、7、，T2执行
image.png
扩容后
这时候由T1执行，T1执行的时候 e = oldTab[j] 指向了key:7 ,e.next = key:3，将key:7放入newTable,然后e和e.next向下移 会发现key:3的next =key:7 ，这时候环型连接形成了
