Hash table

A hash table stores key–value entries in an array of buckets, using a hash function to choose where each key belongs. It handles collisions when distinct keys map to the same bucket.

Hash function: A function that maps input data to a fixed-size value, often used to select a hash table bucket. Its output helps determine the bucket used for each key.
Key–value pair: A pair of associated items in which one item, the key, identifies the other, the value. Each hash table entry associates a lookup key with its value.
Associative array: An abstract collection that associates keys with values and supports lookup by key. It is the key–value interface commonly implemented by a hash table.
Binary search tree: A tree structure that organizes keys so searches follow comparisons from the root to a matching node or insertion position. It maintains key order, while a hash table does not.
Amortized analysis: An analysis method that bounds average cost per operation over a sequence of operations. It explains why occasional expensive resizing can coexist with cheap typical insertions.
Collision resolution: Techniques for storing and retrieving entries when distinct keys map to the same hash table location. A hash table needs a way to distinguish keys assigned to one bucket.
Array data structure: A sequence of elements stored at indexed positions, typically in contiguous memory. The buckets in a hash table are arranged as indexed storage.
Hash set: A set implementation that uses hashing to test membership and store distinct elements. It uses hash table machinery when values matter only as membership keys.
B-tree: A balanced search tree whose nodes contain multiple keys and children, commonly used for storage systems. Its ordered access and block-friendly structure suit workloads where hashing is insufficient.
Expected value: The probability-weighted average of the possible values of a random variable. Expected-time claims for randomized hashing are averages over random choices or inputs.

Linked from 9 pages