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.

---

hash table - hash coding