I've been learning Java recently, and I have a question.
I have learned that HashMap and Hashtable do not preserve the insertion order or the order based on the key. But I've encountered a situation where it doesn't follow.
import java.util.HashMap;
import java.util.Hashtable;
public class Main {
public static void main(String[] args) {
Hashtable<Integer, Integer> hashtableInt = new Hashtable<>();
Hashtable<String, Integer> hashtableStr = new Hashtable<>();
HashMap<Integer, Integer> hashMapInt = new HashMap<>();
HashMap<String, Integer> hashMapStr = new HashMap<>();
for (int i = 0; i < 25; i++) {
hashtableInt.put(i, i);
hashtableStr.put(String.valueOf(i), i);
hashMapInt.put(i, i);
hashMapStr.put(String.valueOf(i), i);
}
System.out.println("Hashtable with Integer keys : ");
for (int key : hashtableInt.keySet()) System.out.print(key + " ");
System.out.println("\n\nHashtable with String keys : ");
for (String key : hashtableStr.keySet()) System.out.print(key + " ");
System.out.println("\n\nHashMap with Integer keys : ");
for (int key : hashMapInt.keySet()) System.out.print(key + " ");
System.out.println("\n\nHashMap with String keys : ");
for (String key : hashMapStr.keySet()) System.out.print(key + " ");
}
}
Hashtable with Integer keys :
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Hashtable with String keys :
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 24 3 23 2 22 1 21 0 20
HashMap with Integer keys :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
HashMap with String keys :
22 23 24 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 20 21 %
In the output above, the Hashes that use Integer keys has a specific order. Only the Hashes adopting String as a key has no order. Furthermore, the key order between Hashtable and HashMap with Integer keys are different.
So what I want to know is...
Why do Hashtable().keySet() and HashMap().keySet() have an order? Generally Hashes and Sets do not have a specific order. Why is that? Did I miss something?
Why do Hashtable().keySet() and HashMap().keySet() have opposite orders? After all, these two will be hash, but does something work internally differently?
If keySet() is expected to have an order, why do Hashtable().keySet() and HashMap().keySet() have irregular order?
Thank you all.
I've debug the put() method and watched how it works, but it's too difficult for me.
You cannot rely on the order. While it isn't really "random" that this happens, one could definitely consider this accidental. Java just gives you the elements in the order these elements are stored in.
If you want a Map with a specified encounter order. See also SequencedMap for this.
This is because of the way how hash data structures store the data. These rely on distributing the data over multiple buckets (typically more buckets than data points).
For deciding which data point goes into which bucket, it calls the hashCode method of the object and then uses the modulus operations to distribute it over the buckets. In the case of Integer, this happens to give you back the original number.
So if you have 10 buckets and store the numbers 1,2,3,4,5,5,6 in these buckets, the number 1 would go to bucket 1 while 2 goes into bucket 2 etc. However, if you e.g. have numbers that are spread out more (or start at a different number), this won't work any more.
For example, if we store the numbers 10, 20 and 30 in a HashMap, the order doesn't work any more:
HashMap<Integer, Integer> hashMapInt = new HashMap<>();
hashMapInt.put(10, 10);
hashMapInt.put(20, 20);
hashMapInt.put(30, 30);
for (int key : hashMapInt.keySet()) System.out.print(key + " ");
On my system, this code results in the output 20 10 30.
When storing the elements as Strings, there is more data associated with each element and the hashCode method combines different characters/bytes so two Strings representing consecutive numbers have more spread out hashes.
The order of elements in a HashMap or Hashtable is not specified and could even vary across different JVMs.