Collections—HashMap
2022-08-21 16:16:58 0 举报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;
0 条评论
下一页
