Collections—HashMap

HashMap核心属性

false

true

对key进行hash运算hash(key)

判断当前map大小大于扩容阈值if (++size > threshold) 

false存在hash冲突

返回最终结果return e== null ? null : e.value;

当key为null时返回的hash值为0，所以HashMap允许key为null并且会放在数组下标为0的位置。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

循环链表，找到匹配key的值while ((e = e.next) != null);if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))

 return first;

true红黑树

e = oldTab[j]) != null

设置默认扩容因子0.75this.loadFactor = DEFAULT_LOAD_FACTOR

hash值

红黑树转链表阈值 static final int UNTREEIFY_THRESHOLD = 6;

判断当前节点是否是红黑树节点if (p instanceof TreeNode)

判断是否为红黑树first instanceof TreeNode

对hash和数组长度-1取模，得到数组小标。判断当前数组下标位置上是否有数据 if ((p = tab[i = (n - 1) & hash]) == null)

判断当前值是否为key所期望获取的值if (first.hash == hash &&          ((k = first.key) == key || (key != null && key.equals(k))))

链表false

扩容resize();

直接替换数组下标中的值  e = p;

扩容底层数组大小为原来的两倍newCap = oldCap << 1扩容阈值也为原来的两倍newThr = oldThr << 1;

判断扩容前的扩容阈值oldThr > 0

链表转红黑树阈值static final int TREEIFY_THRESHOLD = 8;

返回扩容后的数组return newTab;

判断扩容前底层数组大小if (oldCap > 0)

低位指针链表放入新数组中，位置不变。newTab[j] = loHead;高位指针链表放入（旧下标+老数组长度)位置上 newTab[j + oldCap] = hiHead;

根据hash& oldcap 是否为零将原链表使用高低位指针分成两个新链表while ((e = next) != null)if ((e.hash & oldCap) == 0)

设置map初始化大小为16newCap = DEFAULT_INITIAL_CAPACITY;根据扩容因子0.75 计算出扩容阈值 16 * 0.75 = 12            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

 hashMap.get(key)

链表转红黑树条件二，当数组长度小于该值是优先进行数组扩容static final int MIN_TREEIFY_CAPACITY = 64;

判断当前节点是否指向其他数据if (e.next == null)

return null;

判断当前节点是否是红黑树else if (e instanceof TreeNode)

新map大小为老的扩容阈值newCap = oldThr

for (int j = 0; j < oldCap; ++j)数据迁移，将老数组中的数据迁移到扩容后的数组中

默认初始化MAP大小为16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

HashMap最大容量2^30static final int MAXIMUM_CAPACITY = 1 << 30;

判断value是否与数组下标中的值相等if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))

进行has计算，同put操作hash(key)

HashMap hashMap =  new HashMap()

true数组上的元素既不是链表也不是红黑树

table = newTab;

 return e;

得到数组中的节点值first = tab[(n - 1) & hash]

判断当前数组为null或者数组大小为0f ((tab = table) == null || (n = tab.length) == 0)

HashMap默认扩容因子static final float DEFAULT_LOAD_FACTOR = 0.75f;

根据hash值直接放入新数组中newTab[e.hash & (newCap - 1)] = e;