关于java中的HashMap实现

Question

我试图对hashmap进行研究并得出以下分析:

/sf/ask/811758461/#18492835

Q1你们可以给我看一个简单的地图,在那里你可以展示过程......如何通过使用这个公式详细计算给定键的哈希码..计算位置哈希%(arrayLength-1))其中应该放置元素(桶号),假设我有这个hashMap

HashMap map=new HashMap();//HashMap key random order.
         map.put("Amit","Java");
         map.put("Saral","J2EE");

Q2有时可能会发生2个不同对象的hashCodes相同.在这种情况下,2个对象将保存在一个存储桶中,并将显示为LinkedList.入口点是最近添加的对象.该对象指的是具有下一个字段的其他对象,因此一个.最后一个条目是指null.你们能用真实的例子告诉我这个...... !!

.

"Amit"将被分发到第10个桶,因为有点twiddeling.如果没有一点点twiddeling它将进入第7桶,因为2044535&15 = 7.如何可能请详细解释整个计算..？

快照已更新......

而另一个图像是......

Answer 1

如何使用此公式详细计算给定键的哈希码

如果出现这种情况，则按如下方式String计算：String#hashCode();

 public int hashCode() {
    int h = hash;
        int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

基本上遵循java doc中的方程式

 hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

关于此实现，需要注意的一件有趣的事情是，它String实际上缓存了其哈希码。它可以做到这一点，因为String它是不可变的。

如果我计算“Amit”的哈希码String，它将产生以下整数：

System.out.println("Amit".hashCode());
>     2044535

让我们对地图进行简单的放置，但首先我们必须确定地图是如何构建的。关于 Java 最有趣的事实HashMap是它总是有 2^n 个桶。所以如果调用的话，默认的桶数是16个，显然是2^4。

在此映射上执行 put 操作，它首先会获取键的哈希码。在此哈希码上发生了一些花哨的位调整，以确保较差的哈希函数（尤其是那些在较低位上没有差异的哈希函数）不会“过载”单个存储桶。

真正负责将密钥分发到存储桶的真正函数如下：

 h & (length-1); // length is the current number of buckets, h the hashcode of the key

这仅适用于两个存储桶大小的幂，因为它使用 & 将键映射到存储桶而不是模数。

由于位旋转，“Amit”将被分配到第 10 个桶。如果没有任何调整，它将进入第 7 个桶，因为2044535 & 15 = 7.

现在我们有了它的索引，我们可以找到存储桶了。如果存储桶包含元素，我们必须迭代它们并在找到时替换相等的条目。如果在链表中没有找到任何项目，我们将把它添加到链表的开头。

下一个重要的事情HashMap是调整大小，因此如果映射的实际大小高于阈值（由当前存储桶数量和负载因子决定，在我们的例子中为 16*0.75=12），它将调整后备数组的大小。调整大小始终为 2 * 当前存储桶数，保证为 2 的幂，以免破坏查找存储桶的功能。

由于存储桶的数量发生了变化，我们必须重新哈希表中的所有当前条目。这是相当昂贵的，因此如果您知道有多少个项目，您应该使用HashMap该计数来初始化，这样就不必一直调整大小。