Hashtable

Hashtable is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hashtable uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Overview

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are always accommodated in some way.

In a well-dimensioned hashtable, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hashtable designs also allow arbitrary insertions and deletions of key-value pairs, at constant average cost per operation.

Hash Function

In a hashtable, the hash function is used to compute an index into an array of buckets or slots, from which the correct value can be found. The ideal hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (unless the hash keys are fixed; i.e., new keys are not going to be inserted into the table after creation).

Collision Resolution

When the hash function causes a collision by mapping a new key to a cell of the hashtable that is already occupied by another key, the hashtable uses a method to determine a sequence of cells in which to search for a cell that is either empty or contains the key.

Applications

Hashtables are used in many different types of computer software, particularly for tasks such as database indexing, cache memory, and in certain algorithms such as Dijkstra's algorithm for finding the shortest path in a graph.

See Also

• Hash function
• Dijkstra's algorithm
• Associative array