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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1492 天前的主题，其中的信息可能已经有所发展或是发生改变。

请问一下。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;
                }
            }

hashmap

环遍历

大佬

赐教

8 条回复 • 2020-11-17 13:25:34 +08:00

xuanbg

2020-11-17 11:28:56 +08:00

循环遍历判断 key 是否相同的话，还用什么 hash……

2020-11-17 11:37:57 +08:00

循环遍历判断 key 是否相同的话，还用什么 hash…… +1

Joker123456789

2020-11-17 11:37:58 +08:00

你再看一下 putTreeVal 这个方法的源码呢。

aneureka

2020-11-17 11:39:54 +08:00

一楼不在 context 里 2333，你可以看看 TreeNode.putTreeVal 的方法实现，盲猜还是按红黑树搜索节点来做的（当然不同于简单循环遍历），有则替换，无则插入

Joker123456789

2020-11-17 11:43:33 +08:00

@GM
首先不同的对象，hashcode 可能会一样，这就导致了你 put 两个不同的 key 可能 hashcode 一样，造成存到同一个下标里。但是你明明 put 的是两个不同的 key，总不能直接覆盖吧，所以才有了数组+链表的数据结构，就是当 hash 碰撞时，在同一个下标里把两个值存进去。但是也不能直接追加吧，所以需要循环这个链表，判断 hasncode 和值是否都跟你 put 进来的这个 key 相等，如果相等就覆盖 value，不相等才追加。

现在 hashmap 做了优化，当一个下标里的链表过长时，会自动转成红黑树。

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

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

2020-11-17 13:25:34 +08:00

@Joker123456789
@aneureka
@dasinigetudou
感谢大佬们，果然是 putTreeVal 方法里进行了判断，之前看的不仔细了