V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
levizheng
V2EX  ›  Java

大佬们, hashmap 的源码有个不明白的地方求助

  •  
  •   levizheng · 2020-11-17 11:00:18 +08:00 · 2064 次点击
    这是一个创建于 1468 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请问一下。hashmap 在 putVal 的时候,为什么在当前的节点是红黑树的情况下,直接插入数据就可以,而不是像链表一样先循环遍历判断 key 是否相同呢?渣渣非科班小白不懂数据结构,求各位大佬赐教

    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;
                    }
                }
    
    
    
    8 条回复    2020-11-17 13:25:34 +08:00
    xuanbg
        1
    xuanbg  
       2020-11-17 11:28:56 +08:00
    循环遍历判断 key 是否相同的话,还用什么 hash……
    GM
        2
    GM  
       2020-11-17 11:37:57 +08:00
    循环遍历判断 key 是否相同的话,还用什么 hash…… +1
    Joker123456789
        3
    Joker123456789  
       2020-11-17 11:37:58 +08:00
    你再看一下 putTreeVal 这个方法的源码呢。
    aneureka
        4
    aneureka  
       2020-11-17 11:39:54 +08:00
    一楼不在 context 里 2333,你可以看看 TreeNode.putTreeVal 的方法实现,盲猜还是按红黑树搜索节点来做的(当然不同于简单循环遍历),有则替换,无则插入
    Joker123456789
        5
    Joker123456789  
       2020-11-17 11:43:33 +08:00
    @GM
    首先不同的对象,hashcode 可能会一样,这就导致了 你 put 两个不同的 key 可能 hashcode 一样,造成存到同一个下标里。 但是你明明 put 的是两个不同的 key,总不能直接覆盖吧,所以 才有了数组+链表的 数据结构,就是当 hash 碰撞时,在同一个下标里 把两个值存进去。 但是也不能直接追加吧,所以需要循环这个链表,判断 hasncode 和值是否都跟你 put 进来的这个 key 相等,如果相等就覆盖 value,不相等才追加。


    现在 hashmap 做了优化,当一个下标里的链表过长时,会自动转成红黑树。
    dasinigetudou
        6
    dasinigetudou  
       2020-11-17 11:47:06 +08:00
    ```
    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;

    ​ //比较根节点的 hash 值,dir 猜测是决定节点插入时应该插到左子节点还是右子节点

    ​ if ((ph = p.hash) > h)

    ​ dir = -1;

    ​ else if (ph < h)

    ​ dir = 1;

    ​ else if ((pk = p.key) == k || (k != null && k.equals(pk)))

    ​ //如果根节点的 key 和要插入节点的 key 相同,直接返回根节点

    ​ return p;

    ​ else if ((kc == null &&

    ​ (kc = comparableClassFor(k)) == null) ||

    ​ (dir = compareComparables(kc, k, pk)) == 0) {

    ​ //根节点的 key 和要插入的 key 不同,开始比较根节点的左右子节点

    ​ 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))

    ​ //找到相同的 key,将节点返回

    ​ return q;

    ​ }

    ​ //这里记录下 dir,可能是决定为了如果从子节点也找不到接下来创建新的节点插入到左边还是右边

    ​ 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;

    ​ }

    ​ }

    ​ }
    ```
    不知道分析的对不对~希望大佬一起交流
    dasinigetudou
        7
    dasinigetudou  
       2020-11-17 11:51:56 +08:00
    ```
    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;
    //比较根节点的 hash 值,dir 猜测是决定节点插入时应该插到左子节点还是右子节点
    if ((ph = p.hash) > h)
    dir = -1;
    else if (ph < h)
    dir = 1;
    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
    //如果根节点的 key 和要插入节点的 key 相同,直接返回根节点
    return p;
    else if ((kc == null &&
    (kc = comparableClassFor(k)) == null) ||
    (dir = compareComparables(kc, k, pk)) == 0) {
    //根节点的 key 和要插入的 key 不同,开始比较根节点的左右子节点
    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))
    //找到相同的 key,将节点返回
    return q;
    }
    //这里记录下 dir,可能是决定为了如果从子节点也找不到接下来创建新的节点插入到左边还是右边
    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;
    }
    }
    }
    ```
    levizheng
        8
    levizheng  
    OP
       2020-11-17 13:25:34 +08:00
    @Joker123456789
    @aneureka
    @dasinigetudou
    感谢大佬们,果然是 putTreeVal 方法里进行了判断,之前看的不仔细了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1165 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:39 · PVG 07:39 · LAX 15:39 · JFK 18:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.