Hash Table: From Basics to Advanced Operations

1. Introduction and Core Concepts

A hash table is one of the most fundamental and widely used data structures in computer science, providing an incredibly efficient way to store and retrieve data based on keys. At its core, a hash table implements an associative array abstraction — a structure that maps keys to values — and is the underlying mechanism behind dictionaries in Python, Maps in Java, objects in JavaScript, and hash maps in C++. Unlike arrays where you access elements by a numeric index, hash tables allow you to use any hashable object — strings, numbers, tuples, or custom objects — as a key to instantly locate its associated value.

The power of a hash table lies in its promise of average constant-time performance, or O(1), for insertions, deletions, and lookups. This efficiency makes it indispensable for problems that require frequent searching. Imagine building a spell checker that needs to verify millions of words, a web cache that must retrieve pages in milliseconds, or a database index that serves thousands of queries per second. In all these scenarios, scanning through a list or even a sorted array would be far too slow. A well-designed hash table solves this by transforming a key into an array index through a mathematical function, enabling direct access without scanning.

Conceptually, a hash table consists of three main components: an underlying array (often called buckets or slots), a hash function that converts keys into array indices, and a collision resolution strategy to handle cases where different keys map to the same index. Understanding how these three components interact is key to mastering the data structure. While the idea is simple — hash the key, go to that index, store or retrieve the value — the engineering details determine whether your hash table performs in constant time or degrades to linear time. The quality of the hash function, the load factor of the table, and the method for handling collisions all critically impact performance, memory usage, and correctness.

Why Hash Tables Matter

Hash tables matter because they bridge the gap between human-friendly keys and machine-friendly indices. Arrays are fast but require integer indices; linked lists are flexible but slow to search. Hash tables give you the best of both worlds: the flexibility to use meaningful keys like usernames, URLs, or product IDs, combined with the speed of array indexing. This is why virtually every high-level programming language provides a built-in hash table implementation as a primitive type.

From a theoretical perspective, hash tables demonstrate a classic space-time tradeoff. By allocating extra space for buckets and accepting some overhead for hash computation, we achieve dramatic speedups in time complexity. They also illustrate important concepts like randomization, amortized analysis, and the practical impact of average-case versus worst-case performance. For any software engineer, a deep understanding of hash tables is not just an academic exercise — it directly informs decisions about system design, performance optimization, and choosing the right tool for the job.

2. How It Works

The operation of a hash table can be broken down into a simple pipeline: key -> hash function -> index -&> bucket. When you insert a key-value pair, the hash function takes the key and computes a hash code, typically a large integer. This hash code is then compressed to fit the size of the underlying array, most commonly using the modulo operation: index = hash(key) % capacity. The value is then stored at that index. Retrieval follows the exact same path: hash the key again, compute the same index, and fetch the value stored there. If the hash function is deterministic and the table has not been resized, the same key will always map to the same index.

The hash function is the heart of the data structure. A good hash function must be deterministic (same key always yields same hash), efficient to compute, and uniformly distributed (spreading keys evenly across buckets to minimize collisions). For integers, a simple modulo may suffice. For strings, popular functions like djb2, FNV-1a, or MurmurHash iterate over characters and mix bits to produce a well-distributed output. In Python, every hashable object implements a __hash__ method, and the built-in hash() function delegates to it. Cryptographic hash functions like SHA-256 are overkill for hash tables because they are deliberately slow; non-cryptographic functions that are fast and have good avalanche properties are preferred.

Collisions are inevitable. By the pigeonhole principle, if you have more possible keys than buckets, two distinct keys must eventually hash to the same index. Even with fewer keys than buckets, the birthday paradox makes collisions surprisingly likely. Therefore, every hash table must implement a collision resolution strategy. The two dominant approaches are separate chaining and open addressing. In separate chaining, each bucket stores a linked list (or dynamic array) of all key-value pairs that hashed to that index. In open addressing, all entries are stored directly in the array itself, and when a collision occurs, the algorithm probes for the next available slot according to a probing sequence such as linear probing, quadratic probing, or double hashing.

Load Factor and Resizing

