A hash table is a data structure that implements an associative array, also called a dictionary or map: it stores key and value pairs and finds a value from its key in roughly constant expected time by computing where the entry lives rather than searching for it. The idea of hashing with chaining appears as early as January 1953, in an internal IBM memorandum by Hans Peter Luhn, and hash tables now sit inside nearly every language runtime and database. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Origin YearThe January 1953 IBM memorandum by Hans Peter Luhn that used hashing with chaining. Core PrincipleCompute where a value belongs from its own key, so a lookup goes straight to the right place instead of searching. 1 FAQs
What happens when two keys land in the same slot of a hash table?
Collisions are handled by separate chaining or open addressing.
Because most hash table designs use an imperfect hash function, two different keys can produce the same index. This is called a hash collision, and a table has to handle it in some way. Two common strategies are separate chaining, which keeps several elements in the same slot using linked lists, and open addressing, which searches for the next available slot following a probing sequence.
Connections
Sources
1. Wikipedia: Hash Table
Wikimedia FoundationOverview and History sections
a hash table is a data structure that implements an associative array, also called a dictionary or simply map
History
In January 1953, Hans Peter Luhn wrote an internal IBM memorandum that used hashing with chaining.
Introduction
A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
In Group: Hashing and Probabilistic Structures, Lead
In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps keys to values.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.