Java8 集合源码之HashMap
1 首先看构造函数
共四个,看一个就够了如下:
public HashMap() {
this.loadFactor = 0.75F;
}
this.loadFactor为增长因子,默认为0.75
2 往下看put()方法:
public V put(K var1, V var2) {
return this.putVal(hash(var1), var1, var2, false, true);
}
上面我们可以看到它会对map 键进行hash如下:
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
上面讲var1无符号右移16位再与hashCode异或,再往下看putVal()如下:
以下是hashmap的数据结构(数组+链表+红黑树):
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab为空,进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据hash值获取节点,为空就创建一个新的
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//取出找到的hash的节点p.hash与新的hash进行比较,并判断p.key与key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; //都相等就取原来的p
//如果是红黑树节点进行红黑树插入(默认只有超过TREEIFY_THRESHOLD才会有链表转为红黑树)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//hash和key不同时相等的情况
for (int binCount = 0; ; ++binCount) {
//该链表只有一个头节点,创建一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果大于 TREEIFY_THRESHOLD (桶元素超过8)则转为红黑树(替换链表),并跳出循环
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
//上面都不成立(p.next与新加的hash、key不相等; p.next不为空)然后就将p的指针知道p.next
p = e;
}
}
//如果e存在则覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //记录修改次数
//盘但是否到达临界值,大于则将数组设置为原来的2被,并拷贝到新数组
if (++size > threshold)
resize(); //调整分配大小
afterNodeInsertion(evict);
return null;
}
更多稍后会更新~~~~~~~~~~