Hash Tables

In Fundamentals, we have learned how to use HashMap in Java, and dictionaries in Python. Essentially, they are all implemented with hash tables.

Hashing is an extremely effective and practical technique: the basic dictionary operations require only \(O(1)\) time on the average.

In this chapter, we mainly focus on three dictionary operations:

• search
• insert
• delete

Like a BST, we mainly focus on keys, so the ADT is a set. If we also consider the values, then it is a symbol table (a.k.a., map).