HashMap中键为null的情况

Question

HashMap在内部如何区分null和0作为键。

根据这篇文章，null键的哈希码是0。这是正确的吗？如果是的话，两者应该在索引0的同一桶中，并且HashMap中应该有一个值，但实际上HashMap并不是这样工作的。

有人能解释一下吗？HashMap中null键的哈希码是多少？

示例代码：

HashMap<Integer,String> map=new HashMap<Integer,String>();
map.put(null, "abc");
map.put(0, "xyz"); // will it override the value for null as key?

System.out.println(map.get(null));  // abc
System.out.println(map.get(0));     // xyz

- Braj

---

哈希码不是唯一的 - null 的哈希码为 0 或任何其他值并不重要。在哈希映射中，每个哈希码不一定对应一个值。 - Jesper

@Jesper，如果hashCode()返回相同的值，它会检查equals()吗？如果是，那么在这种情况下它将如何工作？ - Braj

是的，但是null当然会被特殊处理，以避免发生NullPointerException。如果您真的想了解所有实现细节，请查找您JDK安装目录中的src.zip中可以找到的HashMap源代码。 - Jesper

在获取一个键时，所有具有相同哈希码的节点将使用equals与给定的键进行比较，直到找到匹配项。对于null，在实现中有一个条件语句：if (key == null) - JosEduSol

因此答案是HashMap以特殊的方式处理null。 - Braj

Answer 1

如果是这样，两个键都应该放在索引0的同一个桶中...

正确。

并且在HashMap中应该有一个值。

不正确。每个键都有一个单独的条目。这是由Map和HashMap规范保证的；也就是说，javadocs会为每个不同的键生成一个单独的条目。实现需要满足规范...而它确实满足了规范。

在Java 8之前，HashMap处理冲突的方式是将所有哈希到相同桶的条目“链接”在一起。 HashMap.get(key)逻辑将迭代相关桶的链，寻找匹配的条目。（在您的示例代码中，null和Integer(0)键的链将有单独的条目。）

在Java 8中，开始时工作方式相同，但是对于所有实现Comparable接口且链太长的情况进行了优化。在这种情况下，长链被转换为二叉树...使得O(N)链扫描变成O(logN)树搜索。

- Stephen C

---

是的，没错。但在这种情况下它是如何工作的？请再解释一下。如果两个具有相同哈希码的对象，那么最后一个对象的值应该覆盖前面的对象。对吗？ - Braj

不。仅仅因为键最终落在同一个桶中或具有相同的哈希码，并不意味着它们会互相覆盖。只有当它们根据 Object.equals 相等时，它们才会互相覆盖。 - Louis Wasserman

Answer 2

这两种情况都属于 hashCode()==0，但是由于equals不同，因此有两个条目，而且两个get返回相应的值。

包含 null 的情况：

public V put(null,"abc") {    
         if (key == null)
                    return putForNullKey(value);
}
private V putForNullKey(V value) {
        ..
        addEntry(0, null, value, 0); ==> 0th index with 0 hashCode
        return null;
    }

当参数为0时的情况：

public V put(K key, V value) {       
        int hash = hash(key.hashCode()); ==> 0
        int i = indexFor(hash, table.length); ==> 0
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { ==> false
                ..
            }
        }

        modCount++;
        addEntry(hash, key, value, i); ==> addition to link list
        return null;
    }

- harsh

---

静态最终整数哈希（Object key）{ int h; 返回（key == null）？0：（h = key.hashCode（））^（h >>> 16）; }我没有看到其中的putForNullKey方法..它只会为所有空键放置零..在反编译hashmap代码后。 - Luckyman Nevermore

Answer 3

你可能在哈希方面犯了一些错误。

1、当键为0时，哈希码可能不为0。因为哈希码是：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

2、当您的键为null时，JDK会调用一个特殊的方法来处理。

 if (key == null)
    return putForNullKey(value);

是的，当键为null时，哈希值为0。 如果您想了解更多，请查看JDK源代码。

- chenzhongpu

---

错误，整数的哈希码始终是其值。尝试 System.out.println(new Integer(0).hashCode()); // print 0。 - Braj

hashCode和hash是不同的，如果k在Integer i = 0中，k.hashCode()等于0。 - harsh

但是 HashMap 内部使用了 hashCode()，不是吗？ - Braj

Answer 4

这是可能的，因为HashMap中单个的Entry不仅仅是键值对，还有一个next字段，所以它类似于简单的链表，添加新entry的过程如下：

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

e本地变量（已经存在的变量）最终成为给定hash和bucketIndex的Entry中的next值。

- MirMasej