Hashtable

A hashtable is a data structure that implements an associative array, allowing efficient storage and retrieval of key-value pairs. Each key is processed by a hash function to produce an integer, which is reduced to an index in an underlying array called the table. The value is stored in or under that bucket.

To handle collisions (when two keys hash to the same index), hashtables use collision-resolution strategies such as separate chaining (storing multiple entries in a bucket, typically with linked lists or dynamic arrays) or open addressing (probing a sequence of slots until an empty one is found).

Operations typically include inserting or updating a key-value pair, retrieving a value by key, and deleting a key. Average-case time for these operations is constant, O(1), assuming a good hash function and an acceptable load factor; worst-case time can degrade to O(n) in the presence of many collisions or a poor hash function.

The load factor, defined as the number of stored elements divided by the table size, influences performance. To maintain efficiency, hashtables are often resized and rehashed when the load factor crosses a threshold.

Practical considerations include choosing a quality hash function, ensuring keys are hashable and, in many cases, immutable. In open addressing, deletions require special handling to preserve the probing sequence. Hashtables generally do not preserve insertion order.

Applications of hashtables include dictionaries, symbol tables, and caches. They are a core component in many programming languages, with built-in implementations such as Python dict, Java HashMap, and C++ unordered_map.