The load factor, defined as n / m where n is the number of entries and m is the number of buckets, is the most important metric for hash table health. As the load factor increases, collisions become more frequent and performance degrades. For separate chaining, a load factor of 1.0 means on average one element per bucket, but some buckets will have chains of length 2 or 3. For open addressing, performance collapses as the load factor approaches 1.0 because probing sequences become very long.

To maintain O(1) average performance, hash tables dynamically resize. When the load factor exceeds a threshold (typically 0.7 to 0.75 for open addressing, and 1.0 to 2.0 for chaining), the table allocates a new, larger array — usually double the size — and rehashes all existing entries into it. This rehashing is an O(n) operation, but because it happens infrequently, its cost is amortized to O(1) per insertion. Similarly, some implementations shrink the table when the load factor drops too low to save memory. Choosing when and how to resize is a critical optimization that balances memory efficiency against time efficiency.

3. Implementation

Implementing a hash table from scratch is an excellent way to understand its internals. Below are two canonical implementations in Python: one using separate chaining, which is simpler and more robust at high load factors, and one using open addressing with linear probing, which is more cache-friendly. Both implementations include dynamic resizing and handle the core dictionary operations.

The first implementation uses separate chaining with lists for buckets. It is the approach used by many language runtimes when simplicity and predictable worst-case behavior are desired. Notice how the _hash method encapsulates the hashing logic, and how put handles both updates and inserts by scanning the chain.

