What is a Hash Table?

A hash table is a data structure that stores key-value pairs, like a dictionary that looks up entries by their key. The magic is speed: a well-built hash table finds, inserts, or removes an entry in O(1) average time, no matter how many entries it holds.

The trick is the hash function. Every key gets converted into a bucket index, so we know exactly where to look without scanning the whole table. When two different keys land in the same bucket (a collision), we keep them together in a list at that bucket. This strategy is called chaining.

The five main operations on a hash table are:

1. Put: Store a key-value pair, or update the value if the key already exists.
2. Get: Look up the value for a given key.
3. ContainsKey: Check whether a key is stored in the table.
4. Remove: Delete a key-value pair.
5. Size: Return the number of pairs currently stored.

Let's create a HashMap class!