Q:

Explanation about HashMap hash algorithm in this example

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.

A:

"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. 
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.

A:

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/

A:

This is mere coincidence and the order from EntrySet and KeySet is not guaranteed. Infact hashmap itself doesn't guarantee insertion order and this will order can also change during rehashing.
Now you are trying to insert primitive int in hashmap as key which internally does autoboxing and Integer object will be inserted as key.
Integer hashcode function is
public static int hashCode(int value) {
    return value;
} 

Means it just return directly the value, in your case 6,9 and 3
Then this hashcode is used internally by hashmap for computing to get index position
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

As you can see the bitwise operator with the given values will return 0 and exponential on those values will lead to same index poistion of 3 which leads to collision. So, hashmap then will store this using either LinkedList (prior java8) and in tree(java8 and its later version).
While iterating via keySet or entrySet, the order won't  be guaranteed and so the order which you are getting is mere coincidence.

