java - 本例对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.

我想不使用计数排序算法来解决它，所以我想我可以做一个 for 循环 并将数字插入 HashMap 然后通过 HashMap entrySet loop 并打印所需的信息。

函数如下:

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 ，这让我感到困惑，因为我认为 的 Key HashMap 是一个整数，哈希码应该是 hashIndex = key % noOfBuckets 所以当我将数字 6、9 和 3 作为我的 HashMap 键时 我以为会有冲突，我的函数应该打印(基于上面使用的数组):

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 /哈希表中的“冲突”术语是指两个不同的键具有相同哈希码的情况。 HashMap 的 Java 实现使用 List/RB-tree 来解决冲突，但是当你有 3 个整数键时，这绝对不是你的情况。
2. HashMap 不保证元素的插入(或任何其他)顺序。还有其他不同的结构，如 LinkedHashMap 或 TreeMap 可以保证某种顺序。但是在你的情况下使用这种结构会产生一些开销，因为你可以在恒定时间内对 3 个元素的集合进行排序。您甚至可以使用 Map.Entry 数组代替 HashMap 来完成您的任务。