Explanation about HashMap hash algorithm in this example

Question

I was trying to solve this 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.

I wanted to solve it without using the counting sort algorithm, So what I thought is I could just do a for loop and insert the numbers in a HashMap and then loop through the HashMap entrySet and print the required info.

Here is the function:

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());
        }
}

which did the trick when I my array was: [3, 3, 2, 1, 3, 2, 1]

However the above array should not lead to any collision so I tried to use an array which should lead to collisions, one of the arrays I tested my function with was: [6,6,9,9,6,3,9] yet my function still printed the Keys in ascending order, which got me confused, because I thought when the Key of the HashMap is an Integer the hash code should be hashIndex = key % noOfBuckets so when I have the numbers 6, 9 and 3 as my HashMap keys I thought there would be collisions and my function should print(based on the above used array):

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

But instead it printed:

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

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?

Thanks.

Answer 1

1. "Collision" term in hash map/hash table is a situation when two different keys has the same hash code. Java implementation of HashMap use List/RB-tree for resolving collisions but when you have literally 3 integer keys this is definitely not your case.
2. HashMap doesn't guarantee the insertion(or any other) order of elements. There are different another structures like LinkedHashMap or TreeMap that can guarantee some order. But using this structures for your case is a little overhead cause you can sort your collection of 3 elements on the constant time. You can even use array of Map.Entry instead of HashMap for your task.

Answer 2

As mentioned already in above answer by @Serge Harnyk

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

I ran the above code you had shared in the question with the array [66,66,69,69,66,63,63,69] and the output was

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

Here, you can see that the output is not in sorted order. Another array for which the entrySet() didn't return the elements in sorted order was [10,5,5,10,10,5,10000000]

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

So, as the documentation of HashMap specifies the order of elements returned by entrySet() or keySet() of HashMap is not guaranteed to be in insertion/sorted order.

The the hash index against which a key is to be hashed is decided based on the hash code of that particular key generated by the hashCode() function implemented in HashMap. You can find the hash code of a key using the .hashCode() function

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

From these you can see that for Integer keys, the hash code is not hashIndex = key % noOfBuckets. Furthermore, you can define your own implementation of the hashCode() method and use it against the HashMap. You can find a detailed explanation implementing your custom hashCode() function here.

refer. https://www.geeksforgeeks.org/internal-working-of-hashmap-java/