0

问题:在阅读java8中WeakHashMap源码时,发现一个问题,put操作在发生hash冲突时,只有替换操作,但是没有新增链表节点的操作,链表节点是什么时候链上去的?

java8中的put源码如下:

public V put(K key, V value) {

    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int i = indexFor(h, tab.length);
     //这里只是在链表上找到key存在的节点做替换,但是对于key不存在的情况,
     //并没有创建新的节点链到原来的链表后面。
    for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
        if (h == e.hash && eq(k, e.get())) {
            V oldValue = e.value;
            if (value != oldValue)
                e.value = value;
            return oldValue;
        }
        //?????当hash 相同但是key不同不是应该创建新节点链到链表上吗?
    }

    modCount++;
    Entry<K,V> e = tab[i];
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * 2);
    return null;
}
骐骥 43
2019-05-16 提问
2 个回答
0

已采纳

首先纠正一点put操作在发生hash冲突时,只有替换操作这句表述不正确。


hash冲突是由于不同的k命中同一块地址,而替换操作明显是由于相同的k,相同的hash命中本该就是他的地方,这应该是正常寻址而已,正常寻址自然是要判断是否有更新/替换操作所以if的条件是用hash和key一起来判断的,只处理更新/替换操作


真正的hash冲突必然是会新增节点的。
weakhashmap 并没有对hash冲突时做什么特殊处理,单纯的就是添加到表头而已。只是提前做了更新/替换操作,确保之后保存的数据一定是新数据(非更新/非替换)。


Entry就是一个单链表你代码里面的new Entry(...)调用的是

Entry(Object key, V value,ReferenceQueue<Object> queue,int hash, Entry<K,V> next) {
    super(key, queue);
    this.value = value;
    this.hash  = hash;
    // 这行代码就是插入表头,新建节点的后继节点为传入的原链表next
    this.next  = next;
}

你贴代码中的for循环不过是检测当前put操作是否为替换\重复添加操作,如果不是重复添加或者更新,而是由于新增不一样的数据,则执行for之后的代码。

我把你贴的put方法加了些注释

public V put(K key, V value) {
    // 屏蔽null用一个new Object()代替
    Object k = maskNull(key);
    // hash计算
    int h = hash(k);
    // 获取当前最新hash表(删除了过期数据)
    Entry<K,V>[] tab = getTable();
    // 根据hash值寻址
    int i = indexFor(h, tab.length);
    for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
        // 如果hash和key都相同则可能会替换,在if逻辑里面判断具体处理逻辑
        if (h == e.hash && eq(k, e.get())) {
            V oldValue = e.value;
            if (value != oldValue)
                e.value = value;
            return oldValue;
        }
    }
    modCount++;
    Entry<K,V> e = tab[i];
    // 这里面将会把新节点添加到表头
    //上面代码已经处理了重复添加和更新value的操作,能执行到这里的代码都是新节点,
    //此时不需要管原来的节点里面保存的是什么可能是null也可能是一个链表,反正不管是啥
    //,直接放到后继节点就行,反正新加的节点一定是头节点,至于后继有没有,
    //根本不需要处理了,null也好还是什么也好无所谓,但是这里面对null值进行了处理,不可能真的是null)
    // 执行到这里不一定就一定有hash冲突,可能有,可能没有,`e = null` 就没有,`e !=null` 就有hash冲突
    // 但是我不管你冲突不冲突,反正插在表头。数据不可能重复,重复的上面的for遍历处理过了。
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * 2);
    return null;
}
0

首先,这个for循环的作用是通过if (h == e.hash && eq(k, e.get()))正确的寻找到key,==寻址和eq方法。当找到key时则替换新值,返回旧的值便于操作。
你想要在for循环中做hash相同但是key不同的节点创建,是要在循环中创建几次?
所以,当for循环查找无果时,应该在循环结束后实现创建的逻辑,如果我没猜错的话,玄机就在这行代码
tab[i] = new Entry<>(k, value, queue, h, e);
具体的插入逻辑你应该看Entry<>(k, value, queue, h, e)这个构造方法。后面的resize也符合插入新值后去判断size是否符合范围!

撰写答案

推广链接