In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets, from which the correct value can be found.
Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after it is created). Instead, most hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and must be accommodated in some way.
In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized) cost per operation.
In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
Read more about Hash Table: Hashing, Collision Resolution, Dynamic Resizing, Performance Analysis, History
Famous quotes containing the word table:
“The best thing about Sassy Seats is that grandmothers cannot figure out how they work and are in constant fear of the child’s falling. This often makes them forget to comment on other aspects of the child’s development, like why he is not yet talking or is still wearing diapers. Some grandmothers will spend an entire meal peering beneath the table and saying, “Is that thing steady?” rather than, “Have you had a doctor look at that left hand?””
—Anna Quindlen (20th century)