Hash table

The hash table, also known as the associative array, is a convenient data structure to hold key => value association?s.

A hash function takes arbitrary data as input and deterministic?ally returns an integer. This integer is then the index into the table?, which typically takes the form of an array. Whilst keys are most commonly strings, there is no requirement that they be so.

Hash tables offer O(1) (see Big O and Complexity theory) insertions, lookups, and deletions, with the caveat that collisions need to be dealt with. Techniques for dealing with collisions include probing, chaining, and rehashing. Note that probing and chaning are generally mutually exclusive.

Probing is, upon finding a collision, moving to the next free bucket? in the table. Chaining involves using each bucket as a pointer to another structure, such as an array, a linked list, or even another hash (preferably with a different size and/or hashing function). table?, which typically takes the form of an array. Whilst keys are most commonly strings, there is no requirement that they be so.

Both probing and chaining can be problematic because, as more and more elements are added to the hash, the O(1) property is lost! Rehashing is a technique to deal with this: by increasing the size of the table and recomputing the hash values with respect to the new table size, the O(1) property can be maintained.

Widely useful, hash tables are found in a wide variety of programs.