5

仔细查看第 393 行的代码，看起来不同的哈希值已映射到相同的索引。我的理解是哈希码用于确定要使用 HashMap 中的哪个桶，并且桶由具有相同哈希码的所有条目的链表组成。他们为什么有e.hash == hash支票？



    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
4

3 回答 3

2

由于哈希码可以是 2^32 值中的一个，因此哈希映射很少有这么多桶（仅表需要 16GB 内存）。所以是的，您可以在地图的相同存储桶中拥有具有不同哈希值的对象（AFAIK 这是一个简单的模运算hachCode % numberOfBuckets）。

注意代码不是直接使用的key.hashCode()，而是hash(key.hashCode()).

于 2013-10-13T19:45:41.360 回答
1

此检查是考虑到碰撞的优化。
您可以有 2 个元素具有相同的哈希键（由于冲突），因此被映射到同一个存储桶。相同的键不同的实际元素。
因此，如果e.hash != hash您不需要检查是否相等（这可能是一项昂贵的操作）

于 2013-10-13T20:13:00.443 回答
0

答案出乎意料地是。我将 Sysout 放在 put() 的代码中以观察它的行为

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        System.out.println("Put: Table empty. Inflating table to threshold:" + threshold);
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    System.out.println("Put: Key not null:" + hash);
    int i = indexFor(hash, table.length);
    System.out.println("Put: Obtained index:" + i);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        System.out.println("Put: Iteraing over table[" + i + "] elements");
        Object k;
        System.out.println("Put: Checking if hash & key are equal");
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    System.out.println("Put: Incrementing modCounter");
    modCount++;
    System.out.println("Put: Adding a new Entry[hash="
            + hash + ", key=" + key + ", value="
            + value + ", i=" + i + "]");
    addEntry(hash, key, value, i);
    return null;
}

然后使用以下输入进行测试， 

MyHashMap p = new MyHashMap<>();
p.put(0, "Z");
p.put(1, "A");
p.put(17, "A");

猜猜输出是什么 

Put: Table empty. Inflating table to threshold:16
Inflate: RoundUpPowerOf2 of size=16
Inflate: Setting Min of [capacity * loadFactor, MAXIMUM_CAPACITY + 1] as threshold
Inflate: Given values[capacity=16, loadfactor=0.75, MAXIMUM_CAPACITY=1073741824
Creating array of Entry[] with size:16
Put: Key not null:0
IndexFor: calculating index for [given hash=0, length=16]
Put: Obtained index:0
Put: Incrementing modCounter
Put: Adding a new Entry[hash=0, key=0, value=Z, i=0]
Put: Key not null:1
IndexFor: calculating index for [given hash=1, length=16]
Put: Obtained index:1
Put: Incrementing modCounter
Put: Adding a new Entry[hash=1, key=1, value=A, i=1]
Put: Key not null:16
IndexFor: calculating index for [given hash=16, length=16]
Put: Obtained index:0
Put: Iteraing over table[0] elements
Put: Incrementing modCounter
Put: Adding a new Entry[hash=16, key=17, value=A, i=0]
因此，如您所见，两个条目存储在同一个索引中。很高兴看到这样的行为。好奇地试图得到这个答案。

于 2015-08-04T07:41:04.063 回答