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. |