From TheBestLinks.com
de:Hashtabelle
ja:ハッシュテーブル
zh-tw:雜湊技術
zh-cn:哈希表
In computer science, a hash table is an associative array data structure that provides fast lookup of a record indexed by a key. Like arrays, hash tables can provide constant-time (O(1)) lookup on average, regardless of the number of items in the table. However, their (very improbable) worst-case time can be as bad as O(n).
Overview
Hash tables use an array to hold, or reference, the stored records. However, because we want to allow keys which are much larger than the range of valid indexes, or might even be a different type of data like strings, we need a way to convert each key into a valid index. We achieve this using a hash function, which is a simple function that takes a key and produces a valid index into the array; thus the name hash table.
The problem is that, since we have more potential keys than array indexes, multiple keys will map to the same array index. If we try to insert two keys that map to the same index, this is called a collision. To resolve this, a collision resolution strategy is used. Most collision resolution strategies are some form of linear search through the set of inserted keys that map to the hash index of the one being searched for; it can be shown that it is very improbable any of these sets will become large enough that such a search is expensive. However, to maintain this property, occasionally the hash table's array must be enlarged, and when this happens all the keys in it have to be added all over again. This is a very expensive, but also very infrequent, operation.
Hash tables allow reasonably simple implementations of the essential operations of associative arrays: lookup of a record given a key; setting a record at a given a key (adding or replacing as necessary); and removing a record with a given key. Their main competitor in practice is the self-balancing binary search tree. See a comparison of hash tables and self-balacing binary search trees.
Common uses of hash tables
Hash tables are found in a wide variety of programs. Most programming languages provide them in standard libraries. Most interpreted or scripting languages have special syntactic support (examples being Python, Perl, Ruby, Io, Smalltalk, Lua and ICI). In these languages, hash tables tend to be used extensively as data structures, sometimes replacing records and arrays.
Hash tables are commonly used for symbol tables, caches, and sets.
Choosing a good hash function
A good hashing of the key is essential for good hash table performance. Hash collisions are generally resolved by some form of linear search, so if a hash function tends to produce similar values for some set of keys, slow linear searches will result.
In an ideal hash function, changing any single bit in the key (including extending or shortening the key) would produce a seemingly random change in all of the bits of the hash, and this change would be independent of the changes caused by any other bits of the key. Because a good hash function can be hard to design, or computationally expensive to execute, much research has been devoted to collision resolution strategies that mitigate poor hashing performance. However, none of them are effective as using a good hash function in the first place.
One issue with the use of hash functions in hash tables is that the range of indexes of the hash table's array is limited, but it should be possible to use a single hash function for arrays of all conceivable sizes. To get around this, the index into the hash table's array is calculated in two steps:
- A generic hash value is calculated which fills a natural machine integer
- This value is reduced to a valid array index by finding its modulus with the array's size.
Hash table array sizes are sometimes set, by construction, to be prime numbers. This is done to avoid any tendency for the large integer hash to have common divisors with the hash table size, which would otherwise induce collisions after the modulus operation.
A common alternative to prime sizes is to use a power of 2 size, with simple bit masking to achieve the modulus operation. Such bit masking may be significantly computationally cheaper than the division operation.
In either case it is often a good idea to arrange the generic hash value to be constructed using numbers that share no common divisors (is coprime) with the table length.
One common problem that can occur with hash functions is clustering. Clustering occurs when the structure of the hash function causes commonly used keys to tend to fall closely spaced or even consecutively within the hash table. This can cause significant performance degradation as the table fills when using certain collision resolution strategies, such as linear probing.
In some applications, an untrusted user may be able to supply information to the hash table which causes collisions and/or clustering, resulting in poor performance and a limited compromise of the system. In such applications, it may be beneficial to conduct tests that simulate worst-case behavior by using a constant hash function.
Collision resolution
If two keys hash to the same value, they cannot be stored in the same location. We must find a place to store a new value if its ideal location is already occupied. There are a number of ways to do this, but the most popular are chaining and open addressing.
Chaining
In the simplest chained hash table technique, each slot in the array references a linked list of records that collide to the same slot.
Insertion requires finding the correct slot, and appending to either end of the list in that slot; deletion requires searching the list and removal.
Chaining hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing the table can be postponed for a much longer time because performance degrades more gracefully even when every slot is used. Indeed, many chaining hash tables may not require resizing at all since performance degradation is linear as the table fills. For example, a chaining hash table containing twice its recommended capacity of data would only be about twice as slow on average as the same table at its recommended capacity.
Alternative data structures can be used for chains instead of linked lists. By using a red-black tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n). However, since each list is intended to be short, this approach is usually inefficient in practice unless the hash table has grown far beyond its capacity without resizing or there are unusually high collision rates, as might occur in input designed to cause collisions.
From the point of view of writing suitable hash functions, chained hash tables are insensitive to clustering, only requiring minimization of collisions. On the other hand, open hash tables, as we'll see in the next section, depend upon better hash functions to avoid clustering which can destroy performance even in nearly empty tables.
The main disadvantage of chained hash tables, especially for small values, is that they require more more memory to store a pointer for each element in the table, as well as to store allocation metadata. This cost can be ameliorated by storing several items in each linked list node (see unrolled linked list).
Open addressing
Open addressing hash tables store all the records within the array. A hash collision is resolved by searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates the there is no such key in the table. Well known probe sequences include:
- linear probing
- in which successive slots a fixed distance apart in the array are probed,
- quadratic probing
- in which the space between probes increases quadratically, and
- double hashing
- in which successive probes use a different hash function.
A critical influence on performance of an open addressing hash table is the load factor, that is, the proportion of the slots in the array that are used. As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically. Once the table becomes full, most algorithms will fail to terminate. Even with good hash functions, load factors are normally limited to 80%. A poor hash function can exhibit poor performance even at very low load factors by generating significant clustering.
The following pseudocode is an implementation of an open addressing hash table with linear probing and single-slot stepping, a common approach that is effective if the hash function is good. Each of the lookup, set and remove functions use a common internal function findSlot to locate the array slot that either does or should contain a given key.
The following is wikicode, a proposed pseudocode for Wikipedia articles.
record pair { key, value }
var pair array slot[0..numSlots-1]
function findSlot(key) {
i := hash(key) modulus numSlots
loop {
if slot[i] is not occupied or slot[i].key = key
return i
i := (i + 1) modulus numSlots
}
}
function lookup(key)
i := findSlot(key)
if slot[i] is occupied // key is in table
return slot[i].value
else // key is not in table
return not found
function set(key, value) {
i := findSlot(key)
if slot[i] is occupied
slot[i].value := value
else {
if the table is almost full
rebuild the table larger (note 1)
i := findSlot(key)
slot[i].key := key
slot[i].value := value
}
}
- note 1
- Rebuilding the table requires allocating a larger array and recursively using the set operation to insert all the elements of the old array into the new larger array. It is common to increase the array size exponentially, for example by doubling the old array size.
function remove(key)
i := find_slot(key)
if slot[i] is unoccupied
return // key is not in the table
j := i
loop
j := (j+1) modulus numSlots
if slot[j] is unoccupied
exit loop
k := hash(slot[j].key) modulus numSlots
if (j > i and (k <= i or k > j)) or
(j < i and (k <= i and k > j)) (note 2)
slot[i] := slot[j]
i := j
mark slot[i] as unoccupied
- note 2
- For all records in a cluster, there must be no vacant slots between their natural hash position and their current position (else lookups will terminate before finding the record). At this point in the pseudocode, i is a vacant slot that might be invalidating this property for subsequent records in the cluster. j is such as subsequent record. k is the raw hash where the record at j would naturally land in the hash table if there were no collisions. This test is asking if the record at j is invalidly positioned with respect to the required properties of a cluster now that i is vacant.
Another technique for removal is simply to mark the slot as deleted. However this eventually requires rebuilding the table simply to remove deleted records. The methods above provide O(1) updating and removal of existing records, with occasional rebuilding if the high water mark of the table size grows.
The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping. In the case where many entries are to be deleted in one operation, marking the slots for deletion and later rebuilding may be more efficient.
Perfect hashing
If all of the keys that will be used are known ahead of time, perfect hashing can be used to create a perfect hash table, in which there will be no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.
Probabalistic hashing
Perhaps the simplest solution to a collision is simply to drop the item we're inserting, giving up the position to the item that is already there. In later searches, this may result in a small chance of false negatives, a search not finding an item which has been inserted.
An even more space-efficient solution which is similar to this is to keep only one bit for each bucket, each indicating whether or not a value has been inserted in its bucket. False negatives cannot occur, but false positives can, since if the search finds a 1 bit, it will say the value was found, even if it was just another value that hashed into the same bucket by coincidence. In reality, such a hash table is merely a specific type of Bloom filter.
See also
References
- NIST (http://www.nist.gov/) entry on hash tables (http://www.nist.gov/dads/HTML/hashtab.html)
- Open addressing hash table removal algorithm from ICI programming language, ici_set_unassign in set.c (http://cvs.sourceforge.net/viewcvs.py/ici/ici/set.c?rev=1.14&view=auto) (and other occurances, with permission).
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
