本例对HashMap哈希算法的解释

Question

我正在尝试解决这个问题：

Given an array of integers with only 3 unique numbers print the numbers in ascending order (with their respective frequencies) in O(n) time.

我想不用counting sort算法解决，所以我想我可以做一个 for loop 并将数字插入 HashMap 然后 loop 通过 HashMap entrySet 并打印所需的信息。

函数如下：

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

当我的数组是：[3, 3, 2, 1, 3, 2, 1]

但是上面的数组不应该导致任何冲突所以我尝试使用一个应该导致冲突的数组，我测试我的函数的数组之一是：[6,6,9,9,6,3,9] 但我的函数仍然打印了Keys 按升序排列，这让我感到困惑，因为我认为当 HashMap 的 Key 是整数时，哈希码应该是 hashIndex = key % noOfBuckets 所以当我有数字时6, 9 and 3 作为我的 HashMap keys 我认为会有冲突，我的函数应该打印（基于上面使用的数组）：

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1

而是打印出来：

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

任何人都可以向我解释为什么我得到了我试图解决的问题的正确解决方案而不是我期待的答案吗？

谢谢。

Answer 1

我不确定你所说的 "collisions" 到底是什么意思，但是如果你阅读 HashMap (https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html) 的文档已经指出，没有关于顺序的声明:

"This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time."

稍后 "To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties."。

您最终使用 Integers 作为键，它们实现了 Comparable 接口，这意味着 HashMap 实现可以排序它们的键 - 它确实如此。

您还可以使用 Hash 实现，其中键的顺序是预定义的，因此是可预测的，例如 SortedMap。

Answer 2

"Collision" term in hash map/hash table 是两个不同的键具有相同哈希码的情况。 Java HashMap 的实现使用 List/RB-tree 来解决冲突，但是当你有 3 个整数键时，这绝对不是你的情况。
HashMap 不保证元素的插入（或任何其他）顺序。还有其他不同的结构，如 LinkedHashMap 或 TreeMap 可以保证某种顺序。但是在你的情况下使用这种结构会产生一些开销，因为你可以在恒定时间内对 3 个元素的集合进行排序。您甚至可以使用 Map.Entry 数组代替 HashMap 来完成您的任务。

Answer 3

摘自 实施说明 HashMap：

Tree bins (i.e., bins whose elements are all TreeNodes) are
ordered primarily by hashCode, but in the case of ties, if two
elements are of the same "class C implements Comparable",
type then their compareTo method is used for ordering.

后一种情况是整数 class: implements Comparable<Integer>.

整数的哈希码始终是其整数值。而且因为只会发生冲突，所以当两个不同的条目获得相同的哈希码时，整数不会发生冲突。
table 中节点的顺序取决于哈希码。可能是整数键被预排序了吗？

Answer 4

Could anyone please explain to me why I got the right solution to the question I was trying to solve instead of the answer I was expecting?

巧合

更新

正如其他人已经提到的，HashMap 在迭代其内容时不保证任何顺序，这与排序的 TreeMap 或保存条目顺序的 LinkHashMap 不同.所以是的，如果你的元素是排序的，那只是巧合。

Answer 5

正如@Serge Harnyk 在上面的回答中提到的

HashMap doesn't guarantee the insertion(or any other) order of elements.

我运行您在问题中与数组 [66,66,69,69,66,63,63,69] 共享的上述代码，输出为

Key= 66 Value= 3
Key= 69 Value= 3
Key= 63 Value= 2

在这里，您可以看到输出没有排序。 entrySet() 没有 return 元素排序的另一个数组是 [10,5,5,10,10,5,10000000]

Key= 5 Value= 3
Key= 10000000 Value= 1
Key= 10 Value= 3

因此，由于 HashMap 的文档指定了元素的顺序 return 通过 entrySet() 或 keySet() 的 HashMap 不是 gua运行teed insertion/sorted 顺序。

根据 HashMap 中实现的 hashCode() 函数生成的特定键的哈希码来确定要对其进行哈希处理的哈希索引。 您可以使用 .hashCode() 函数

查找密钥的哈希码

for(Map.Entry<Integer,Integer> entry : hm.entrySet()) {
    System.out.println("key= "+entry.getKey()+" has Hash Code= "+entry.getKey().hashCode()); 
}

Array [66,66,69,69,66,63,63,69] had the output

key= 66 has Hash Code= 66
key= 69 has Hash Code= 69
key= 63 has Hash Code= 63

Array [10,5,5,10,10,5,10000000] had the output

key= 5 has Hash Code= 5
key= 10000000 has Hash Code= 10000000
key= 10 has Hash Code= 10

从这些可以看出，对于整数键，散列码不是hashIndex = key % noOfBuckets。此外，您可以定义自己的 hashCode() 方法实现并将其用于 HashMap。您可以在此处找到实现自定义 hashCode() 函数的详细说明。

参考。 https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

Answer 6

这纯属巧合，无法保证 EntrySet 和 KeySet 的顺序。事实上 hashmap 本身不保证插入顺序，这个顺序也可以在重新散列期间改变。

现在您正在尝试将原始 int 作为键插入到 hashmap 中，它在内部进行自动装箱，并且 Integer 对象将作为键插入。

整数哈希码函数是

public static int hashCode(int value) {
    return value;
}

意味着它只是 return 直接值，在你的例子中是 6,9 和 3

然后hashmap内部使用这个hashcode计算得到索引位置

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如您所见，具有给定值的按位运算符将 return 0 并且这些值的指数将导致相同的索引位置 3，从而导致冲突。因此，hashmap 然后将使用 LinkedList（之前的 java8）和树（java8 及其更高版本）存储它。

通过 keySet 或 entrySet 进行迭代时，无法保证顺序，因此您得到的顺序纯属巧合。

本例对HashMap哈希算法的解释

Explanation about HashMap hash algorithm in this example

java

hashmap

hashcode

collision