HashMap在Java中的实现。桶指数是如何计算的？

Question

我正在看HashMap在Java中的实现，在某一点上卡住了。
如何计算indexFor函数？

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

谢谢

Answer 1

匿名用户

上面的答案很好，但我想进一步解释为什么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;
    ...
}

=

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

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

与现在一样，您可以认为HashMap永远不需要更改大小（16），因为indexFor（）总是返回值

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

HashMap将在size

什么是threadhold<代码>Thread固定计算如下

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这里不是表格。长度
当您将新条目放入HashMap和HashMap时，需要创建新条目（请注意，HashMap键相同时不创建新条目，它只会覆盖现有条目的新值），然后size

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

希望能有所帮助

Answer 2

它不是在计算散列，而是在计算桶。

表达式h

Answer 3

散列本身由您试图存储的对象的hashCode（）方法计算。

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

如果h是1000，但是您的底层数组中只有512个桶，您需要知道将对象放在哪里。通常，对h进行mod操作就足够了，但是这太慢了。考虑到HashMap的内部属性，底层数组的桶数总是等于2^n，Sun的工程师可以使用h的想法

例：

     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)