Dictionary / Software Engineering Core

Hash Table

/hæʃ ˈteɪbəl/hash ta·blenoun
Data Structures CoreFoundational

Definition

1.[in data structures] a container that converts each key into an array position by arithmetic, giving constant-time average lookup at the cost of handling positions that collide.

Swapping the list for a hash table cut the lookup from linear to constant time.

Formal statement

i = h(k) mod m

h is the hash; m the number of buckets. Collisions are resolved by chaining or open addressing.

Etymology

From hash in the culinary sense of chopping and mixing, recorded in English from the seventeenth century; applied to scrambling a key into an address by Hans Peter Luhn at IBM in 1953.

Synonyms

  • dictionarysense 1 · Near
  • associative arraysense 1 · Absolute

See also

References

  • Cormen, T. et al. (2009). Introduction to Algorithms, 3rd ed., ch. 11.MIT Press.