写点什么

HashMap 分析 - 新增

作者:zarmnosaj
  • 2022 年 6 月 29 日
  • 本文字数:1499 字

    阅读完需:约 5 分钟

新增

源码:


public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}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)        n = (tab = resize()).length;    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        Node<K,V> e; K k;        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 {            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;            }        }        if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}
复制代码


return putVal(hash(key), key, value, false, true);对 key 进行 hash 操作


if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;哈希表为空则创建表


if ((p = tab[i = (n - 1) & hash]) == null)根据 key 的哈希值计算出要插入的数组索引 i


tab[i] = newNode(hash, key, value, null);如果 table[i] 等于 null,则直接插入


if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))如果 key 已经存在了,直接覆盖 value


else if (p instanceof TreeNode)如果 key 不存在,判断是否为红黑树


e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);红黑树直接插入键值对


for (int binCount = 0; ; ++binCount)为链表结构,循环准备插入


if ((e = p.next) == null)下一个元素为空时,方法内部会转换为红黑树进行处理


if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;key 已经存在直接覆盖 value


if (++size > threshold) resize();超过最大容量,扩容

总结

以流程描述 HashMap 新增元素的逻辑:


  1. put(k,v)

  2. 判断哈希表是否为空

  3. 是则扩容

  4. 否则根据 ket 得到下标 index

  5. 判断 table<index>是否为 NULL

  6. 是则直接插入,然后判断 HashMap 的长度是否大于 threshold,是则扩容,否则结束

  7. 否则判断 key 是否相等

  8. 相等则直接复制,然后判断 HashMap 的长度是否大于 threshold,是则扩容,否则结束

  9. 否则判断 table[i]是否为红黑树

  10. 是则红黑树直接插入,然后判断 HashMap 是否需要扩容,不需要则结束

  11. 否则遍历链表进行插入

  12. 判断节点长度是否大于 8

  13. 是则红黑树直接插入,然后判断 HashMap 是否需要扩容,不需要则结束

  14. 否则链表插入,然后判断 HashMap 是否需要扩容,不需要则结束

发布于: 刚刚阅读数: 3
用户头像

zarmnosaj

关注

靡不有初,鲜克有终 2020.02.06 加入

成都后端混子

评论

发布
暂无评论
HashMap分析-新增_6月月更_zarmnosaj_InfoQ写作社区