HashMap 基本存储逻辑

HashMap 是基于hashing的原理,我们可以通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它计算并获得键的hash值(并进一步获取索引位置),获取Map数组中的索引位置,判断是否该位置是否存在元素,
1、不存在则会重新创建一个,
2、否则的话判断当前节点的key是否与存入相同则获取该node用于替换value
3、该节点的key不同,则遍历:
如果是该节点的不是链表而是红黑树则遍历该树(当链表的值超过8则会转红黑树)
如果是该节点的是链表

if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash表的长度(不是元素长度)-1和hash值与运算计算索引位置
if ((p = tab[i = (n - 1) & hash]) == null)
//重新创建一个节点,最后一个参数null,指该节点仅有一个存储对象
else {
Node e; K k;
//否则的话判断当前节点的key是否与存入相同
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    e = ((TreeNode)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;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}
//如果存在相同的key则替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
}

jdk 1.8 加入红黑树村粗结构,即 当数组节点对应的链表长度大于8时,则自动转换成红黑出存储,当链表的值小于6则会从红黑树转回链表 以提升效率
HashMap 基本存储逻辑_第1张图片

你可能感兴趣的