Hashing and Hash Functions
A dictionary stores a set of keys (each possibly with satellite data) and supports INSERT, SEARCH and DELETE. A sorted array answers SEARCH in Θ(lg n) time and a balanced search tree does all three in O(lg n).
Algorithms · topic
Hashing
Division and multiplication hash functions, simple uniform hashing, chaining with load factor and expected costs, open addressing with linear, quadratic and double hashing, primary and secondary clustering, expected probes, deletion with tombstones and full insertion traces.
Study this topic
Collision Resolution: Chaining and Open Addressing
m-1], and collisions (two keys with the same slot) cannot be avoided once the universe is larger than the table (see Hashing and Hash Functions). The cost analysis uses expectation and linearity of expectation from Random Variables, Expectation and Variance.
Hashing cheat sheets
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.