Skip to main content
Definition Website Computer and Technology

Hash Table

Subject: Computer and Technology noun /ˈhæʃ ˌteɪ.bəl/ 1 definition

  1. Definition (noun)

    Entry #7 · Updated

    A Hash Table is an associative data structure that stores key-value pairs in an underlying array by passing each key through a deterministic hash function to compute a bucket index. By mapping keys directly to storage slots, it provides constant-time, O(1) average-case lookup, insertion, and deletion without scanning every element. Because distinct keys can hash to the same index (a hash collision), implementations rely on collision-resolution mechanisms and periodic resizing to maintain efficiency, trading sorted key order for fast direct access.

    Common Types

    • Separate Chaining Hash Table: Stores colliding key-value pairs in a secondary structure, such as a linked list or small dynamic array, attached to each bucket index.

    • Open Addressing Hash Table: Keeps all entries directly inside the main array and resolves collisions by probing alternative slots using sequences like linear probing or double hashing.

    • Cuckoo Hash Table: Uses two or more hash functions and relocates existing keys between alternate buckets on collision to guarantee worst-case O(1) lookup time.

    • Concurrent Hash Table: Coordinates access with fine-grained bucket locks or lock-free atomic operations so multiple threads can read and write entries safely in parallel.

    Example

    An API gateway tracks 250,000 active user sessions in an in-memory hash table keyed by each session's 128-bit token string. When an incoming request presents token tok_9f8c3a1b, the gateway hashes the string directly to its array bucket and retrieves the user's permissions in a single step instead of scanning all 250,000 records.