Linear probing is a collision resolution scheme for hash tables, the data structures that hold a collection of key-value pairs and look up the value tied to a given key. It belongs to the open addressing family, alongside quadratic probing and double hashing, in which every table cell stores a single key-value pair. When the hash function sends a new key to a cell that is already taken, linear probing scans forward through the table to the closest following free location and places the key there. A lookup follows the same path, starting at the cell the hash function names and moving along the table until it reaches a cell holding the matching key or an empty cell. The scheme was invented in 1954 by Gene Amdahl, Elaine M. McGraw and Arthur Samuel, and independently by Andrey Yershov, and Donald Knuth first analyzed it in 1963. Its strength is good locality of reference, which keeps it fast on standard hardware, while its weakness is a greater sensitivity to the quality of the hash function than some other collision resolution schemes. With a random hash function, a 5-independent hash function or tabulation hashing, it takes constant expected time per search, insertion or deletion.
Facts
Time Complexity
Time Complexity (category) Connections
Credited To
Source Linear probing (Wikipedia)
Source Linear probing (Wikipedia)
Source Linear probing (Wikipedia)
In Field
Source Linear probing (Wikipedia)
Invented
Source Linear probing (Wikipedia)
Source Linear probing (Wikipedia)
Source Linear probing (Wikipedia)
Sources
1. Linear probing (Wikipedia)
Lead section [complexity-category]
It takes constant expected time per search, insertion, or deletion when implemented using a random hash function, a 5-independent hash function, or tabulation hashing.
In Field: Algorithms and Complexity Theory, Lead section
Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key-value pairs and looking up the value associated with a given key.
In Group: Hashing and Membership Filter Algorithms, Lead section
Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key-value pairs and looking up the value associated with a given key.
Invented: Gene Amdahl, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
Credited To: Gene Amdahl, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
Invented: Arthur Samuel, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
Credited To: Arthur Samuel, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
Invented: Andrey Ershov, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
Credited To: Andrey Ershov, Lead section [invented]
It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov) and first analyzed in 1963 by Donald Knuth.
View the SourceReader 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.