本文是基于jdk1.8写的
https://mp.weixin.qq.com/s/WKSg1hBSFtkG6j9iFozy2w
1.7hashmap扩容的时候出现成环的原因是因为我们扩容的时候链表的位置相反，这就导致了我们原来是A->B->C 变为C->B->A 而因为在线程情况下有可能出现其中一个线程已经设置了链表直接的关系，另外一个线程又重新设置导致其会出现两个节点互为对方的next
所以1.8的头插法避免了死循环
红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。
创建map
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor是把threshold变为2的幂次方，比如我们设置初始大小为9 则最适合的是2的4次方
这个初始的阈值后来会赋值在put时候设置为新的长度
static final int tableSizeFor(int cap) {
int n = cap - 1;
n等于n与n右移一位后的异或结果
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;
}
Put
ublic V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash是根据我们的key得到骑在数组中的位置
onlyIfAbsent：true代表不会改变存在的结果，即我们存入某个值 发现存在oldvalue 我们不会体会，false代表我们会体会
evict：如果是false代表数组正在创建
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
如果tab为null 或者tab长度为0 初始化table的size 或者增加为双倍
n = (tab = resize()).length;
(n - 1) & hash是计算这个hash值真正落位的地方 这样设计的好处是通过吧n设计成2的倍数
那么n-1在位运算的时候基本上都是 1111形式这样和hash与之后得到结果比较平均，散列特性比较好
想想看 加入你的hash 是1 和2 但是 与他与的是0000那么得到结果很容易一致，hash很容易冲突
if ((p = tab[i = (n - 1) & hash]) == null)
如果该位置没有元素直接插入一个新的节点
tab[i] = newNode(hash, key, value, null);
else {
否则构建一个链表把新的节点插入链表中，采用尾插法
Node<K,V> e; K k;
如果hash相同且 key相等于或者eaquals相等 则代表这两个key很有可能是同一个对象，那么我们就需要替换value，如果是TreeNode 代表链表长度超过阈值8了 形成了红黑树，剩余的就是就是加入到链表的尾部
代表了相同的key 需要替换 value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
代表了红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
尾插法 一直获取最后一个链表节点为null的插入进去
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;
}
如果发现链表某个节点是一样的 直接break（不需要替换因为本身key就是一样的）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
继续下一个
p = e;
}
}
如果e不等于null，说明已经存在该key
if (e != null) {
V oldValue = e.value;
如果onlyIfAbsent 为false 或者oldvalue 本身就是null 则替换value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess 由linkedhashmap，即把该节点移到链表最后
但是我们这边hashmap是数组实现的就不需要执行
afterNodeAccess(e);
返回oldvalue
return oldValue;
}
}
modCount是记录了hashmap 增删的次数，如果我们在迭代的时候发现其修改了 直接抛出
ConcurrentModificationException
++modCount;
如果size的长大于threshold 我们在resize
这边的阈值好像就是负载因子结合map容量的计算
if (++size > threshold)
resize();
也是给linkedhashmap使用的
afterNodeInsertion(evict);
我们直接返回null
return null;
}
初始化数组或者翻倍数组的长度（翻倍的意义在于hash匹配的时候 hash散列效果好）
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
计算老的数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
老的threshold
int oldThr = threshold;
int newCap, newThr = 0;
如果不是初始化
if (oldCap > 0) {
如果oldCap 大于等于MAXIMUM_CAPACITY
if (oldCap >= MAXIMUM_CAPACITY) {
重置threshold 直接返回，因为已经最大了 不会再扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
如果newCap 是oldCap 的2倍时候还小于MAXIMUM_CAPACITY 且oldCap 大于初始值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
直接threshold变为2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
初始化容量被设置为阈值大小
newCap = oldThr;
else { // zero initial threshold signifies using defaults
使用default
newCap = DEFAULT_INITIAL_CAPACITY;
阈值是容量乘以负载因子
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
如果新的阈值等于0 重新计算
获取newCap * loadFactor;结果
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
创建一个包含这么多节点的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
如果oldTab 不等于null 则转移数据到新的table
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
赋值给e
if ((e = oldTab[j]) != null) {
情况oldtable中该位置的数据
oldTab[j] = null;
e.next == null 代表该节点没有没有链表
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
如果已经是红黑树了 对红黑树进行切割，把他们插入到新的数组
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
用两个链表进行
Node<K,V> loHead = null, loTail = null; 这个是假设该链表的节点还是在原来的位置
Node<K,V> hiHead = null, hiTail = null;这个是用来存放节点到了新的位置=原来的位置+oldcap
Node<K,V> next;
do {
next = e.next;
(e.hash & oldCap) == 0 代表e.hash和newcap-1相与之后结果还是一样 ，如果不等于0则e.hash和newcap-1相与结果是原来的位置+oldcap。
hash表的链表上的节点之间的hash值 不一定相等 有可能只是低位相等 。之所以(e.hash & oldCap) 而不是
e.hash和newcap-1 是因为newcap-1与oldCap 的高位都一样 但是低位 前者都是1 后者都是0 ，我们通过这样 就相当于只比较了newcap的高位，从而得到hash的真正位置。
那么博客所说的省去了计算hash（这边的hash相当于节点的hash&newCap-1）的地方我是不是可以理解为因为oldcap的低位都是0 只有高位是1 所以计算节点hash与oldcap进行与相当于只是计算了高位的相与，所以性能更好？
if ((e.hash & oldCap) == 0) {
如果loTail ==null我们先尝试把结果塞入到loHead ，是因为loTail ==null 代表节点还没有链表
if (loTail == null)
loHead = e;
else
否则把节点插入loTail的next
loTail.next = e;
loTail = e;
}
else {
相当于插入到新的节点 逻辑跟上面一样
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
将loTail 的next赋值为null 插入到目前的j位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
将hiTail 的next赋值为null 插入到目前的j+oldCap位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
链表转为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
红黑树的插入
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
红黑树把自身的节点扩展到新的扩容后的数组中
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
get--根据hash得到数组的位置，如果数组上没有链表或者红黑树，则直接返回该节点
否则需要进一步根据key==e.key 或者key.eqauls(e.key)
eqauls和==本质上市一样的只是针对于不同的类型喜欢重写equals 所以比较不一样
有的是比较属性，有的是比较数值是否相等
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) {
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);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
网友评论