linear probing hash table Algorithm

Linear probing is a scheme in computer programming for resolve collisions in hash tables, data structures for keeping a collection of key – value pairs and looking up the value associated with a given key. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the nearest following free location and inserts the new key there. Another early publication of this method was by Soviet researcher Andrey Ershov, in 1958.

The first theoretical analysis of linear probing, showing that it takes constant expected time per operation with random hash functions, was given by Knuth. The idea of an associative array that lets data to be accessed by its value rather than by its address dates back to the mid-1940s in the work of Konrad Zuse and Vannevar shrub, but hash tables were not described until 1953, in an IBM memorandum by Hans Peter Luhn. significant later developments include a more detailed analysis of the probability distribution of the running time, and the proof that linear probing runs in constant time per operation with practically usable hash functions rather than with the idealized random functions assumed by earlier analysis.

linear probing hash table source code, pseudocode and analysis