Overview
A hash table T[0:m-1]
uses a hash function to map a universe of keys into slots of the hash table. It can be seen as a generalization of direct addressing (which has “hash function” ).
Load Factor
Consider hash table with slots that stores entries. Then the load factor for is defined to be , i.e. the average number of entries that map to the same slot.
Static Hashing
Static hashing refers to providing a single fixed hash function intended to work well on any data. Generally speaking, this should not be favored over random hashing.
Division Method
The division method for creating hash functions maps a key into one of slots by taking the remainder of divided by . That is, .
Multiplication Method
The multiplication method for creating hash functions first multiples a key by a constant and extracts the fractional part of . Then it multiplies this value by and takes the floor of the result. That is, .
Random Hashing
Random hashing refers to choosing a hash function randomly in a way that is independent of the keys being stored.
Universal Hashing
Let be a finite family of hash functions that map a given universe of keys into range . Such a family is said to be universal if
Bibliography
- Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
- “Universal Hashing,” in Wikipedia, April 18, 2024, https://en.wikipedia.org/w/index.php?title=Universal_hashing.