54

我正在查看HashMapJava 中的实现，并且一直停留在某一点上。
函数是如何indexFor计算的？

static int indexFor(int h, int length) {
   return h & (length-1);
}

谢谢

4

5 回答 5

122

哈希本身是由hashCode()您尝试存储的对象的方法计算的。

您在这里看到的是根据 hash 计算存储对象的“桶” h。理想情况下，为了避免碰撞，您将拥有与最大可实现值相同数量的存储桶h- 但这可能对内存要求太高。因此，您通常拥有较少数量的具有碰撞危险的存储桶。

如果h是 1000，但您的底层数组中只有 512 个桶，您需要知道将对象放在哪里。通常，一个mod操作就h足够了，但这太慢了。鉴于HashMap底层数组的桶数总是等于的内部属性2^n，Sun 的工程师可以使用 的想法h & (length-1)，它对由所有 's 组成的数字进行按位与1，实际上只读取n哈希的最低位 (这和做的一样h mod 2^n，只是要快得多）。

例子：

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)
于 2012-06-04T09:58:52.907 回答
39

它不是在计算hash，而是在计算bucket。

该表达式对using 进行h & (length-1)按位操作，这就像一个位掩码，仅返回 的低位，从而形成 的超快变体。ANDhlength-1hh % length

于 2012-06-04T09:47:46.623 回答
3

上面的答案很好，但我想更多地解释为什么Java可以indexFor用于创建索引

例如，我有一个HashMap这样的（这个测试是在Java7上的，我看到Java8改变了HashMap很多但是我觉得这个逻辑还是很好的）

// Default length of "budget" (table.length) after create is 16 (HashMap#DEFAULT_INITIAL_CAPACITY)
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("A",1); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("B",2); // hash("B")=70, indexFor(hash,table.length)=70&(16-1) = 6
hashMap.put("P",3); // hash("P")=85, indexFor(hash,table.length)=85&(16-1) = 5
hashMap.put("A",4); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("r", 4);// hash("r")=117, indexFor(hash,table.length)=117&(16-1) = 5

您可以看到带有键的条目索引和带有键的"A"对象和带有键的"P"对象"r"具有相同的索引（= 5）。这是我执行上面的代码后的调试结果

在此处输入图像描述

图片中的表格在这里

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    transient HashMap.Entry<K, V>[] table;
    ...
}

=>我看到
如果索引不同，新条目将添加到表中
如果索引相同且相同hash，则新值将更新 如果索引相同且不同，则新条目将指向旧条目（如 a ）。然后你知道为什么有字段
hashLinkedListMap.Entrynext

static class Entry<K, V> implements java.util.Map.Entry<K, V> {
        ...
        HashMap.Entry<K, V> next;
}

您可以通过阅读 中的代码再次验证它HashMap。

与现在一样，您可以认为HashMap永远不需要更改大小（16），因为indexFor()总是返回值 <= 15 但它不正确。
如果你看HashMap代码

 if (this.size >= this.threshold ...) {
      this.resize(2 * this.table.length);

HashMapsize当>=时将调整表格大小（双倍表格长度）threadhold

是什么threadhold？threadhold计算如下

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
...
this.threshold = (int)Math.min((float)capacity * this.loadFactor, 1.07374182E9F); // if capacity(table.length) = 16 => threadhold = 12

是什么size？size计算如下。
当然，size这里不是 table.length。
每当您将新条目放入HashMap并HashMap需要创建新条目时（请注意，HashMap当键相同时不要创建新条目，它只会覆盖现有条目的新值）然后size++

void createEntry(int hash, K key, V value, int bucketIndex) {
    ...
    ++this.size;
}

希望有帮助

于 2018-07-31T13:04:38.963 回答
2

它正在计算将存储条目（键值对）的哈希映射的存储桶。存储桶 ID 为hashvalue/buckets length.

哈希图由桶组成；对象将根据存储桶 id 放置在这些存储桶中。

hash code / buckets length任何数量的对象实际上都可以根据它们的值落入同一个桶中。这被称为“碰撞”。

如果许多对象落入同一个桶中，则在搜索它们的 equals() 方法时将被调用以消除歧义。

碰撞次数与桶的长度成间接比例。

于 2012-06-04T09:48:30.080 回答
-3

bucket_index = (i.hashCode() && 0x7FFFFFFFF) % hashmap_size 可以解决问题

于 2018-11-05T02:50:03.353 回答