Double hashing
Encyclopedia
Double hashing is a computer programming
technique used in hash table
s to resolve hash collision
s, cases when two different values to be searched for produce the same hash key. It is a popular collision
-resolution technique in open-addressed
hash tables.
Like linear probing
, it uses one hash value as a starting point and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing
, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. In other words, given independent hash functions
and 
, the jth location in the bucket sequence for value k in a hash table of size m is:
Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The only solution to this is to rehash to a larger size.
On top of that, it is possible for the secondary hash function to evaluate to zero. For example, if we choose k=5 with the following function:
The resulting sequence will always remain at the initial hash value. One possible solution is to change the secondary hash function to:
This ensures that the secondary hash function will always be non zero.
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
technique used in hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
s to resolve hash collision
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
s, cases when two different values to be searched for produce the same hash key. It is a popular collision
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
-resolution technique in open-addressed
Open addressing
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array until either the target record is found, or an unused array slot is found, which indicates that...
hash tables.
Like linear probing
Linear probing
Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location. This is accomplished using two values - one as a starting value and one as an interval between successive values in modular...
, it uses one hash value as a starting point and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing
Quadratic probing
Quadratic probing is a scheme in computer programming for resolving collisions in hash tables.It is an open addressing method to handle overflows after a collision takes place in some bucket of a hash table....
, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. In other words, given independent hash functions
and , the jth location in the bucket sequence for value k in a hash table of size m is:Disadvantages
Linear probing and, to a lesser extent, quadratic probing are able to take advantage of the data cache by accessing locations that are close together. Double hashing has larger intervals and is not able to achieve this advantage.Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The only solution to this is to rehash to a larger size.
On top of that, it is possible for the secondary hash function to evaluate to zero. For example, if we choose k=5 with the following function:
The resulting sequence will always remain at the initial hash value. One possible solution is to change the secondary hash function to:
This ensures that the secondary hash function will always be non zero.
External links
- How Caching Affects Hashing by Gregory L. Heileman and Wenbin Luo 2005.
- Hash Table Animation