# Simple Hash Table with Separate Chaining
class HashTableChaining:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        # Use built-in hash and compress to capacity
        return hash(key) % self.capacity

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing
                return
        bucket.append((key, value))  # Insert new
        self.size += 1
        if self.size / self.capacity > 0.75:
            self._resize()

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

    def delete(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

    def _resize(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)

The second implementation uses open addressing with linear probing. Here, all keys and values are stored directly in parallel arrays. On collision, we simply move to the next index (idx + 1) % capacity until we find an empty slot. This method suffers from primary clustering, where consecutive filled slots form clusters that increase probe lengths, but it benefits from better cache locality since data is stored contiguously.

class LinearProbingHashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.keys = [None] * capacity
        self.values = [None] * capacity
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        idx = self._hash(key)
        # Probe until empty slot or same key
        while self.keys[idx] is not None and self.keys[idx] != key:
            idx = (idx + 1) % self.capacity
        if self.keys[idx] is None:
            self.size += 1
        self.keys[idx] = key
        self.values[idx] = value
        # Resize if load factor > 0.7
        if self.size / self.capacity > 0.7:
            self._resize()

    def get(self, key):
        idx = self._hash(key)
        start = idx
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
            if idx == start:
                break
        return None

    def _resize(self):
        old_keys = self.keys
        old_values = self.values
        self.capacity *= 2
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity
        self.size = 0
        for i in range(len(old_keys)):
            if old_keys[i] is not None:
                self.put(old_keys[i], old_values[i])

Dynamic resizing is crucial for maintaining performance. The following helper shows the logic for deciding when to grow or shrink, and a complete resize routine that rehashes every entry. Note that rehashing must recompute indices because capacity has changed, so hash % capacity will yield different results.

def _resize_chaining(self):
    old_keys = self.keys
    old_values = self.values
    self.capacity *= 2
    self.keys = [None] * self.capacity
    self.values = [None] * self.capacity
    self.size = 0
    for i in range(len(old_keys)):
        if old_keys[i] is not None:
            self.put(old_keys[i], old_values[i])

# Example: load factor check with < and >
def needs_resize(size, capacity):
    load = size / capacity
    if load < 0.25:
        return "shrink"
    elif load > 0.7:
        return "grow"
    else:
        return "ok"

Finally, in practice you will rarely implement your own hash table in Python because dict and set are highly optimized hash tables written in C. Understanding how to use them effectively — including techniques like frequency counting and memoization — is equally important.

from collections import defaultdict

# Frequency counting with hash table (dict)
def count_frequencies(nums):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    return freq

# Using hash table for caching / memoization
cache = {}

def fib(n):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

# Type-hinted example: Dict[str, int] requires escaping
from typing import Dict
word_counts: Dict[str, int] = {"apple": 3, "banana": 5}
print(count_frequencies([1, 2, 2, 3, 3, 3]))
print(fib(10))

4. Step-by-Step Example

Let us walk through a concrete example to make the abstract operations tangible. We will use a small hash table with capacity m = 5 and a simple hash function h(key) = hash(key) % 5. For clarity, assume we are hashing integer keys where hash(key) = key, so h(key) = key % 5. We will use separate chaining for collision resolution and insert the sequence of key-value pairs: (10, "A"), (22, "B"), (31, "C"), (4, "D"), (15, "E"), (28, "F").

Initially, all 5 buckets are empty lists: [ [], [], [], [], [] ]. Insert 10: h(10) = 10 % 5 = 0, so we place (10, "A") in bucket 0. Insert 22: h(22) = 2, bucket 2 gets (22, "B"). Insert 31: h(31) = 1, bucket 1 gets (31, "C"). Insert 4: h(4) = 4, bucket 4 gets (4, "D"). At this point the table is [ [(10,"A")], [(31,"C")], [(22,"B")], [], [(4,"D")] ] with load factor 4/5 = 0.8.

Next, insert 15: h(15) = 0, which collides with bucket 0 already containing (10, "A"). With separate chaining, we append to the chain: bucket 0 becomes [(10,"A"), (15,"E")]. The table is now [ [(10,"A"), (15,"E")], [(31,"C")], [(22,"B")], [], [(4,"D")] ]. Insert 28: h(28) = 3, bucket 3 gets (28,"F"). The final table is [ [(10,"A"), (15,"E")], [(31,"C")], [(22,"B")], [(28,"F")], [(4,"D")] ]. All insertions were O(1) on average, with one collision handled by chaining.

Search and Delete Walkthrough

Now consider searching for key 15. We compute h(15) = 0 and scan bucket 0's chain: first we compare 10 != 15, then 15 == 15, so we return "E". This required 2 comparisons in the chain. Searching for key 99: h(99) = 4, we scan bucket 4 which contains only (4,"D"), no match, so we return None. Deleting key 10: h(10)=0, we locate (10,"A") in bucket 0 and remove it, leaving bucket 0 as [(15,"E")]. If we were using open addressing with linear probing instead, the same insertions would have caused probing: 15 would have probed from 0 to 1 (occupied), to 2 (occupied), to 3 (empty) before insertion, illustrating how clustering increases probe length.

This example also shows why resizing matters. After 5 inserts, our load factor is 1.0, and bucket 0 already has a chain length of 2. If we continued inserting without resizing, chains would grow and search time would degrade from O(1) toward O(n). A real implementation would have resized to capacity 10 after exceeding a threshold of 0.75, rehashing all keys with the new modulo 10, which would redistribute keys like 10 (10%10=0) and 15 (15%10=5) into different buckets and shorten chains.

5. Complexity Analysis

The complexity of hash table operations is nuanced because it depends heavily on the hash function quality, load factor, and collision resolution method. In the ideal case where the hash function distributes keys uniformly and the load factor is kept low, all primary operations achieve constant time. However, in the pathological worst case where all keys collide into the same bucket, the structure degrades to a linked list.

For separate chaining, the average case analysis assumes simple uniform hashing, where each key is equally likely to hash to any bucket. The expected chain length is α = n/m (the load factor). An unsuccessful search must scan an entire chain of expected length α, while a successful search scans about 1 + α/2 on average. When α is bounded by a constant (e.g., α < 0.75 or α < 1), this is O(1). Insertion is O(1) for appending to the chain plus O(α) to check for duplicates. Deletion similarly requires finding the element first, so it is O(α).

For open addressing, the analysis is more complex because probe sequences depend on the table's fullness. With linear probing, the expected number of probes for an unsuccessful search is approximately 1 / (1 - α), which grows rapidly as α approaches 1. For α = 0.5, it is 2 probes; for α = 0.9, it is 10 probes; for α = 0.99, it is 100 probes. This is why open addressing tables must be kept at lower load factors (typically < 0.7) and why double hashing or quadratic probing is often preferred to reduce clustering.

Space complexity is O(n + m), where n is the number of entries and m is the bucket count. In practice, m is proportional to n due to resizing, so space is O(n). The overhead comes from empty buckets, pointers for chaining, and tombstones in open addressing. An important distinction is that worst-case O(n) time occurs only with a poor hash function or adversarial inputs that cause many collisions. With a universal hash family or cryptographic mixing, the probability of worst-case behavior can be made negligibly small, which is why hash tables are considered O(1) average time in all practical contexts.

Amortized Analysis of Resizing

Resizing is O(n) in the worst case, but amortized analysis shows that each insertion still costs O(1) on average. If we double capacity each time we resize, the total cost of all resizes after n insertions is n + n/2 + n/4 + ... < 2n, so the average cost per insertion is < 2. This geometric series argument is why doubling is preferred over incrementing by a fixed amount. Similarly, Python's dict grows by factors of 2x for small tables and ~1.5x for large tables to balance memory and time.

6. Variations and Optimizations

Basic hash tables have been refined into numerous variants optimized for different workloads. One of the most important optimizations is the choice of hash function. Python's hash for strings and bytes uses SipHash to defend against hash-flooding denial-of-service attacks, where an attacker crafts many keys that collide to degrade performance to O(n). For custom objects, implementing a good __hash__ that mixes fields and avoids trivial collisions (like returning a constant) is critical. Techniques like universal hashing, where the hash function is randomly chosen from a family at runtime, provide theoretical guarantees against adversarial inputs.

Robin Hood hashing is an elegant open addressing variant that reduces variance in probe lengths. When inserting, if the new key has probed farther than the key occupying the current slot, they swap — the richer key (with shorter probe distance) gives to the poorer key (with longer distance). This keeps the maximum probe length low and makes worst-case searches much faster, at the cost of slightly more complex insertion logic. Cuckoo hashing takes a different approach: it uses two hash functions and two tables, and on collision it kicks the existing key to its alternative location, potentially cascading. Cuckoo hashing guarantees O(1) worst-case lookup (at most 2 probes) and is excellent for read-heavy workloads.

Other notable variants include hopscotch hashing, which bounds probing within a neighborhood to improve cache performance, and extendible hashing and linear hashing, which are used in databases to handle hash tables that do not fit in memory and must be stored on disk. For concurrent environments, lock-free and open-addressed hash tables with atomic operations, or sharded hash tables where the table is divided into segments each with its own lock, enable high throughput for multi-threaded servers.

Perfect hashing is worth highlighting for static datasets where keys are known in advance. A perfect hash function maps each key to a unique bucket with no collisions, enabling true O(1) worst-case lookup with no collision resolution needed. Minimal perfect hashing goes further by using exactly n buckets for n keys. These are used in compiler keyword tables, routing tables, and embedded systems. Consistent hashing, by contrast, is optimized for distributed systems: it maps both keys and servers to a hash ring, so adding or removing a server only remaps a small fraction of keys, minimizing data movement.

7. Real-World Applications

Hash tables are ubiquitous in real-world software, often hidden behind higher-level abstractions. In web servers and browsers, hash tables power caches that store recently fetched resources. An HTTP cache might use the URL as a key and the response body as the value, allowing O(1) retrieval without re-fetching from the origin server. Similarly, in-memory caches like Redis and Memcached are essentially distributed hash tables that sit in front of databases to absorb read traffic. Session stores, where a session ID maps to user data, are another classic use case that demands fast lookups under high concurrency.

Databases rely heavily on hash tables for indexing and query execution. A hash index allows point queries (WHERE id = 123) to be answered in O(1) average time, complementing B-tree indexes that excel at range queries. During query execution, hash joins are one of the most efficient join algorithms: the database builds a hash table from the smaller table's join keys, then probes it with keys from the larger table, avoiding the O(n log n) sort required by merge joins. Hash-based aggregation (GROUP BY) and deduplication (DISTINCT) also use hash tables to count or filter groups in a single pass.

In networking, hash tables are central to high-speed packet processing. Routers use hash tables to implement forwarding tables that map destination IP prefixes to next hops, and to track flow state for NAT and firewalls where a 5-tuple (source IP, dest IP, source port, dest port, protocol) is the key. Load balancers use consistent hashing to assign requests to backend servers while minimizing reshuffling when servers are added or removed. Even the internet's Domain Name System (DNS) resolvers cache name-to-IP mappings in hash tables to answer repeated queries instantly.

Additional Domains

Beyond infrastructure, hash tables appear in compilers and interpreters for symbol tables that map variable names to type information and memory locations. In cryptography and blockchain, hash tables (and their cousin, the Merkle tree) are used to store and verify transactions. In bioinformatics, k-mer counting for genome assembly uses hash tables to count occurrences of short DNA substrings. In gaming, transposition tables cache previously evaluated board positions to speed up AI search. The common thread is any problem requiring fast associative lookup, deduplication, or counting benefits from a hash table.

8. Comparison with Alternatives

Choosing a data structure requires understanding trade-offs. Hash tables excel at point lookups but are not always the best choice. If you need ordered traversal, range queries, or worst-case guarantees, other structures may be superior. The table below compares hash tables with the most common alternatives: balanced binary search trees (like AVL or Red-Black trees), arrays, linked lists, and tries.

Balanced BSTs, such as those behind C++ std::map or Java TreeMap, maintain keys in sorted order and guarantee O(log n) worst-case time for all operations. They support ordered operations like finding the predecessor/successor, range scans, and in-order traversal, which hash tables cannot do efficiently. However, they have higher constant factors due to pointer chasing and rebalancing, and they use more memory for tree pointers. Arrays provide O(1) access by index and excellent cache locality but require integer indices and are expensive to search (O(n) unsorted, O(log n) sorted via binary search) and to insert/delete in the middle (O(n) shifts).

Tries (prefix trees) are specialized for string keys, offering O(L) lookup where L is key length, and they support prefix searches and autocomplete naturally. Bloom filters, a probabilistic alternative, can test membership in O(1) time with very little space but allow false positives and cannot retrieve values. Understanding these trade-offs helps you decide: use a hash table when you need fast average-case point operations and do not need ordering; use a BST when ordering matters; use a trie for string prefixes; use a Bloom filter when space is extremely constrained and false positives are acceptable.

In Python specifically, dict is a hash table, while the bisect module plus list simulates a sorted array, and there is no built-in balanced BST — you would use heapq or sortedcontainers. For most application code, dict and set (which is a hash table with only keys) are the default choices for associative storage precisely because their average O(1) performance is hard to beat for general-purpose use.

9. Common Mistakes and Best Practices

Even experienced developers make subtle mistakes with hash tables that lead to bugs or performance cliffs. The most common error is using mutable objects as keys. In Python, lists and dictionaries are unhashable precisely for this reason: if you mutate a key after insertion, its hash changes and it becomes unfindable in its original bucket, effectively leaking memory and causing lookup failures. Always use immutable, hashable types like strings, numbers, tuples of immutables, or custom objects with stable __hash__ and __eq__ implementations. If you define __eq__, you must also define __hash__ to be consistent: objects that compare equal must have equal hashes.

Another frequent pitfall is a poor hash function that does not distribute well. Returning a constant hash, or hashing only part of the key (e.g., hashing a person object by first name alone), creates many collisions and degrades performance to O(n). Similarly, forgetting to handle collisions at all — assuming hash % capacity is unique — leads to silent data loss where new inserts overwrite old ones. Always implement proper collision resolution and test with adversarial data. In security-sensitive contexts, use a randomized or SipHash-like function to prevent hash-flooding attacks.

Performance mistakes include ignoring load factor and never resizing, or resizing too eagerly. A table that never grows will have long chains and slow lookups; one that grows by a fixed increment (e.g., +10 buckets) will resize too often and waste time rehashing. Doubling strategy with amortized analysis is the standard. Also, be careful with open addressing deletion: you cannot simply mark a slot as None, because that breaks probe chains for keys that collided beyond it. Instead, use a tombstone marker (e.g., a special sentinel) that indicates deleted but still probed, and periodically rehash to clean tombstones.

Best Practices Checklist

• Keep load factor bounded: resize at 0.7 for open addressing, 0.75-1.0 for chaining.
• Choose capacity as a prime number or power of two depending on hash function; Python uses power of two with a perturbation scheme.
• Implement __hash__ and __eq__ consistently; make keys immutable.
• For custom objects, combine field hashes with tuple hashing: return hash((self.field1, self.field2)).
• Prefer separate chaining for simplicity and high load tolerance; prefer open addressing for cache performance and memory efficiency.
• Use Python's built-in dict/set for production code — they are highly optimized in C and handle resizing, probing, and hash randomization for you.
• Profile before optimizing: measure collisions and probe lengths if you suspect degradation.
• For concurrent access, use sharding or concurrent hash map libraries rather than a single lock around the entire table.

Finally, remember that hash tables are unordered. Do not rely on iteration order for correctness unless using an ordered variant like Python 3.7+ dict (which preserves insertion order as an implementation detail) or collections.OrderedDict. If you need sorted order, explicitly sort keys or use a BST.

10. Interview Questions

Hash tables are a favorite topic in technical interviews because they test understanding of fundamentals, trade-offs, and practical problem-solving. Below are common questions with guidance on what interviewers look for and how to approach them.

Q1: Design a hash table from scratch without using built-in dict. How would you handle collisions and resizing? This question tests your ability to implement core operations. Start by describing the array of buckets, hash function (hash % capacity), and choose separate chaining for simplicity. Explain put, get, delete logic, and emphasize load factor monitoring and doubling resize with rehashing. Mention time complexity O(1) average, O(n) worst, and discuss why you would use a prime capacity or power of two. Bonus points for discussing open addressing alternatives and tombstones for deletion. Be ready to code a minimal version on the whiteboard and analyze amortized cost.

Q2: Given an array of integers, find if there are two numbers that sum to a target (Two Sum). What is the optimal solution? The naive O(n²) double loop is too slow. The optimal O(n) solution uses a hash table to store seen numbers. For each num, compute complement = target - num, check if complement is in the hash table in O(1), if yes return indices, otherwise store num -> index. This demonstrates the classic hash table pattern of trading space for time to achieve linear time. Follow-ups include handling duplicates, returning all pairs, or solving Three Sum where sorting plus two pointers may be better. Discuss space O(n) and why hashing beats sorting here.

Q3: How would you detect duplicates or find the first non-repeating character in a string? Both problems are solved elegantly with hash tables for frequency counting. For duplicates, insert each element into a set (a hash table with no values) and check for existence before insertion — O(n) time, O(n) space. For first non-repeating character, do two passes: first pass builds a frequency dict (char -> count), second pass scans the string in order and returns the first char with count 1. This highlights that hash tables are unordered, so you need the original order for the second scan. Variants include finding the most frequent element or grouping anagrams by hashing sorted strings.

Q4: What is the difference between a hash table and a hash map? Explain hash collisions and how to minimize them. Terminology varies by language, but generally they refer to the same structure. Explain collisions via pigeonhole principle and birthday paradox, then describe separate chaining vs open addressing with pros/cons. To minimize collisions, discuss good hash functions (uniform distribution, avalanche effect), keeping load factor low, using universal hashing, and choosing appropriate capacity (prime vs power of two). Mention that Python randomizes hash seeds per process to prevent collision attacks. This question checks depth of understanding beyond just using dict.

Q5: Implement an LRU (Least Recently Used) Cache with O(1) get and put. What data structures would you use? This is a classic hard interview problem that combines a hash table with a doubly linked list. The hash table maps keys to nodes in the linked list for O(1) lookup, while the linked list maintains recency order (most recent at head, least at tail). On get, move the node to head; on put, insert at head and evict tail if over capacity. In Python, you can mention that collections.OrderedDict or functools.lru_cache implements this, but the interview expects you to design the hybrid structure and explain why neither a hash table alone (no ordering) nor a list alone (O(n) search) suffices. Analyze O(1) time and O(capacity) space, and discuss thread safety and expiration extensions.