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]