HashMap

Basics

• Simple hash table, Keys and Values are not ordered
• get(), remove() are constant time
• put() costs O(1) on average, O(n) when collision happens
• iteration order is not predictable, as the keys are not sorted
• allow both keys and values to be null

TreeMap vs HashMap

• TreeMap are naturally sorted by order of key, HashMap is not:

TreeMap<Integer, Integer> tm = new TreeMap<>();
tm.put(3, 1);
tm.put(2, 2);
tm.put(1, 10);
tm.put(-100, 2);
tm.values(); //[2, 10, 2, 1]

HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(3, 1);
hm.put(2, 2);
hm.put(1, 10);
hm.put(-100, 2);
hm.values(); // [10, 2, 1, 2]