Java中HashMap源码学习笔记。1.8 / 1.7 中设计思路比较
HashMap<String, String> map = new HashMap<>();
map.put("key", "value");
String v = map.get("key");
System.out.println(v);
jdk1.7
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始桶容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子
- 1.确定数组下标
int hashCode = hash(key)
int index = hashCode % table.length
- 2.put hash冲突
对于每一个新的元素，首先放到链表头部块 (效率最快)
--> 导致由于是单向链表所以上面的节点找不到
-->解决办法 讲新的链表赋值给head头部(相当于整个链表下移)
- 3.优化
对于2的整次幂的任意数X ---> hashCode % X == hashCode & (X -1) - 4.扩容
扩容后的节点复制操作
void transfer(Map.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Map.Entry<k, v> e : table) {
while (null != e) {
Map.Entry<k, v> next = e.next();
//计算扩容后的下标
int i = indexFor(e.hash, newCapacity);
//将整个e节点指向扩容后新的数组对应链表头节点
e.next = newTable[i];
//将新的链表下移
newTable[i] = e;
//e重新指向原始链表的下一个节点(准备进行下一次移动操作)
e = next;
}
}
}
- 扩容的问题
1.扩容后新链表的元素与之前链表元素位置颠倒
2.多线程下扩容的并发死锁问题 是因为线程共享链表 并且扩容后链表倒置
如何避免
- 1.使用CurrentHashMap
- 2.new HashMap(15,1) 指定已知容量和负载因子
- 问题思考
- 为什么要找一个2的整次幂的数作为桶的容量
为了计算下标效率更高 位运算效率更高
- 计算hashCode时为什么要进行右移以及异或操作
例如：由于上面的思路中2的整次幂数-1 高位全部为0 低位全部为1
15: 0000 1111
&
h: 0110 0111
= 0000 0111
只有低位参与了下标计算,hash碰撞的几率会会很大,导致hashMap链表高度过高,效率降低
所以右移之后将高位移到低位 再进行异或运算,这样计算出来的下标值更均匀,hash碰撞几率更低
- HashMap中key可以为null吗
可以只有一个 key为null直接put
- 计算扩容后数组的大小
设传入大小为L
计算： L -1 | L >>> 1 L >>> 2 L >>> 4 L >>> 8 L >>> 16
原理： 最高1位 依次右移得到以低位全为1的树 即 2的n次方 -1
最终结果 + 1
jdk1.8
数组 + 链表 + 红黑树
- hash计算 通过hashCode()的高16位异或低16位实现 更加散列
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 两个变量
// 当链表长度大于8时转为红黑树
static final int TREEIFY_THRESHOLD = 8;
//当红黑树高度小于6转为链表
static final int UNTREEIFY_THRESHOLD = 6;
1.8 往链表插值时直接插入到链表的尾部（区别与1.7）因为反正需要遍历，而这样做可以避免链表死锁
- 关键代码分析
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//当前数组位置没有元素，直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//当前数组位置已有元素
HashMap.Node<K,V> e; K k;
//key相同直接相当于更新
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果当前数组位置是红黑树
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
当前链表节点为尾部节点 直接放到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断当前长度是否大于阈值 进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
1.8 扩容
do {
next = e.next;
//为0不变为1则下标为结果加上oldLength
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;
}
}
注意:
在1.8中扩容是的算法有所变化，之前的 hash & newTable.length -1 改为 (e.hash & oldCap) == 0
总结
JDK源码中确实有许多代码设计精致的地方值得我们取挖掘学习. coding...
网友评论