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).