2

当我运行这个程序

public class MyHashMapOperationsDebug {

    public static void main(String[] args) {
        MyHashMap hashMap = new MyHashMap();//MyHashMap is replica of HashMap
        for (int i=1;i<=11;i++)
        hashMap.put(i, i+100);
        }
}

并且MyHashMap.java有 

void addEntry(int hash, K key, V value, int bucketIndex) {  //replica of HashMap's addEntry method  

Entry<K,V> e = table[bucketIndex];
**System.out.println("bucketIndex : " + bucketIndex);**
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

输出： 

bucketIndex : 7  
bucketIndex : 14  
bucketIndex : 4  
bucketIndex : 13  
bucketIndex : 1  
bucketIndex : 8  
bucketIndex : 2  
bucketIndex : 11  
bucketIndex : 11  
bucketIndex : 2  
bucketIndex : 8

即使只有 11 个键存储在大小为 16 的映射中，为什么有些键会进入同一个存储桶？例如，索引为 2 和 11 的存储桶各有两个键

编辑： 阅读下面的输入后 一个问题：在上面使用 Java 的 HashMap 和整数的情况下，复杂性是什么。是 O(1) 吗？

4

4 回答 4

13

因为在事先不知道所有密钥的情况下，不可能设计一种算法来保证它们均匀分布。即使事先知道所有的键，如果它们中的两个具有相同的 hashCode，它们将始终在同一个桶中。

这并不意味着 HashMap 不是 O(1)。即使假设每个桶有 2 个条目，无论映射中的条目数量如何，这仍然会使每个 get 操作及时执行，而不依赖于映射中的条目数量，这是 O(1 ）。

于 2013-07-07T10:14:55.093 回答
1

在上面使用 Java 的 HashMap 和 Integer 的情况下，复杂性是什么。是 O(1) 吗？

是的。该Integer.hashcode()方法返回Integer自身的值，并将均匀分布在可能的散列值空间中。

所以哈希表的性能将是最优的；即O(1)用于get运营和O(1)（摊销）用于put运营。而且由于可能只有 2^32 个唯一键，因此我们不需要考虑如何HashMap扩展超出该点的问题。

于 2013-07-07T12:02:19.373 回答
0

例如，索引 2 和 11 的存储桶各有两个键：那是因为 hashCollision。如果您对所有 n 个元素都有 Hash Collision，则 HashMap 在查找中可以提供 O(n) 的性能。那是散列算法的糟糕设计。

事实上，你可以说为了避免这些冲突，你需要分配一些额外的空间。因为您的散列技术确保您没有很多冲突，并且要做到这一点，您显然需要额外的备份。

但同时，你不能完全避免冲突，因为如果你的散列技术使得每个桶只有一个条目，你将需要很多空间。所以，实际上hashCollisions，在有限的范围内是好的。

于 2013-07-07T10:26:14.237 回答
0

要设计一个 o(1) 散列函数，事先知道密钥分布是非常困难的。即使您知道密钥分配，您的密钥也可能映射到同一个插槽。因此，一旦您的负载因子移动到某个分数，您就需要进行重新散列。如果假设您的地图大小为 16 并且您有 17 个键，那么它将发生冲突。所以在这种情况下，您需要有一些机制来重新散列地图以消除潜在的冲突。

hashmap 中的查找操作是渐近 O(1)，但它也可以 GO TO o(n)。

于 2013-07-07T10:26:54.067 回答