此示例中有关HashMap哈希算法的说明

Question

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

给定只有3个唯一数字的整数数组，它们会在O（n）时间中按升序（以及它们各自的频率）打印数字。

我想不使用counting sort算法来解决它，所以我想我可以做一个，for loop然后将数字插入a 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按升序打印，这让我感到困惑，因为我以为当的Keyof HashMap是一个整数时，哈希码应该是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

1. 哈希映射/哈希表中的“冲突”一词是两个不同键具有相同哈希码的情况。HashMap的Java实现使用List / RB-tree解决冲突，但是当您真正拥有3个整数键时，这绝对不是您的情况。
2. HashMap不保证元素的插入（或任何其他）顺序。还有其他不同的结构（如LinkedHashMap或TreeMap）可以保证一定的顺序。但是，针对您的案例使用这种结构会产生一些开销，因为您可以在固定时间内对3个元素的集合进行排序。您甚至可以使用Map.Entry数组代替HashMap来完成任务。