java - 请分享一些关于java中的rehash方法的见解？

Question

我正在寻找有关哈希表/ HashMap 数据结构的更好的见解。

通过查看 API，我可以看出内部 Entry 类被称为存储桶。如果我错了，请纠正我。

请找到以下方法:-

  public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    Entry<K,V> e = tab[index];  <-------are we assigining null to this entry?
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

通过以下代码行

Entry<K,V> e = tab[index];

我可以假设我们将 null 分配给这个新的条目对象；这里也请指正。

所以我的另一个问题是:-

为什么我们不直接这样做

Entry<K,V> e = null 
 instead  of 
Entry<K,V> e = tab[index];

请在下面找到调试的屏幕截图:-

请分享您对此的宝贵见解。

Answer 1

Entry<K,V>是一个可以表示链表中链接的实例。请注意 next成员指的是列表中的下一个条目。

存储桶包含映射到同一索引的条目的链接列表。

Entry<K,V> e = tab[index]仅当该索引中尚未存储条目时才会返回 null。否则，它将返回该存储桶的链表中的第一个条目。

tab[index] = new Entry<>(hash, key, value, e);创建一个新条目并将其存储为存储桶中的第一个条目。前一个第一个 Entry 被传递给 Entry 构造函数，以便成为列表中的下一个(第二个)Entry。