What is a hash table and how does it work?

The idea behind the speed

Instead of scanning a list to find a key, a hash table computes exactly where the value should be using a hash function. That is why looking up a key is usually as fast as reading one array slot.

// unordered_map is a hash table
unordered_map<string, int> phone;
phone["Asha"] = 99999;        // store
cout << phone["Asha"];        // fast lookup

// HashMap is a hash table
Map<String, Integer> phone = new HashMap<>();
phone.put("Asha", 99999);     // store
System.out.println(phone.get("Asha"));  // fast lookup

# Python dict is a hash table
phone = {}
phone["Asha"] = 99999      # store
print(phone["Asha"])       # fast lookup

Collisions

Different keys can hash to the same index. This is handled in two common ways. Chaining stores a small list at each index, and open addressing looks for the next free slot. Good hash functions keep collisions rare.