In
computer science, a
hash table, or a
hash map, is a
data structure that associates
keys with
values. The primary operation it supports efficiently is a
lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a
hash function into a
hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be.
Hash tables support the efficient addition of new entries, and the time spent searching for the required data is independent of the number of items stored (i.e.
O(1)).
Time complexity and common uses of hash tables
Hash tables are often used to implement
associative arrays,
sets and
caches. Like
arrays,
hash tables provide constant-time
O(1) lookup on average, regardless of the number of items in the
table. While theoretically the worst-case lookup time can be as bad as O(
n) this is for all practical purposes statistically impossible unless the implementation is buggy or unless n is small.
Compared to other associative array data structures,
hash tables are most useful when large numbers of records are to be stored, especially if the size of the data set can be predicted.
Hash tables may be used as in-memory data structures.
Hash tables may also be adopted for use with
persistent data structures; database indexes sometimes use disk-based data structures based on
hash tables, although
balanced trees are more popular.