hash table

(redirected from Hash-table)

hash table

hash table

A lookup table that is designed to efficiently store non-contiguous keys (account numbers, part numbers, etc.) that may have wide gaps in their alphabetic and numeric sequences.

Hash tables are created by using a hashing function (algorithm) to hash the keys into hash buckets. Each bucket is a list of key value pairs. Since different keys may hash to the same bucket, the goal of hash table design is to spread out the key-value pairs evenly with each bucket containing as few key-value pairs as possible. When an item is looked up, its key is hashed to find the appropriate bucket. Then, the bucket is searched for the right key-value pair.

If access to the values is desired other than through the keys, an indexing system can be built on top of a hash table. Such user-level search engines can be made to handle imprecise queries and misspellings. See key-value pair and DHT.


A Hash Table
When an item is looked up, its key is hashed into a hash value that becomes the index into the bucket. Then, the bucket is searched for the right key-value pair.
References in periodicals archive ?
For a hash-table index, the average time to search for a cell is O(1) while worst-case time is O(N) where N is the number of cells in the list.
One implementation uses a hash-table based index while the other does not have a location index.
Although the hash-table index performs slightly better than the binary tree and red-black index, the difference among them is relatively small.