Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Hash Tables

Glossary

direct-address table	To represent the dynamic set, we use an array, or direct-address table, denoted by T[0..m - 1], in which each position, or slot, corresponds to a key in the universe U. (See page 222)



bit vector	an array of bits (See page 222)



collision	occurs when two keys hash to the same slot (See page 224)



load factor	the average number of elements stored in a chain. We define the load factor α for T as n/m. Analysis will be in terms of α, which can be less than, equal to, or greater than 1. (See page 226)



simple uniform hashing	the assumption that any given element is equally likely to hash to any of the m slots, independently of where any other element has hashed to. (See page 226)



division method	In the division method for creating hash functions, we map a key k into one of m slots by taking the remainder of k divided by m. That is, the hash function is h(k) = k mod m. (See page 230)



multiplication method	The multiplication method for creating hash functions operates in two steps. First, we multiply the key k by a constant A in the range 0 < A < 1 and extract the fractional par of kA. Then, we multiply this value by m and take the floor of the result. (See page 231)



universal hashing	Using this method, enough of the functions work well for any random input set that if one function is chosen randomly from the class, it is likely to perform well on any input set that is actually presented. (See page 232)



open addressing	In open addressing, all elements are stored in the hash table itself. That is, each table entry contains either an element of the dynamic set or NIL. (See page 237)



probe	used to examine (or probe) the hash table in search of a particular item. (See page 237)



uniform hashing	generalizes the notion of simple uniform hashing to the situation in which the hash function produces not just a single number, but a whole probe sequence. Uniform hashing assumes that each key is equally likely to have any of the m! permutations of (0, 1, ... , m - 1) as its probe sequence. (See page 239)



auxiliary hash function	refers to an ordinary hash function h': U → {0, 1, ... , m - 1). (See page 239)



linear probing	a method which uses the hash function h(k, i) = (h'(k) + i) mod m for i = 0, 1, ... , m - 1. (See page 239)



primary clustering	A phenomenon where two keys that hash into differenct values compete with each other in successive rehashes. (See page 239)



quadratic probing	uses a hash function of the form h(k, i) = (h'(k) + c₁i + c₂i²) mod m, where h' is an auxiliary hash function, c₁ and c₂ ≠ 0 are auxiliary constants, and i = 0, 1, ... m - 1. (See page 239)



secondary clustering	a milder form of clustering in which different keys that hash to the same value follow the same rehash path (See page 240)



double hashing	involves the use of two hash functions, h1(key) and h2(key). h1, which is known as the primary hash function, is first used to determine the position at which the record should be placed. If that position is occupied, the rehash function rh(i, key) = (i + h2(key)) % tablesize is used successively until an empty location is found. As long as h2(key1) does not equal h2(key2), records with keys key1 and key2 do not compete for the same set of locations. (See page 240)



static	once the keys are stored in the table, the set of keys nover changes (See page 245)



perfect hashing	We call a hashing technique perfect hashing if the worst-case number of memory accesses required to perform a search is O(1). (See page 245)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.