Skip to content
Data Structures & Algorithms

Hash Tables interview questions and answers

39 questions, 11 with code. About 3 h 21 min to read them all.

By TestLab · Updated

Plan for an interview
39 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a hash table and how does it work?

A hash table is a data structure that maps keys to values using a hash function. It achieves constant-time operations on average by placing entries in buckets based on computed hash codes rather than searching linearly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Internal Structure

A hash table contains three main components:

  • Hash function: Converts a key into an integer hash code.

  • Buckets or slots: Fixed-size storage locations holding entries.

  • Load factor: The ratio of stored entries to available buckets.

A typical lookup follows this process:

  1. Compute the key’s hash code.

  2. Convert that code into a bucket index.

  3. Locate the bucket.

  4. Compare the stored key with the requested key to confirm a match.

  5. Resolve any collision if the bucket contains multiple candidates.

For example, a simple hash function might use hash(key) % bucket_count. Python’s built-in hash() is randomized for supported types such as str and bytes, helping prevent predictable collision patterns.

Hashable Keys

Hash-table keys must be hashable, meaning they have a hash value and can be compared reliably with equivalent keys.

  • str, int, float, tuple, and frozenset are commonly hashable.

  • list and dict are unhashable because they are mutable containers.

  • A tuple is hashable only when all its elements are hashable.

# Valid keys
employee_id = 42
coordinates = (10, 20)

# Invalid keys
names = ["Ada", "Grace"]  # list is unhashable
settings = {"role": "admin"}  # dict is unhashable

Built-in hashable types are effectively immutable because changing a key after insertion could change where it should be stored.

Collision Handling

Different keys can produce the same hash code, creating a collision. Common strategies include:

Strategy How It Works Main Trade-off
Separate chaining Each bucket stores a collection of entries, often a list Simple to implement; pointer overhead and potentially long lists
Linear probing Searches consecutive slots after a collision Good cache locality; clustering can increase probe counts
Quadratic probing Searches using squared probe offsets Reduces clustering; may not inspect every slot
Double hashing Uses a second hash function to determine the step size Fewer clustering patterns; more computation

A from-scratch implementation often uses separate chaining, represented as a list of lists. CPython 3.12’s dict instead uses a compact open-addressing table with probing. A Python set is also implemented as a hash table, but it stores keys rather than key-value pairs.

Example Walkthrough

Suppose a table has four buckets, and the hash function returns hash(key) % 4:

Operation Hash Index Result
Insert "cat" 1 "cat" is placed in bucket 1
Insert "dog" 2 "dog" is placed in bucket 2
Insert "bird" 1 It shares bucket 1 with "cat"
Look up "bird" 1 Search bucket 1 and confirm the exact key

A lookup must compare keys after finding a bucket because another key may share the same index.

Resizing and Load Factor

The load factor indicates how full the table is:

load factor = number of entries / number of buckets

As entries increase, collisions become more likely. A table can therefore resize by allocating more buckets and rehashing every entry into its new position.

  • Trigger: A common threshold is a load factor around 0.66 or 0.75, depending on the implementation.

  • Rehashing: Every existing key is hashed again and placed in the new table.

  • Cost: A single resize takes O(n) time.

  • Amortized insertion: O(1) across a sequence of insertions because the total rehashing cost is spread across many operations.

Complexity

The following bounds assume fixed-size keys and constant-time key comparison:

Operation Best Case Average Case Worst Case
Lookup O(1) O(1) O(n)
Insert O(1) O(1) amortized O(n)
Delete O(1) O(1) O(n)
  • Best case: The desired bucket or slot is found immediately.

  • Average case: Uniform hashing and a controlled load factor keep probes or chain lengths small.

  • Worst case: Many keys collide in one bucket or probing becomes expensive.

  • Space: O(n) for n stored entries, excluding the input; no recursion stack is used.

Python 3.12 guarantees that dict preserves insertion order, but it does not guarantee that iteration order follows hash-code order.

Interview Tips

  • Distinguish average O(1) from amortized O(1): average concerns hashing behavior, while amortized concerns occasional resizing costs.

  • Explain how duplicate keys are handled: they normally update the existing value instead of creating another entry.

  • Mention that deleting from a chained table simply removes the entry from its chain, while deleting from an open-addressed table needs tombstones or backward-shift deletion.

  • Common follow-up questions cover load factors, rehashing, collision attacks, thread safety, and implementing a hash map with separate chaining.

2

What is hashing in data structures?

Hashing is a technique that maps data of arbitrary size to fixed-size values using a hash function, enabling O(1) average-time lookups, insertions, and deletions in hash tables. The hash function computes an index into an array of buckets where the value is stored, and collisions (different keys mapping to the same bucket) are resolved through chaining or open addressing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hashing Works

  • Hash function: Takes a key and returns an integer hash code. A good hash function distributes keys uniformly across buckets to minimize collisions.

  • Buckets (slots): An array where each entry holds a key-value pair (or a pointer to a chain of entries). The bucket index is typically hash(key) % capacity.

  • Load factor: Ratio of stored entries to bucket count (n / capacity). When it exceeds a threshold (e.g., 0.75), the table resizes.

  • Resizing (rehashing): Allocate a larger bucket array (usually 2×), then re-insert every entry using the new capacity. This is O(n) but happens rarely, giving amortized O(1) insertion.

Collision Resolution

Method Description Pros Cons
Separate chaining Each bucket holds a linked list (or dynamic array) of entries that hashed to the same index. Simple, handles high load factors, easy to implement. Extra memory for pointers, cache misses from pointer chasing.
Open addressing All entries stored directly in the bucket array; on collision, probe for the next free slot. Better cache locality, no pointer overhead. Clustering degrades performance, requires tombstones for deletion, load factor must stay < 1.
Linear probing Check index + 1, index + 2, … Simple, good cache performance. Primary clustering (contiguous blocks of occupied slots).
Quadratic probing Check index + 1², index + 2², … Reduces primary clustering. Secondary clustering (keys with same initial index follow same probe sequence).
Double hashing Probe step = hash2(key) where hash2 is a second hash function. Minimizes clustering. More computation, hash2 must never return 0.

Key Requirements

  • Deterministic: Same key always produces same hash code during a program run.

  • Uniform distribution: Keys spread evenly across buckets.

  • Fast computation: Hash function should be O(1) or O(k) where k is key length.

  • Equality consistency: If a == b, then hash(a) == hash(b). In Python, mutable types (lists, dicts, sets) are unhashable because their contents can change, breaking this invariant. Immutable types (int, str, tuple of immutables, frozenset) are hashable.

Time and Space Complexity

Operation Average Worst Case Reason
Lookup O(1) O(n) All keys collide into one bucket (chaining) or probe sequence scans entire table (open addressing).
Insert O(1) amortized O(n) Same as lookup; resizing adds O(n) every n/α insertions.
Delete O(1) O(n) Same as lookup; open addressing needs tombstone.
Space O(n) O(n) Bucket array + entries. Load factor α = n/capacity kept constant.

Python-Specific Details

  • dict and set use open addressing with a variant of linear probing and a perturbation scheme to reduce clustering.

  • Insertion order is preserved (guaranteed since Python 3.7, implementation detail in 3.6).

  • hash() returns a 64-bit integer (salted per process for security since 3.3).

  • Custom classes are hashable by default (based on id()), but if you define __eq__, you must also define __hash__ to remain usable as a dict key.

Common Pitfalls

  • Using mutable objects as keys: Lists, dicts, and sets cannot be dict keys or set elements. Convert to tuple or frozenset first.

  • Poor hash functions: A hash that returns a constant or clusters keys (e.g., hash(x) = x % 10 for multiples of 10) degrades to O(n).

  • Forgetting __hash__ when overriding __eq__: In Python, defining __eq__ without __hash__ sets __hash__ = None, making instances unhashable.

  • Assuming iteration order: Only guaranteed in Python 3.7+ for dict; never rely on order in other languages’ hash tables.

  • Integer overflow in other languages: In C++/Java, hash codes are 32-bit; combine fields carefully to avoid overflow and poor distribution.

  • Follow-up questions interviewers ask: “How would you implement a hash map from scratch?” “What happens during resizing?” “Why must equal objects have equal hashes?” “How does Python’s dict differ from Java’s HashMap?” “Design an LRU cache using a hash map and doubly linked list.”

3

How does hashing differ from a hash table?

Hashing is the process of transforming input into a fixed-size value through a hash function. A hash table is a data structure that uses hashing to store and retrieve keyed values efficiently while handling hash collisions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

Aspect Hashing Hash table
Purpose Produces a hash value from input Stores and retrieves key-value pairs
Output Usually one integer or fixed-size value A location or collection of entries organized by hash value
Collision handling Not inherently handled Required because different keys may produce the same hash
Data structure Not a data structure Implements a map or dictionary abstraction
Typical example hash("cat") A dictionary containing "cat" → 4

Hashing also has uses outside hash tables, including checksums, content addressing, caches, and cryptographic password protection. A hash table is specifically the storage structure built around hash values.

Hash Table Internals

A hash table generally maintains an array of buckets or slots and performs the following steps for an operation:

  1. Apply the hash function to the key.

  2. Convert the result into a bucket index.

  3. Search that bucket using an equality check.

  4. Insert, update, or remove the matching entry.

The hash value determines the initial location, but it does not identify the key uniquely. Two different keys can have the same hash value, so the implementation must compare the stored keys with the requested key.

The load factor is commonly defined as:

load factor = number of stored entries / number of buckets

A high load factor means many entries compete for the same buckets, increasing collision handling costs. A low load factor uses more memory but usually provides faster operations.

Collision Handling

Strategy How collisions are handled Characteristics
Separate chaining Each bucket stores a collection of entries Simple to implement; chains can become long
Linear probing Check the next slot, then the next, until an empty slot is found Cache-friendly but vulnerable to clustering
Quadratic probing Check slots using a quadratic offset sequence Reduces clustering compared with linear probing
Double hashing Use a second hash function to determine the probe sequence More evenly distributes keys

In separate chaining, each bucket can be a list of key-value pairs. In open addressing, all entries remain in the table’s slots, and probing finds another available location.

Python 3.12 dictionaries use an internal form of open addressing, while sets use a hash-table structure to store keys. Dictionary insertion order has been guaranteed since Python 3.7.

Resizing and Rehashing

When the number of entries exceeds the implementation’s load-factor threshold, the table may allocate a larger bucket array and rehash every existing key using the new bucket count.

  • Rehashing an entire table of n entries takes O(n) time.

  • Individual insertions can therefore trigger an expensive resize.

  • Across m insertions, the total resize cost is amortized, making each insertion amortized O(1) under the usual assumptions.

  • Resizing temporarily requires additional memory proportional to the table size.

The exact threshold and growth factor depend on the implementation and should not be assumed to be the same across languages.

Complexity

The following bounds assume constant-time hashing and key equality checks.

Operation Best Average Worst Reason
Lookup O(1) O(1) O(n) Best case finds the entry immediately; worst case examines many colliding entries
Insert O(1) O(1) O(n) Worst case includes collision searching and possible rehashing
Delete O(1) O(1) O(n) Worst case requires searching a collision chain or probe sequence
Resize O(n) O(n) O(n) Every stored key must be placed into the new table

Hashing a variable-length key of length k additionally takes O(k) time to process all its characters. Hash tables use O(n) additional space for buckets and entries, excluding the input; no recursion stack is involved.

Common Pitfalls and Interview Tips

  • Equal hashes do not imply equal keys. A hash table must still compare keys with equality.

  • Keys must be hashable. Python lists are mutable and therefore cannot be dictionary keys; tuples can be keys when all their elements are hashable.

  • Duplicate dictionary keys update the existing value. The key’s original insertion position is retained. Duplicate values in a set are ignored.

  • Negative and zero keys are valid. Their hash values are still mapped to valid bucket indexes.

  • Empty and single-entry tables have no collision-management issue and operations remain constant time.

  • Do not confuse ordinary hashing with cryptographic hashing. Password storage requires a slow, salted algorithm such as Argon2 or bcrypt, not a general-purpose hash table.

  • A common follow-up asks why Python dictionaries guarantee insertion order but older versions did not. The relevant change is the implementation of compact ordered entries, with the language-level ordering guarantee introduced in Python 3.7.

4

What is a simple example of a hash function?

A hash function converts input data into a fixed-size value, usually an integer, so it can be used efficiently as a key or index. A simple example is a polynomial rolling hash that transforms a string into a bucket index in a hash table.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A typical string hash function processes characters sequentially:

  1. Start with an initial hash value.

  2. Convert each character to its numeric code using ord().

  3. Combine the current hash with that value.

  4. Apply modulo to keep the result within the hash table’s size.

The recurrence is:

hash_value = (hash_value * 31 + ord(character)) % table_size

For "cat" with table_size = 101:

  1. Start with 0.

  2. Process 'c': (0 * 31 + 99) % 101 = 99.

  3. Process 'a': (99 * 31 + 97) % 101 = 35.

  4. Process 't': (35 * 31 + 116) % 101 = 90.

The resulting bucket index is therefore 90.

Buckets and Collisions

A hash table stores values in an array of buckets. The hash function determines the bucket in which a key should be stored.

Different keys can produce the same hash. This is a collision and is unavoidable when a finite hash range must represent a larger set of possible keys.

Method How collisions are handled Main trade-off
Separate chaining Store colliding entries in a collection attached to the same bucket Usually simple, but long chains increase lookup cost
Linear probing Check the next bucket sequentially Cache-friendly, but clustering can increase probes
Quadratic probing Check buckets using a quadratic sequence Reduces some clustering, but requires careful probe design
Double hashing Use a second hash function to determine the probing step Distributes probes more widely, but needs another hash function

Python dictionaries use open addressing, while Python sets use a hash table to store their keys. Dictionary iteration order is guaranteed to be insertion order since Python 3.7.

Load Factor and Resizing

The load factor is approximately:

number of stored entries / number of buckets

When the load factor becomes too high, the table resizes to reduce collisions. During resizing, existing entries are rehashed and placed into the new table.

  • Resizing: O(n) for one resize because up to n entries must be rehashed.

  • Amortized insertion: O(1) across a sequence of insertions when the table grows geometrically and maintains a bounded load factor.

The exact resize threshold and growth policy are implementation-specific and should not be assumed when implementing a custom table.

Complexity

For a string of length k:

  • Hash computation time: O(k), because every character is processed once.

  • Hash computation auxiliary space: O(1), excluding the input string and with no recursion stack.

  • Lookup, insert, and delete time: best case O(1), average expected case O(1), and worst case O(n), assuming hash computation is treated as constant-time.

  • Hash table space: O(n) additional table storage for n stored entries, excluding the input string and separately stored key or value payloads.

Common Pitfalls

  • Empty input: Under this recurrence, an empty string produces 0.

  • One-character input: The result is that character’s code modulo the table size.

  • Duplicates: Identical strings intentionally produce identical hashes.

  • Invalid table size: The modulus must be positive; an implementation should reject a non-positive value.

  • Poor distribution: A small table or unsuitable base can create many collisions.

  • Security: Python’s built-in string hash() is randomized by default between processes, although PYTHONHASHSEED can disable or fix the seed. Do not use it for persistent checksums or security-sensitive purposes.

  • Incorrect bucket access: The hash value must be within the bucket array, which the modulo operation ensures when the table size is positive.

  • Unrelated edge cases: Sorting, already sorted input, graph connectivity, and cycles do not apply to hashing a single string.

5

How do hash tables work internally in Java, Python, and C++?

A hash table stores key-value pairs by applying a hash function to each key and using the resulting index to select a bucket. Hash functions distribute keys efficiently, but collisions are inevitable, so implementations also use collision handling and periodic resizing.

Read full answer

Applies toJava 21, CPython 3.12, and C++20 (examples in Python 3.12)

Core Mechanism

Most hash tables use an array of buckets. For a table with capacity m, a typical index calculation is:

index = hash(key) % m

  • Hash function: Converts a key into an integer hash code. Hashing a key of length L may cost O(L), so constant-time complexity assumes fixed-size or constant-cost keys.

  • Buckets: Slots in the hash table’s backing array.

  • Load factor: α = number_of_entries / bucket_count. A higher load factor means more collisions but less memory.

  • Resizing: When the load factor exceeds an implementation-specific threshold, the table allocates a larger bucket array.

  • Rehashing: Every entry’s bucket index is recomputed in the new array because bucket indexes depend on capacity. Implementations such as Java and CPython can reuse a cached hash code rather than call the key’s hash function again.

For example, suppose three keys map to buckets 1, 1, and 2 in a four-bucket table. The load factor is 3/4. When another entry is added, the table might resize to eight buckets and reindex every key.

Collision Handling

Two common strategies are:

  • Separate chaining: Each bucket contains a list or linked list of entries. Colliding entries are appended to the same bucket.

  • Open addressing: All entries live directly in the bucket array. A collision causes the implementation to search another position using:

  • Linear probing: Check the next consecutive bucket.

  • Quadratic probing: Check positions separated by increasing squares.

  • Double hashing: Use a second hash function to determine the probe step.

Open addressing generally requires a lower load factor because longer probe sequences become more likely. Separate chaining tolerates higher load factors but uses additional memory for bucket structures.

Language Differences

Implementation Internal strategy Notable behavior
Java 21 HashMap Separate chaining with linked-list buckets and treeified bins for suitable large buckets Iteration order is unspecified
CPython 3.12 dict Open addressing using a compact entry layout and perturb-assisted probing Preserves insertion order; guaranteed since Python 3.7
CPython 3.12 set A hash table storing keys without associated values Iteration order is unspecified
C++20 std::unordered_map Implementation-defined; common implementations use separate chaining Iteration order is unspecified

Python keys must be hashable. Integers and strings are immutable and hashable. A tuple is also immutable and hashable when all its elements are hashable because its hash is derived from those elements; a tuple containing a list is unhashable. Lists cannot be keys because they are mutable and unhashable.

Complexity

Assuming a well-distributed hash function and constant-cost hashing:

Operation Best Average Worst case
Lookup O(1) O(1) O(n)
Insert O(1) O(1) O(n)
Delete O(1) O(1) O(n)
  • Best case: The first examined location contains the key or is available.

  • Average case: Buckets or probe sequences distribute entries evenly.

  • Worst case: Many keys collide or follow the same probe sequence, requiring O(n) examination.

  • Amortized insertion: O(1), because an occasional O(n) resize is spread across multiple insertions.

  • Space: O(n) for entries and buckets, excluding the input. The recursion stack is O(1) because the implementation is iterative.

Code Example

This Python 3.12 implementation demonstrates separate chaining, duplicate-key updates, deletion, load-factor tracking, and resizing:

from collections.abc import Hashable


class HashTable:
    """A hash table using separate chaining and automatic resizing."""

    def __init__(self, capacity: int = 8) -> None:
        if capacity < 1:
            raise ValueError("capacity must be positive")

        self._capacity = capacity
        self._buckets: list[list[tuple[Hashable, object]]] = [
            [] for _ in range(capacity)
        ]
        self._size = 0

    def _index(self, key: Hashable) -> int:
        return hash(key) % self._capacity

    def put(self, key: Hashable, value: object) -> None:
        bucket = self._buckets[self._index(key)]

        for position, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[position] = (key, value)
                return

        bucket.append((key, value))
        self._size += 1

        if self._size > self._capacity * 0.75:
            self._resize(self._capacity * 2)

    def get(self, key: Hashable) -> object:
        for existing_key, value in self._buckets[self._index(key)]:
            if existing_key == key:
                return value

        raise KeyError(key)

    def delete(self, key: Hashable) -> None:
        bucket = self._buckets[self._index(key)]

        for position, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[position] = bucket[-1]
                bucket.pop()
                self._size -= 1
                return

        raise KeyError(key)

    def _resize(self, new_capacity: int) -> None:
        old_buckets = self._buckets
        self._capacity = new_capacity
        self._buckets = [[] for _ in range(new_capacity)]
        self._size = 0

        for bucket in old_buckets:
            for key, value in bucket:
                new_bucket = self._buckets[self._index(key)]
                new_bucket.append((key, value))
                self._size += 1


table = HashTable(capacity=4)
table.put("one", 1)
table.put("two", 2)
table.put("three", 3)
table.put("four", 4)  # Triggers resizing.
table.put(-7, "negative")

print(table.get(-7))  # Expected output: negative

Common Pitfalls

  • Treating O(1) as guaranteed: adversarial or poorly distributed hashes can cause O(n) operations.

  • Forgetting that resizing requires recomputing every key’s bucket position.

  • Using mutable or unhashable keys.

  • Confusing duplicate keys with hash collisions: duplicates update the existing value, while colliding keys remain separate entries.

  • Assuming Python’s set or C++’s unordered_map preserves insertion order. Python’s dict does guarantee insertion-ordered iteration.

  • Forgetting edge cases: an empty table raises KeyError for missing reads, one-element tables work normally, duplicates update values, and negative integer keys are valid.

6

What are hash collisions in hash tables?

A hash collision occurs when two different keys produce the same hash-table bucket index. The table must resolve this collision while still distinguishing the keys using an equality check.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Collisions Occur

  • A hash function converts each key into a value, and that value determines the bucket or slot used.

  • Different keys can receive the same hash value, even though they are not equal.

  • Collisions are unavoidable when more keys can exist than the table has slots, because multiple keys must map to the same location.

  • A hash collision is not the same as equal keys: "AB" and "BA" are unequal, but a weak hash function may map both to the same bucket.

Python dictionaries require hashable keys. Lists cannot be dictionary keys because they are mutable and unhashable. Tuples can be keys when all their elements are hashable.

Collision Handling Strategies

Strategy How collisions are stored Characteristics
Separate chaining Each bucket contains a list of entries Simple to implement; can tolerate a higher load factor
Linear probing Check the next slot, then the next, until an empty slot is found Cache-friendly but vulnerable to clustering
Quadratic probing Check slots using a quadratic sequence Reduces some clustering but may leave gaps
Double hashing Use a second hash function to determine the probe sequence Usually distributes keys more evenly

Python 3.12 dictionaries use an internal open-addressing design rather than separate chaining. They also preserve insertion order, a guarantee provided since Python 3.7.

Load Factor and Resizing

The load factor is the ratio:

number of stored entries / number of table slots

A load factor that is too high increases collisions and lookup time. When a table exceeds its configured threshold, it:

  1. Allocates a larger table.

  2. Recomputes each key’s bucket index.

  3. Moves the entries into the new table.

This process is called rehashing. A resize takes O(n) time, but resizes are infrequent enough that insertion remains amortized O(1) across a sequence of insertions.

Complexity

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) amortized O(1) O(n)
Delete O(1) O(1) O(n)
  • Average case: the hash function distributes keys evenly, so only a constant number of entries or slots must be examined.

  • Worst case: every key hashes to the same bucket or probe sequence, requiring O(n) examination.

  • Space: O(n) for the table and stored entries. A single operation uses O(1) auxiliary space, with no recursion stack. The original input is not counted separately from the table’s retained copies.

Common Pitfalls

  • Skipping the equality check: Equal hashes do not imply equal keys.

  • Using mutable keys: Changing a key’s hash-related state while it is stored can make it unreachable.

  • Ignoring collisions: A production implementation must provide a complete collision-resolution strategy.

  • Forgetting to rehash: Entries must be placed according to the new capacity after resizing.

  • Assuming O(1) always holds: Constant-time operations are averages; poor hash distribution can cause O(n) worst-case behavior.

  • Using a custom hash in production: Python’s built-in dict provides randomized string hashing, optimized probing, and substantially better collision resistance.

7

Which hash table collision handling techniques exist?

Hash tables resolve collisions with separate chaining or open addressing. Common open-addressing variants include linear probing, quadratic probing, and double hashing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hash Tables Handle Collisions

A hash function converts a key into a numeric value, which is usually reduced with modulo to select one of the table’s buckets. Two different keys may map to the same bucket, producing a collision.

A collision is not necessarily an error. The hash table must choose a strategy for locating and storing both keys without losing either one.

Common Collision Handling Techniques

Technique How it works Advantages Limitations
Separate chaining Each bucket contains a collection, commonly a list, of keys with the same hash index. Simple to implement; deletion is straightforward; supports different key types in one table. Uses extra memory and may have poor cache locality if chains grow.
Linear probing If a slot is occupied, check consecutive slots until an empty one is found. Fast and cache-friendly; commonly used by compact implementations. Causes primary clustering, where occupied regions expand and increase probe lengths.
Quadratic probing Probe offsets such as 0, 1², 2², and 3². Reduces primary clustering compared with linear probing. Can cause secondary clustering and requires careful table sizing and termination rules.
Double hashing Use a second hash function to determine the probe step. Distributes keys more evenly and limits clustering. Requires another hash function and slightly more computation.
Robin Hood hashing During probing, move a key to another slot when doing so reduces its probe distance. Keeps probe sequences relatively short and improves lookup performance. More complicated to implement, move, and resize.
Cuckoo hashing Store each key in one of two candidate locations and relocate conflicting keys when necessary. Can provide good lookup performance with controlled load factors. Insertion may require repeated relocation and can fail if no valid arrangement exists.

Small Collision Example

Suppose the table has five slots, and hash(key) % 5 produces the following results:

  1. Inserting 10 maps to slot 0, which is empty.

  2. Inserting 15 also maps to slot 0, causing a collision.

  3. With separate chaining, slot 0 becomes [10, 15].

  4. With linear probing, 10 remains in slot 0, and 15 is placed in slot 1.

  5. With double hashing, the second hash value could make 15 jump directly to another free slot instead of scanning adjacent slots.

Load Factor and Resizing

The load factor is the ratio:

load factor = number of stored keys / number of buckets

A high load factor means more collisions and longer probe sequences. Dynamic hash tables therefore resize when the load factor exceeds a threshold.

During resizing, the table allocates a larger bucket array and rehashes every key into its new location. Rehashing the entire table takes O(n) time, but spreading that cost across a sequence of insertions makes insertion amortized O(1), assuming constant-time hashing and conventional geometric growth.

Complexity and Python Behavior

Operation Average case Worst case Reason
Lookup O(1) O(n) A good hash usually finds the target quickly, but every key may be in one bucket or probe sequence.
Insert O(1) amortized O(n) Resizing is spread across insertions; collisions can still place the key after many probes.
Delete O(1) average O(n) The key is normally found quickly, but collision handling may require scanning a chain or probe sequence.

For separate chaining, average lookup and insertion are often written as O(1 + α), where α is the load factor; when α is bounded by a constant, this is O(1).

Auxiliary space is O(n) for either approach when storing n keys. The input is not counted separately, and no recursion stack is involved.

In Python 3.12, dict uses a compact open-addressing implementation and preserves insertion order. A set is also implemented as a hash table, but it stores keys rather than key-value pairs. Practical dictionary keys should be hashable and stable; lists cannot be keys because they are unhashable, while tuples can be keys when all their elements are hashable.

Common Pitfalls

  • Do not treat collisions as exceptional: different keys routinely share a bucket, so lookup logic must continue probing or searching the chain.

  • Avoid full-table loops: open addressing needs a bounded probe count or an explicit empty-slot check.

  • Do not mutate a key’s hash during use: changing the hash state can make the key unreachable.

  • Handle duplicate keys consistently: inserting an existing key should update its value rather than create an invalid duplicate entry.

  • Remember resizing costs: an individual resize is O(n), even though insertion remains amortized O(1).

  • Account for adversarial inputs: worst-case O(n) behavior is possible when many keys collide or probe sequences become highly concentrated.

8

What makes a good hash function?

A good hash function deterministically maps keys to fixed-size hash values, computes efficiently, and distributes likely keys uniformly enough to keep collisions and probe lengths low. For hash tables, “good” primarily means useful distribution and speed rather than cryptographic security.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Characteristics

  • Deterministic: The same key must produce the same hash during its lifetime in the table. Equal keys must also have equal hashes.

  • Uniform distribution: Hash values should spread across the available buckets. With m buckets and n keys, uniform hashing gives an expected chain length of approximately n/m under a chaining scheme.

  • Fast computation: Hashing a conventional k-byte key takes O(k) time because the key is processed byte by byte or word by word. It can use O(1) auxiliary space when streamed.

  • Avalanche effect: A small input change should affect many output bits. This is desirable for many general-purpose hashes, although it is not the only way to achieve good bucket distribution.

  • Suitable for the expected data: A function should distribute both random and structured keys well. Sequential identifiers, common words, and attacker-controlled input are common test cases.

Hash-Table Internals and Complexity

A table has m buckets and a load factor α = n/m. A key’s hash normally determines its initial bucket through hash(key) % m.

  • Separate chaining stores a list of colliding entries in each bucket. It is simple and commonly implemented with a list of lists.

  • Open addressing stores entries directly in the table and searches other slots after a collision. Linear probing examines consecutive slots, quadratic probing examines offsets such as i², and double hashing uses a second hash to choose probe steps.

  • Resizing allocates a larger bucket array and rehashes every stored key into its new bucket. With bounded load factors and geometric growth, resizing makes insertion amortized O(1).

Operation Best Average Worst Space
Hash a k-byte key O(k) O(k) O(k) O(1) auxiliary when streamed
Lookup, insert, or delete after hashing O(1) O(1); insertion amortized O(1) O(n) O(n + m) table storage

The bounds assume bounded load factors and good hashing. The worst case occurs when many keys collide or probe the same sequence. Table storage counts buckets and stored entries; counting the input payloads as well still gives O(n + m) total space, and no recursion stack is involved.

Cryptographic Hashes

Property Non-cryptographic hash Cryptographic hash
Pre-image resistance Not required Finding an input for a given hash must be computationally hard
Second-preimage resistance Not required Finding a different input with the same hash must be hard
Collision resistance Accidental collisions should be rare Finding any collision must be computationally hard
Performance Usually optimized for speed Usually secure and fast; password KDFs are deliberately slow

SHA-256 and BLAKE3 are cryptographic hashes, not key-stretching functions. Password storage should use a salted password KDF such as Argon2id, scrypt, or PBKDF2. Ordinary hash tables need good collision distribution, not cryptographic preimage resistance.

Common Implementations

  • Python 3.12: hash() is type-dependent. Strings and bytes use SipHash-2-4 with a randomized per-process seed; integers use a numeric hash and are not randomized in that way.

  • Java: String.hashCode() uses s[0]·31^(n-1) + … + s[n-1]. HashMap separately spreads the result with h ^ (h >>> 16); it does not replace the specified String.hashCode() algorithm.

  • MurmurHash, xxHash, and FarmHash: Fast non-cryptographic hashes used in high-throughput systems, databases, and distributed systems.

  • FNV-1a: A fast byte-oriented non-cryptographic hash. Integers must first be encoded into bytes.

Interview Tips

  • Use an immutable, stable hash for dictionary keys. Python lists are unhashable because they are mutable; tuples are hashable only when their elements are hashable.

  • For a custom object, combine hashable fields without shadowing the built-in hash: for example, update value with value = value * 31 + hash(field). Dataclasses and attrs generate __hash__ when eq=True and frozen=True, provided the fields are hashable.

  • A conventional polynomial hash can use h = (31 * h + ord(character)) % M. This preserves input order, but a finite output range still permits collisions.

  • Do not mutate a key after insertion; its hash must remain unchanged.

  • Integer overflow differs by language: Java int overflow wraps modulo 2^32, C/C++ unsigned overflow wraps, and signed overflow in C/C++ is undefined.

  • Common follow-ups ask about load factor, rehashing, chaining versus probing, hash-flooding resistance, and the difference between hash-table hashes, cryptographic hashes, and password KDFs.

9

How does separate chaining handle collisions in a hash table?

Separate chaining is a collision resolution strategy in which every bucket of a hash table holds a list (or linked list) of entries that share the same hash index. When two keys hash to the same slot, they are simply appended to that bucket’s list, allowing the table to store more items than it has buckets.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A hash function maps each key to an index in the underlying array. Instead of rejecting or probing for another slot when a collision occurs, separate chaining stores all colliding keys in the same slot.

Consider a table with capacity 3 and keys 10, 22, and 33: 1. 10 % 3 = 1 → stored in bucket 1. 2. 22 % 3 = 1 → collision with 10. Appended to bucket 1’s list. 3. 33 % 3 = 0 → stored in bucket 0.

Lookup requires hashing the key to the index and then scanning the list at that index. This makes insertion fast because no other elements need to be moved.

Separate Chaining vs Open Addressing

Open addressing stores all elements directly in the array and probes for the next free slot on collision. Separate chaining stores elements in auxiliary structures attached to the array.

Feature Separate Chaining Open Addressing
Storage Linked lists or dynamic arrays in buckets Array slots only
Load Factor Can exceed 1.0 Must stay below 1.0
Cache Locality Poorer (pointers scattered) Better (contiguous memory)
Deletion Simple (remove from list) Complex (requires tombstones)
Performance Degrades if hash function is bad Degrades as table fills up

Load Factor and Resizing

The load factor is the ratio of stored elements to bucket capacity. In separate chaining, the load factor can grow indefinitely, but performance suffers as lists get longer. To maintain efficiency, the table is resized when the load factor exceeds a threshold, typically 0.75.

Resizing involves creating a new, larger array and rehashing every existing element into the new buckets. This rehashing is amortized O(1) per insertion because the cost is spread across many insert operations.

Complexity Analysis

  • Time (Average): O(1) for lookup, insert, and delete. The list at a bucket is short on average.

  • Time (Worst): O(n). This happens if a bad hash function maps all keys to the same bucket, turning the table into a linked list.

  • Space: O(n + k), where n is the number of elements and k is the bucket capacity. The input itself is not counted as extra space.

Common Pitfalls

  • Unhashable keys: Keys must be immutable. Lists cannot be keys because they are mutable and unhashable.

  • Poor hash functions: A hash function that maps all keys to the same index degrades performance to O(n).

  • Forgetting to resize: Without resizing, the load factor grows, making lookups slow.

  • Interview follow-ups: Interviewers often ask how to implement an LRU Cache using a hash map and a doubly linked list, or how to handle collisions in open addressing.

10

How does open addressing resolve hash table collisions?

Open addressing resolves hash-table collisions by storing every entry directly in a bucket array and probing alternative positions until an available one is found. Unlike separate chaining, it does not attach lists or secondary buckets to occupied positions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A hash function maps a key to an integer, and that integer determines the initial bucket:

index = hash(key) % capacity

If the bucket is occupied by another key, a collision has occurred. The algorithm calculates additional bucket positions according to a probing sequence. Each bucket contains at most one entry.

A typical insertion follows these steps:

  1. Compute the key’s initial bucket.

  2. If the bucket is empty, insert the entry.

  3. If it contains the same key, update its value.

  4. Otherwise, probe the next position and repeat.

  5. Resize the table when the load factor exceeds a configured threshold.

Hash consistency requires equal keys to have equal hashes. Keys must also be hashable and effectively immutable: tuples can be keys when their elements are hashable, while lists cannot because they are mutable.

Python’s dict uses a more sophisticated open-addressing layout rather than the simple array below. CPython preserves dict insertion order as a language guarantee since Python 3.7. A Python set stores keys in a hash table.

Probing Techniques

Technique Probe formula Advantages Limitations
Linear probing (h(key) + i) % m Simple and cache-friendly Creates primary clustering, where consecutive slots fill
Quadratic probing (h(key) + i²) % m Reduces primary clustering Can create secondary clustering or repeat probe positions
Double hashing (h1(key) + i × h2(key)) % m Usually distributes keys best Requires a suitable second hash and careful table-size selection

Here, i starts at zero and increases for each probe, while m is the bucket-array capacity.

For double hashing, h2 should be nonzero and ideally relatively prime to m, allowing the probe sequence to visit every bucket. For quadratic probing, the table size and coefficients must be chosen carefully because some sequences may not cover every position.

Complexity and Resizing

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) O(1) O(n)
Delete O(1) O(1) O(n)

The average-case bounds assume a reasonable load factor and sufficiently uniform hashing. The worst case occurs when many entries cluster in one region and the algorithm must inspect most of the table.

The load factor is approximately:

load factor = live entries / capacity

When it becomes too large, the table is resized and every live entry is rehashed into a larger array. Rehashing one table costs O(n), but doubling the capacity periodically makes insertion amortized O(1) even though an individual insertion can cost O(n).

Deletion normally marks a position as a tombstone rather than simply clearing it. Otherwise, later probes could incorrectly stop at that position. Tombstones reduce usable capacity and should eventually be removed through rehash-based cleanup.

Space usage is O(n) for the bucket array, including both buckets and stored entries. The implementation below uses O(1) auxiliary stack space because it is iterative; the input is not counted.

Code Example

from collections.abc import Hashable


def linear_probing_demo() -> list[int | None]:
    """Demonstrate insertion, lookup, deletion, tombstone reuse, and resize."""
    capacity = 8
    keys: list[Hashable | None] = [None] * capacity
    values: list[int | None] = [None] * capacity
    occupied = [False] * capacity
    deleted = [False] * capacity
    live_count = 0
    deleted_count = 0

    def locate(key: Hashable) -> tuple[int, int]:
        index = hash(key) % capacity
        insertion_index = -1

        for _ in range(capacity):
            if occupied[index]:
                if keys[index] == key:
                    return index, index
            elif deleted[index]:
                if insertion_index == -1:
                    insertion_index = index
            else:
                return -1, insertion_index

            index = (index + 1) % capacity

        return -1, insertion_index

    def resize(new_capacity: int) -> None:
        nonlocal capacity, keys, values, occupied, deleted
        nonlocal live_count, deleted_count

        old_keys = keys
        old_values = values
        old_occupied = occupied

        capacity = new_capacity
        keys = [None] * capacity
        values = [None] * capacity
        occupied = [False] * capacity
        deleted = [False] * capacity
        live_count = 0
        deleted_count = 0

        # Rehash every live entry into the larger table.
        for old_index, key in enumerate(old_keys):
            if old_occupied[old_index]:
                new_index = hash(key) % capacity
                while occupied[new_index]:
                    new_index = (new_index + 1) % capacity

                keys[new_index] = key
                values[new_index] = old_values[old_index]
                occupied[new_index] = True
                live_count += 1

    def put(key: Hashable, value: int) -> None:
        nonlocal live_count, deleted_count

        found_index, insertion_index = locate(key)
        if found_index != -1:
            values[found_index] = value
            return

        if (live_count + 1) / capacity >= 0.70:
            resize(capacity * 2)
            _, insertion_index = locate(key)
        elif deleted_count > live_count:
            resize(capacity)
            _, insertion_index = locate(key)

        if insertion_index == -1:
            raise RuntimeError("Hash table has no available bucket")

        keys[insertion_index] = key
        values[insertion_index] = value
        occupied[insertion_index] = True
        live_count += 1

    def get(key: Hashable) -> int:
        found_index, _ = locate(key)
        if found_index == -1:
            raise KeyError(key)
        return values[found_index]  # type: ignore[return-value]

    def delete(key: Hashable) -> None:
        nonlocal live_count, deleted_count

        found_index, _ = locate(key)
        if found_index == -1:
            raise KeyError(key)

        keys[found_index] = None
        values[found_index] = None
        occupied[found_index] = False
        deleted[found_index] = True
        live_count -= 1
        deleted_count += 1

    results: list[int | None] = []

    put(1, 10)
    put(9, 20)  # Collides with 1 and is placed in the next bucket.
    results.append(get(1))

    delete(1)  # Leaves a tombstone.
    results.append(get(9))

    put(17, 30)  # Reuses the tombstone.
    results.append(get(17))

    for key in range(2, 7):
        put(key, key * 10)  # Eventually triggers a resize.

    results.append(get(9))
    return results


print(linear_probing_demo())  # [10, 20, 30, 20]

For the small collision example, 1 and 9 initially map to the same bucket when capacity is 8. The second key moves to the next bucket, and deletion of the first key leaves a reusable tombstone.

Common Pitfalls

  • Failing to resize: A high load factor increases probing time and may exhaust the table.

  • Ignoring tombstones: Deleted positions can make later searches unnecessarily long.

  • Using mutable keys: Changing a key’s contents can make it unreachable in the table.

  • Confusing hashes with equality: Both consistent hashing and correct equality checks are required.

  • Assuming constant-time worst case: Probing can degrade to O(n) because of clustering.

  • Overlooking edge cases: Duplicate keys should update the existing value; negative and other hashable keys are valid; an empty table must be initialized; and a full table must be resized or rejected.

  • Common follow-up questions: Interviewers often ask about deletion, rehashing, load-factor thresholds, collision attacks, and how Python’s dict differs from the textbook implementation.

11

What are the time and space complexity of hash tables?

A hash table provides average-case constant-time lookup, insertion, and deletion by mapping keys to buckets with a hash function. Its performance depends on the load factor, hash-function quality, collision strategy, and whether resizing is required.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hash Tables Work

  • Hash function: Converts a key into an integer hash. The table maps that hash to a bucket index, commonly using modulo.

  • Buckets: At any given moment, the table has a fixed number of bucket slots, each holding zero or more entries. Resizing can later change that number.

  • Load factor: α = number of entries / number of buckets. A higher load factor generally means longer collision chains or probing sequences.

  • Hashability: Keys must have a stable hash and support equality comparisons. Python lists are unhashable because they are mutable, while tuples are hashable only when all their elements are hashable.

  • Rehashing: When the load factor exceeds a threshold, the table allocates more buckets and recomputes every key’s bucket index.

These bounds assume constant-time hashing and equality. For strings or other variable-length keys, hashing can add an O(k) cost, where k is the key length.

Collision Handling

Strategy How collisions are stored Average lookup Worst lookup Space
Separate chaining Multiple entries occupy the same bucket, commonly using a linked list or list O(1 + α) O(n) O(n + m)
Linear probing Collisions move to the next available slot O(1 + α) O(n) O(m)
Quadratic probing Collisions use a quadratic offset sequence O(1 + α) O(n) O(m)
Double hashing Collisions use a second hash-derived step O(1 + α) O(n) O(m)

Here, n is the number of entries and m is the number of buckets. With a bounded load factor, m = Θ(n), so total table space is O(n).

Time and Space Complexity

Operation Best Average Worst Reason
Lookup O(1) O(1) expected O(n) Usually one bucket is checked, but all entries could collide
Insert O(1) O(1) expected; O(1) amortized O(n) Resizing or pathological collisions can process many entries
Delete O(1) O(1) expected O(n) Finding the key may require scanning a long chain
Resize/rehash O(n) O(n) O(n) Every existing entry is placed into a new bucket array

A resize itself is O(n). If the bucket count doubles when the table becomes too full, that cost is spread across subsequent insertions, producing amortized O(1) insertion.

The table uses O(n + m) space, or O(n) with a bounded load factor, including both bucket storage and stored entries. An iterative implementation uses O(1) recursion-stack space. The original input is not counted separately.

Python dict and set

In CPython 3.12, dict uses a compact open-addressed layout and preserves insertion order, which has been a language guarantee since Python 3.7. Its operations are O(1) on average and O(n) in the worst case because of adversarial collisions.

A Python set is also implemented as a hash table, but it stores keys rather than key-value pairs. Deleting a dictionary entry does not change the relative order of the remaining entries.

Common Pitfalls

  • Do not report only O(1); interviews usually expect average, worst-case, and amortized insertion bounds.

  • State the load-factor assumption. With unbounded chaining, expected operations become O(1 + α), not automatically O(1).

  • Include bucket arrays, stored entries, and temporary resize storage in the space analysis.

  • Distinguish table space from input space and state the O(1) recursion-stack requirement for iterative implementations.

  • Handle empty and one-element tables, missing keys, duplicate keys, negative integer keys, and resizing correctly.

  • A common follow-up asks why dict and set require hashable keys and why lists cannot be used as keys.

12

What does load factor mean in hash tables?

The load factor in a hash table measures how full the table is relative to its capacity. It is usually expressed as the number of stored entries divided by the number of available buckets or slots, and it helps determine when collisions are becoming likely enough to warrant resizing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Formula

For a hash table with n stored entries and m buckets or slots:

load factor = n / m

Examples:

  • 75 entries in 100 buckets produce a load factor of 0.75.

  • 120 entries in 100 buckets produce a load factor of 1.2.

The implementation selects a maximum load factor, often around 0.75 for open-addressed hash tables. This threshold is a design choice rather than a universal standard.

Why Load Factor Matters

The hash function maps keys to buckets, so different keys can still map to the same bucket. This is called a collision. As the load factor increases:

  • More keys compete for the same buckets.

  • Lookup, insertion, and deletion take longer.

  • Open addressing is especially affected because a new key must search a sequence of occupied slots.

  • Memory efficiency may improve slightly because fewer buckets are needed, but at the cost of more collisions.

Many implementations resize or rehash the table when the load factor exceeds the configured threshold.

Resizing and Rehashing

When resizing, the implementation usually:

  1. Allocates a larger bucket or slot array.

  2. Recomputes each key’s bucket using the new capacity.

  3. Moves or re-inserts every entry into the new table.

This process is called rehashing. Because bucket selection depends on the table capacity, keys generally cannot be copied directly to their old positions.

A single insertion during a resize can take O(n) time. However, the resize cost is spread across many insertions, giving amortized O(1) time per insertion.

Operation Best Case Average Case Worst Case Reason
Lookup O(1) O(1) O(n) The key is found immediately on average but may collide with all other keys in the worst case.
Insertion O(1) O(1) amortized O(n) Average insertion includes amortized resizing; a full or highly collided table can require linear work.
Deletion O(1) O(1) O(n) The key is found immediately on average but may require searching a collision chain or probing sequence.
Resizing O(n) O(n) O(n) Every stored entry must be rehashed into the new table.

These bounds assume constant-time hashing and comparison. They can degrade if the hash function is expensive or poorly distributed.

Space Complexity

A hash table storing n entries with m buckets or slots uses O(n + m) total space, including its stored entries and bucket structure. The input itself is not counted separately.

During resizing, transient memory usage can temporarily approach O(n + m) because the old and new tables may exist simultaneously. This is generally not a recursion-stack concern because rehashing is normally implemented iteratively.

Collision-Handling Context

Collision Strategy Typical Load-Factor Interpretation Main Concern
Separate chaining Average number of entries per bucket Long chains increase lookup time; the table can exceed a load factor of 1.
Open addressing Fraction of occupied slots A high load factor leaves long probing sequences; the load factor generally must remain below 1.
Linear or quadratic probing Occupied-slot ratio Poor probe distribution can create clustering, especially with linear probing.
Double hashing Occupied-slot ratio Better distribution than linear probing, but it requires a suitable second hash function.

In Python 3.12, dict maintains insertion order, a guarantee introduced in Python 3.7. Its implementation manages its internal table and resizing automatically, so application code usually does not need to calculate or manage the load factor directly.

Common Pitfalls

  • Confusing load factor with occupancy: In chaining, several entries may occupy one bucket, so the number of used buckets can be lower than the number of entries.

  • Assuming a fixed threshold: 0.75 is common, but the appropriate value depends on the implementation and collision strategy.

  • Ignoring tombstones: In open addressing, deleted entries may remain as tombstones until rehash cleanup, increasing the effective occupancy.

  • Reporting only average complexity: State both average O(1) and worst-case O(n) behavior.

  • Forgetting amortized insertion cost: Resizing makes one insertion potentially expensive, but sequential insertions cost O(1) amortized each.

  • Failing to distinguish total and auxiliary space: The table occupies O(n + m) total space; additional workspace during rehashing is typically O(n + m) in the worst case.

Interview Tips

A strong answer should explain that load factor controls table fullness, connect it to collision probability and resizing, and mention that insertion remains O(1) amortized. Interviewers may follow up by asking how resizing works, how deletion affects load factor, or why a lower load factor improves performance but uses more memory.

13

How does load factor affect hash table performance?

The load factor is the ratio of stored entries to available buckets. It controls table density: lower load factors usually reduce collisions and probing costs, while higher load factors increase them but use memory more efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Internals

For a hash table containing n entries and m buckets:

[ text{load factor } alpha = frac{n}{m} ]

  • Hash function: Converts a key into a numeric hash value, often using hash(key) % m to select a bucket.

  • Buckets: Store or reference entries associated with each hash value.

  • Collision: Occurs when multiple keys map to the same bucket or occupied slot.

  • Load factor: Indicates how densely the buckets are occupied.

If m grows proportionally to n, the load factor remains bounded as the table grows.

Performance Effects

A higher load factor generally means:

  • More collisions or longer probe sequences.

  • More key comparisons in separate chaining.

  • More cache misses when scanning chains or probing slots.

  • Greater clustering in open addressing, especially with linear probing.

  • More work to locate entries before deleting them; tombstone accumulation is a separate open-addressing issue.

A lower load factor generally means:

  • Fewer collisions and shorter searches.

  • Faster lookups, insertions, and deletions.

  • More memory used for buckets or slots.

  • Potentially poorer cache locality if the table becomes unnecessarily large.

The best load factor depends on the hash function and collision strategy. Keeping the load factor bounded is usually more important than choosing one universal value.

For example, suppose a hypothetical table has 8 buckets and resizes when the load factor would exceed 0.75:

State Buckets Entries Load factor
Initially 8 0 0
Before seventh insertion 8 6 0.75
After resizing and rehashing 16 6 0.375
After seventh insertion 16 7 0.4375

Actual thresholds and growth policies are implementation-specific.

Complexity and Resizing

Assuming a good hash function and controlled load factor:

Operation Best Case Average Case Worst Case
Lookup O(1) O(1) O(n)
Insertion O(1) O(1) O(n)
Deletion O(1) O(1) O(n)
  • Best case: The key is found in the first examined bucket or slot.

  • Average case: Collisions remain rare because the load factor is bounded.

  • Worst case: Many keys collide, creating a chain of length n or requiring nearly the entire table to be searched.

For separate chaining, expected lookup cost is approximately O(1 + α), which becomes O(1) when α is bounded by a constant. For open addressing under uniform hashing, expected lookup cost is approximately O(1 / (1 - α)) for α < 1.

Space complexity is O(n + m) because the table stores n entries and m buckets or slots, excluding the input itself; no recursion stack is involved. Open addressing typically requires O(m) space, while separate chaining requires O(n + m).

A typical resize performs three steps:

  1. Allocate a larger bucket array.

  2. Rehash every existing key using the new bucket count.

  3. Place each key into its new bucket or slot.

Rehashing is necessary because changing the bucket count changes hash(key) % m. Geometric capacity growth makes each resize O(n), but produces amortized O(1) insertion time across a sequence of insertions. Peak space during resizing remains O(n + m) because old and new tables may coexist temporarily.

Collision Strategies

  • Separate chaining: Each bucket contains a list or linked list of colliding entries. Higher load factors create longer chains, and this strategy can support a load factor above 1.

  • Linear probing: Checks the next slot after a collision. High load factors can cause primary clustering.

  • Quadratic probing: Checks slots separated by squared offsets, reducing primary clustering but requiring careful probe-sequence design.

  • Double hashing: Uses a second hash-derived step size and aims to distribute keys more evenly.

Open addressing requires enough empty slots for successful searches and insertions, so implementations normally resize before the load factor becomes too high.

Python Dictionaries and Sets

CPython’s dict uses an open-addressing-based internal layout and maintains insertion order, guaranteed since Python 3.7. A Python set stores its elements in a hash-table-based structure.

Dictionary and set operations have average O(1) time and O(n) worst-case time. Their keys must be hashable: built-in mutable containers such as lists are unhashable and cannot be keys, while tuples can be keys when every contained value is hashable.

Common Pitfalls

  • Treating average O(1) operations as guaranteed; adversarial collisions can still cause O(n) behavior.

  • Assuming a smaller table is always faster; excessive resizing consumes time and memory.

  • Forgetting that changing the bucket count requires rehashing all entries.

  • Using open addressing without preserving empty slots or handling tombstones correctly.

  • Expecting users of dict or set to control their internal load factor directly.

  • Getting resize thresholds off by one and allowing the table to exceed its maximum load factor.

  • Ignoring integer overflow in fixed-width languages when calculating sizes, hashes, or bucket indices.

  • Rehashing should not mutate caller-owned keys or collections; graph traversal built around a hash table also still requires visited markers to prevent cycles.

  • Common follow-ups ask about hash quality, collision handling, worst-case behavior, and why resizing is amortized O(1).

14

What are the hash table resizing strategies and complexity?

Hash table resizing is the process of changing the number of buckets when the table becomes too full or too empty, ensuring that operations remain fast. It involves rehashing existing keys into a new, larger (or smaller) array of buckets.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Resizing Works

Resizing is triggered by the load factor, which is the ratio of stored elements to total buckets. When the load factor exceeds a threshold (commonly 0.75), the table must grow to maintain O(1) performance. Conversely, if the load factor drops too low (e.g., below 0.25), the table may shrink to save memory.

The core steps are: 1. Allocate a new array of buckets with the new size. 2. Iterate through every existing key-value pair. 3. Compute the new index for each key using the new size (rehashing). 4. Insert the pair into the new array.

Python’s built-in dict uses open addressing and grows dynamically, while a custom implementation often uses chaining with separate linked lists or arrays per bucket.

Resizing Strategies

There are two primary approaches to determining the new size:

  • Exponential Growth (Doubling): The most common strategy. The capacity is doubled (e.g., 8 → 16 → 32). This ensures that the number of resize operations is logarithmic relative to the number of inserts, keeping the amortized cost low.

  • Linear Growth: The capacity is increased by a fixed amount (e.g., +16). This is less common because it can lead to frequent resizing as the table grows large.

For shrinking, the capacity is typically halved. Some implementations only grow and never shrink to avoid the cost of frequent rehashing, but this wastes memory if the table is emptied.

Complexity Analysis

The complexity depends on whether you look at a single operation or the sequence of operations over time.

Case Time Complexity Reason
Best Case O(1) Insert does not trigger a resize; only a single hash and bucket insertion.
Average (Amortized) O(1) Resizing is rare. The cost of a resize is spread across many successful O(1) inserts.
Worst Case (Single Op) O(n) A single insert may trigger a resize, requiring all n elements to be rehashed.
Space O(n) The table stores n elements plus empty buckets.

The amortized O(1) guarantee holds because if you double the size each time, the total cost of n inserts is O(n), making the average cost per insert O(1).

Common Pitfalls

  • Forgetting to rehash: Simply allocating a larger array without rehashing keys will break lookups, as indices depend on the table size.

  • Resizing too often: Using a small growth increment (e.g., +1) causes O(n) resizes for every insert, degrading performance to O(n) average.

  • Negative numbers: Ensure the hash function handles negative keys correctly (Python’s % operator returns a non-negative result for positive divisors, so it is safe).

  • Duplicates: Always check for an existing key in the bucket before appending to avoid storing duplicate entries.

  • Memory waste: Shrinking too aggressively can cause “thrashing,” where the table repeatedly grows and shrinks.

15

How does the hash function choice affect hash table performance?

The choice of a hash function determines how keys are distributed across buckets, directly affecting collision rates, chain or probe lengths, and average operation cost. A good hash function distributes expected keys uniformly; a poor one creates clusters and can degrade performance from constant time toward linear time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hashing Affects Performance

A hash function converts a key into an integer hash code, which is usually reduced modulo the number of buckets:

bucket_index = hash(key) % bucket_count

A good hash function should be:

  • Uniform: distributes similar keys across different buckets.

  • Consistent: equal keys produce equal hash codes.

  • Fast: computes the hash with low constant overhead.

  • Hard to predict: reduces the risk of adversarial inputs causing collisions.

For example, if every integer hashes to 0, every key enters the same bucket under separate chaining. Searching that bucket becomes linear even when the table has many otherwise unused buckets.

Collisions, Buckets, and Load Factor

Collisions occur when different keys map to the same bucket and must be handled differently:

Strategy How collisions are handled Main characteristic
Separate chaining Each bucket stores a list of entries Simple and tolerant of high load factors
Linear probing Try the next bucket sequentially Good cache locality but vulnerable to primary clustering
Quadratic probing Try buckets using a quadratic sequence Reduces primary clustering but may not visit every slot
Double hashing Use a second hash to determine the probe step Strong distribution when the step size is chosen correctly

The load factor is entry_count / bucket_count. A higher load factor uses memory efficiently but increases collisions and probe lengths. Hash tables therefore usually resize when the load factor exceeds a threshold, commonly around 0.75.

Resizing creates a larger bucket array and rehashes every entry. A single resize costs O(n), but growing geometrically—for example, doubling the capacity—makes insertion amortized O(1).

Complexity

For a well-distributed hash function:

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) amortized O(1) O(n)
Delete O(1) O(1) O(n)
Resize or rehash O(n) O(n) O(n)

The worst case occurs when many keys collide in one bucket or probing cluster. A poor hash function can make the average behave like O(n) for a particular key distribution.

Space usage is O(n) for the bucket array and stored entries. The input is not counted separately, and hash-table operations use no recursion.

Python dict, Sets, and Hashable Keys

CPython’s dict uses an open-addressed entry table and has guaranteed insertion order since Python 3.7. A set is also implemented as a hash table, but it stores keys without associated values.

Dictionary and set keys must be hashable and should not change while stored:

  • Lists cannot be keys because they are mutable and unhashable.

  • Tuples can be keys when all their elements are hashable.

  • Negative numbers are valid keys, although Python maps -1 and -2 to the same hash value; the dictionary resolves the collision correctly.

  • A custom object should define __hash__ and __eq__ consistently: equal objects must have equal hashes.

Common Pitfalls

  • Assuming every hash function is uniform: integer hashes are predictable, so untrusted integer keys can create collision-heavy patterns.

  • Confusing a fast hash with a good hash: computing a hash quickly is insufficient if it produces poor bucket distribution.

  • Ignoring equality semantics: hashes locate candidate entries, but equality determines whether the key already exists.

  • Forgetting resizing costs: O(n) rehash work is acceptable only because capacity grows geometrically.

  • Changing a stored key’s hash: mutable custom keys can become unreachable inside the table.

  • Ignoring the load factor: allowing excessive occupancy increases chain lengths and probing work even with a good hash function.

16

How do general-purpose and cryptographic hash functions differ?

A general-purpose hash function rapidly maps data to a compact value for efficient data-structure operations, while a cryptographic hash function provides security properties that make unauthorized modification, forgery, and collision-based attacks computationally impractical. Cryptographic hashes are designed for integrity and security, not merely for distributing data across hash-table buckets.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Purpose and Guarantees

Property General-purpose hash Cryptographic hash
Primary purpose Fast lookup, indexing, deduplication, and bucket selection Integrity checks, digital signatures, commitment schemes, and security protocols
Collision resistance Usually weak or not required Strong computational collision resistance
Output size Often an integer of fixed machine-dependent width Usually a fixed bit length, such as 256 bits for SHA-256
Performance priority Maximum speed and good distribution Security, while remaining reasonably efficient
Typical uses dict, set, caches, and hash-based collections SHA-256, SHA-3, BLAKE2, and other approved secure hashes

A collision occurs whenever two different inputs produce the same hash value. General hash functions can tolerate collisions because hash tables resolve them with techniques such as chaining or open addressing. A cryptographic hash function is not mathematically collision-free, but finding a meaningful collision should require an infeasible amount of computation.

Cryptographic Security Properties

A secure unkeyed cryptographic hash function is expected to provide:

  • Preimage resistance: Given digest = hash(message), it should be infeasible to recover any message producing that digest.

  • Second-preimage resistance: Given a message and its digest, it should be infeasible to find a different message with the same digest.

  • Collision resistance: It should be infeasible to find any two different messages with the same digest.

These guarantees are computational rather than absolute. For example, SHA-256 produces only (2^{256}) possible outputs, so collisions exist mathematically. Its security relies on the expected cost of finding one being too high for practical attackers.

Operation in Hash Tables

A general-purpose hash function transforms a key into a value that selects a bucket:

  1. Compute hash(key).

  2. Convert the result into a bucket index.

  3. Search that bucket using the collision-handling strategy.

  4. Compare the stored key with the requested key because different keys may have collided.

Python 3.12 dictionaries use open addressing internally, while sets store hashable keys in a hash table. Dictionary iteration preserves insertion order, guaranteed since Python 3.7.

Python’s built-in hash() is suitable for general data structures but not cryptography. Its result for str and bytes is randomized between processes, and equal values always produce equal hashes within a process. It must not be used for signatures, password storage, access tokens, or other security-sensitive purposes. Libraries such as hashlib provide standardized cryptographic hashes such as SHA-256 and SHA-3.

Complexity

  • Hash computation: A cryptographic hash such as SHA-256 takes (O(m)) time for a message of length (m), because every input byte must be processed.

  • Auxiliary space: SHA-256 uses (O(1)) auxiliary space with a fixed internal state. The input and stored output are not counted.

  • Hash-table lookup, insertion, and deletion: With a well-distributed hash and controlled load factor, each operation is (O(1)) average. In the worst case, many keys collide and the operation is (O(n)).

  • Key hashing cost: If hashing a key costs (O(m)), a complete hash-table operation costs (O(m + 1)) on average and (O(m + n)) in the worst case. The common (O(1)) claim assumes constant-time or previously cached key hashing.

  • Hash-table storage: Storing (n) key-value entries requires (O(n)) space. The original input is not counted separately, and there is no recursion stack.

Example Walkthrough

Consider two different strings, "abc" and "def".

  1. A general hash might compute small integer values such as hash("abc") and hash("def").

  2. A dictionary applies its internal table mask or modulo operation to choose bucket indices.

  3. If both values select the same bucket, the dictionary resolves the collision through its open-addressing sequence and compares the actual keys.

  4. A cryptographic hash instead computes a 256-bit SHA-256 digest for each string.

  5. The two digests should differ, and finding two practical inputs with the same digest should be computationally infeasible.

Common Pitfalls

  • Confusing collision handling with cryptographic security: A hash table can function correctly despite many collisions; a cryptographic protocol may fail if collisions become easy to find.

  • Using hash() for security: Python’s built-in hash() is not a cryptographic hash function and is unsuitable for signatures, authentication, or integrity guarantees.

  • Using obsolete algorithms: MD5 and SHA-1 should not be used for new security designs. Prefer SHA-256 or SHA-3 when an approved standard hash is required.

  • Treating hashes as reversible encryption: A hash does not encrypt or decrypt data. Recovering a preimage is intended to be infeasible.

  • Ignoring domain separation: Protocols should include the relevant context, algorithm identifier, and version in the hashed message to prevent cross-protocol attacks.

  • Confusing a hash with a password-storage function: Passwords should be processed with a slow, salted password-hashing function such as Argon2, scrypt, or bcrypt rather than a fast cryptographic digest.

17

What does a salt do in cryptographic hashing?

A salt is a non-secret random value incorporated into a password-hashing operation. By using a different salt for each password, identical passwords will normally produce different stored hashes, preventing attackers from reusing one set of precomputed hashes across many accounts.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Purpose and Threat Model

Password hashes are commonly stored in databases that may later be exposed. Without a salt, an attacker can:

  • Precompute hashes: Build a dictionary of common password-to-hash mappings once, then test every stored hash against it.

  • Identify repeated passwords: Recognize when multiple users have the same password because their hash values match.

  • Perform rainbow-table attacks: Use large precomputed tables mapping many common passwords to their hashes.

A per-password salt changes the input to the password-hashing operation. For example, two users with the password Password123! might produce different results because their salts differ.

The salt does not prevent guessing attacks against an individual password. An attacker who obtains the salt and hash can still try candidate passwords. It prevents one set of precomputed work from being reused for every account.

How Salting Works

A typical password-storage process is:

  1. Generate cryptographically secure random salt bytes.

  2. Store the salt alongside the resulting password hash.

  3. Run the password through a dedicated password-hashing algorithm using that salt.

  4. During login, retrieve the stored salt and parameters, hash the submitted password with them, and compare the result with the stored hash.

  5. If the salt or stored hash format is invalid, reject the verification attempt.

Modern password hashes normally encode the algorithm, parameters, salt, and resulting hash together, for example as one encoded string. The salt itself does not need to be secret because it is required to verify the password.

A common practice is to use at least 16 random bytes per password. The exact size should follow the password-hashing algorithm’s recommendations.

Salt Compared with Other Values

Value Secret? Purpose Stored with password hash?
Salt No Prevents reuse of precomputed hashes and distinguishes identical passwords Yes
Pepper Yes Adds a secret unknown to the database attacker No; kept separately
Hash No Represents the password using a one-way function Yes
Encryption key Yes Supports reversible encryption Usually stored securely elsewhere

A pepper is optional and must be protected separately, such as in a secrets manager. A salt alone is intended to provide most of the protection against precomputation.

Algorithm Choice

For passwords, use a deliberately expensive Argon2id, scrypt, or bcrypt implementation rather than a general-purpose fast hash such as SHA-256 or MD5, subject to platform and operational requirements.

A salt prevents reusable precomputation, but it does not make a fast algorithm suitable for password storage. An attacker can still automate many guesses; the algorithm’s work factor, memory requirements, and hardware parallelism determine the actual guessing rate.

Complexity

For a password of length (m), a salt of length (s), and fixed algorithm parameters:

  • Best, average, and worst-case time: All have the same parameterized bound, (O(m + s + C)), where © is the algorithm’s configured per-hash work cost. A plain hash over the combined input is (O(m + s)), but password KDFs add an intentional cost © that can dominate and is not determined solely by the input lengths.

  • Auxiliary space: (O(s + M)), excluding the original password input, where (M) is the KDF’s configured working-memory requirement. The salt itself requires (O(s)) storage; memory-hard algorithms such as Argon2id and scrypt make (M) significant.

  • Recursion stack: No recursion stack is involved in the conceptual salting operation.

Common Pitfalls

  • Reusing one salt across all passwords: This weakens protection because attackers can build precomputed hashes for that shared salt and test them against every affected account.

  • Using predictable salts: A predictable or low-entropy salt allows attackers to construct targeted precomputed tables.

  • Treating the salt as a replacement for slow hashing: Salting and password-hashing cost solve different problems.

  • Storing the salt where verification cannot access it: The salt must be available to the verifier and can safely be stored with the hash.

  • Using fast general-purpose hashes: Use Argon2id, scrypt, or bcrypt with current recommended parameters.

  • Changing the salt during verification: Verification must use the exact salt and parameters associated with the stored hash.

18

What are preimage, second-preimage, and collision resistance in cryptography?

Preimage resistance, second-preimage resistance, and collision resistance are the three main security properties expected from a cryptographic hash function. They determine how difficult it is for an attacker to reverse a digest or make two different messages produce the same digest.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Resistance Properties

  • Preimage resistance: Given a digest y, it is computationally infeasible to find any message x such that H(x) = y. This property provides one-wayness, but it does not guarantee that the original message cannot be recovered if additional information is available.

  • Second-preimage resistance: Given a message x and its digest H(x), it is computationally infeasible to find a different message x' such that H(x') = H(x).

  • Collision resistance: It is computationally infeasible to find any two different messages x and x' such that H(x) = H(x'). Unlike second-preimage resistance, the attacker does not need to begin with a particular message.

These properties are distinct. Finding a collision proves that two messages share a digest, but it does not necessarily reveal a preimage for an arbitrary target digest.

Comparing the Attacks

Property Attacker starts with Attacker must produce
Preimage resistance A target digest y Any message x with H(x) = y
Second-preimage resistance A message x and H(x) A different message x' with H(x') = H(x)
Collision resistance Usually no original message Any two different messages with equal digests

For an ideal hash with an n-bit output:

  • A preimage attack generally requires approximately 2^n hash evaluations.

  • A second-preimage attack also generally requires approximately 2^n evaluations.

  • A collision attack generally requires approximately 2^(n/2) evaluations because of the birthday paradox.

For example, SHA-256 produces 256 bits. Generic preimage resistance is therefore approximately 256-bit security, while generic collision resistance is approximately 128-bit security in concrete terms, corresponding to 2^128 work. Actual security depends on the algorithm; weaknesses in the construction can reduce these theoretical levels.

Practical Security Requirements

  • A password-storing system should use a deliberately slow, salted password-hashing function such as Argon2, scrypt, or bcrypt. Ordinary cryptographic hashes such as SHA-256 are designed to be fast.

  • A signature scheme normally requires collision resistance because an attacker could otherwise construct two messages with the same digest.

  • Content integrity often requires collision resistance. For example, two different software updates must not be able to share a digest.

  • Preimage resistance alone is insufficient when an existing message must remain uniquely associated with its digest; second-preimage or collision resistance may also be needed.

These guarantees assume that the hash algorithm, implementation, parameters, and surrounding protocol are secure. They do not mean that finding a matching message is mathematically impossible.

Complexity

Let n be the output length in bits and m the length of the message being hashed. Assuming hash evaluation takes O(m) time:

Generic search Time complexity Extra space complexity
Exhaustive preimage search O(2^n · m) O(1) when testing one candidate at a time
Exhaustive second-preimage search O(2^n · m) O(1) when testing one candidate at a time
Birthday collision search O(2^(n/2) · m) O(2^(n/2)) when storing previously seen digests

The space figures exclude storage for the input message. Memory-efficient collision searches can reduce auxiliary storage to O(1), although their exponential runtime remains the primary limitation.

Common Pitfalls and Interview Tips

  • Confusing the properties: A preimage attack reverses a digest, a second-preimage attack replaces a known message, and a collision attack finds two different messages sharing a digest.

  • Assuming resistance guarantees confidentiality: A digest may reveal whether two messages are equal without revealing their contents.

  • Ignoring implementation flaws: Side-channel leakage, incorrect encoding, truncation, and poor key handling can undermine otherwise strong algorithms.

  • Using fast hashes for passwords: Preimage resistance does not compensate for the excessive speed of general-purpose hashes.

  • Ignoring length-extension attacks: Some hash constructions permit length extension. Use HMAC or a suitable modern construction when that property matters.

  • Common follow-up: Explain why collision resistance is the most directly relevant property for digital signatures and why collision searches are approximately square-root as expensive as preimage searches.

19

What is the MD5 hash function?

MD5 is a deterministic cryptographic hash function that converts arbitrary-length input into a fixed 128-bit digest, usually displayed as 32 hexadecimal characters. It was designed for integrity verification, but its collision resistance has been broken, so it should not be used where cryptographic security is required.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How MD5 Works

MD5 processes the input as a sequence of bytes:

  1. The message is padded with a 1 bit, followed by zero bits until its length is 56 bytes modulo 64 bytes.

  2. The original message length, measured in bits, is appended as a 64-bit little-endian value.

  3. The padded message is divided into 64-byte blocks.

  4. Each block passes through four rounds containing 64 total operations using additions, rotations, bitwise functions, and fixed constants.

  5. The resulting 128-bit state is emitted as the digest.

The same input always produces the same digest. Unlike encryption, hashing is not reversible with a decryption key.

Security Properties

MD5 has these practical characteristics:

  • Fixed output: Every digest is exactly 128 bits, regardless of input length.

  • Deterministic: Equal byte sequences produce equal digests.

  • Avalanche effect: A small input change usually causes many digest bits to change.

  • Collision vulnerability: Different inputs can be constructed to produce the same MD5 digest.

  • Preimage resistance: Finding an input for a specified digest is still considered computationally infeasible.

The collision weakness makes MD5 unsafe for digital signatures, certificates, software distribution, or detecting deliberate file tampering. A matching digest only provides strong assurance when an attacker cannot modify both the file and its expected digest.

MD5 Compared with Modern Alternatives

Algorithm Output size Security status Appropriate use
MD5 128 bits Collision-broken Legacy compatibility only
SHA-256 256 bits Collision-resistant in current practice General-purpose integrity and signatures
SHA-3 Variable, commonly 256 bits Collision-resistant in current practice Modern hashing applications
Argon2id Configurable Password-oriented Password hashing

For passwords, use a dedicated password hashing function such as Argon2id, bcrypt, or scrypt. Fast general-purpose hashes are unsuitable because attackers can make many password guesses per second.

Time and Space Complexity

For a message containing (m) bytes:

  • Time: (O(m)), because MD5 processes the message in constant-size 64-byte blocks.

  • Auxiliary space: (O(1)), excluding the input, because the hash state and block buffer have fixed sizes.

  • Input storage: (O(m)) if the complete input must be held in memory; this is not part of MD5’s auxiliary hashing state.

  • Output storage: (O(1)), because the digest is always 16 bytes.

  • Recursion stack: (O(1)); MD5 processing does not use recursion.

Practical Use

MD5 may still appear in:

  • Legacy data formats and database identifiers

  • Compatibility checks against historical systems

  • Cache keys where collisions are not a security concern

  • Non-adversarial change detection

Even for accidental corruption detection, a purpose-built checksum such as CRC-32 may be more appropriate because it is faster and was not designed as a cryptographic primitive.

Common Pitfalls

  • Calling MD5 encryption: It is hashing and produces no decryption key.

  • Using it for security: Collision attacks make it unsuitable for signatures and adversarial integrity checks.

  • Confusing it with Python’s hash(): Python’s built-in hash() serves hash tables and may be randomized across processes; MD5 is a fixed cryptographic algorithm.

  • Hashing passwords directly: Use a salted password KDF rather than MD5, SHA-256, or another fast hash.

  • Assuming equal digests prove authenticity: Attackers can replace both the data and an unprotected MD5 digest.

  • Changing the encoding unintentionally: MD5 hashes bytes, so equivalent text with different encodings can produce different digests.

20

What are the vulnerabilities of MD5 and SHA1?

MD5 and SHA-1 are cryptographically broken for collision resistance: practical collision and chosen-prefix attacks can make distinct inputs share a digest, enabling forgery where an attacker controls a signed or certified prefix. Their Merkle–Damgård design also permits length-extension attacks, so neither belongs in signatures, certificates, password storage, or adversarial integrity checks.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Digest Construction and History

  • MD5: Introduced in 1992 and produces a 128-bit digest. Collisions appeared in 2004, with chosen-prefix attacks by 2009.

  • SHA-1: Introduced in 1995 and produces a 160-bit digest. The first practical collision, SHAttered, appeared in 2017; the first published chosen-prefix SHA-1 attack appeared in 2020.

  • Both pad messages into fixed-size blocks and repeatedly apply a compression function to a chaining state. This is the Merkle–Damgård construction.

Cryptographic Failure Modes

  • Collision resistance: Finding distinct m1 and m2 with the same digest is practical for MD5. SHAttered required roughly 2^63.1 SHA-1 computations; the 2020 chosen-prefix attack (“SHA-1 is a Shambles”) needed about 2^63.4.

  • Chosen-prefix collisions: An attacker controls two prefixes and appends suffixes to produce colliding messages. This enables certificate forgery and substitution in protocols that mistakenly trust an affected digest.

  • Preimage resistance: Recovering a message from its digest remains infeasible with known generic attacks for both algorithms, although neither has a formal proof of security.

  • Second-preimage resistance: Finding a second message matching a specific original message is also not known to be generically practical. Collision attacks do not automatically constitute second-preimage attacks, but they still violate protocols that assume digest uniqueness.

  • The generic birthday bound for an n-bit digest is approximately 2^(n/2): 2^64 for MD5 and 2^80 for SHA-1. Their actual collision attacks are substantially stronger than this bound predicts.

Length-Extension Attacks

Given H(m) and the length of m, an attacker can compute H(m || padding || extension) by continuing the Merkle–Damgård compression state. This produces a different extended message rather than a collision, but it defeats naive secret-prefix MACs such as H(secret || message).

HMAC avoids this attack by using separate inner and outer keys:

HMAC_K(M) = H((K' ⊕ opad) || H((K' ⊕ ipad) || M))

Here, K' is the key zero-padded to the block size; a key longer than the block size is first replaced by its digest, which is then zero-padded. New systems should normally use HMAC-SHA-256 rather than HMAC-SHA-1.

Practical Impact and Modern Alternatives

Scenario Risk with MD5 or SHA-1 Preferred choice
TLS certificates Legacy certificate-signature schemes can be undermined by collision attacks SHA-256 certificates and modern TLS
Code signing Colliding artifacts can undermine systems that trust only a digest SHA-256 plus an Ed25519 or other modern signature
Password storage Fast generic digests permit high-speed guessing and are not password KDFs A password KDF with a unique salt
File checksums Adversarial collisions can replace an artifact SHA-256, or BLAKE3 where appropriate
  • SHA-2: SHA-256, SHA-384, and SHA-512 remain widely supported for signatures and integrity.

  • SHA-3: Fixed-output variants use the Keccak sponge construction and are not vulnerable to Merkle–Damgård length extension. SHAKE is a separately standardized extendable-output function.

  • For password hashing, use Argon2id, bcrypt, scrypt, or PBKDF2-HMAC-SHA-256 with a unique salt and appropriate work factor.

Hash-Table Context

  • A hash function maps a key to a bucket. The load factor, commonly number_of_entries / bucket_count, measures occupancy. When it crosses an implementation threshold, the table is resized and every entry is rehashed into a larger bucket array.

  • Separate chaining keeps a list of entries in each bucket. Open addressing stores entries directly in the array and handles collisions by probing other slots using linear probing, quadratic probing, or double hashing.

  • Resizing costs O(n) for n entries but makes insertion O(1) amortized over a sequence of insertions.

  • CPython 3.12’s dict uses open addressing and preserves insertion order, a language guarantee since Python 3.7. A set stores keys in a hash table.

  • Dictionary keys must be hashable. Lists are mutable and unhashable, whereas tuples are hashable when all their elements are hashable.

  • Lookup, insertion, and deletion take O(1) best case, O(1) average case with constant-time hashing and bounded load, and O(n) worst case under pathological collisions. Hashing a k-byte key additionally takes O(k).

  • Space is O(n) for the bucket array and stored entries, plus O(1) auxiliary recursion stack; the input itself is not counted.

Interview Tips

  • Distinguish collision, preimage, and second-preimage resistance; they are separate properties.

  • MD5 can be acceptable for non-adversarial checksums or deduplication, but not where an attacker can manipulate inputs. Do not use fixed public MD5 or SHA-1 for attacker-controlled hash-table keys; consider a keyed hash such as SipHash.

  • MD5 was never a NIST-approved hash; NIST deprecated SHA-1 for digital signatures in 2011, and major browsers ended trust in SHA-1 certificates in 2017.

  • Watch bucket-index bounds during probing and resizing, and never mutate a key after insertion. Common follow-ups ask about load factor, resize thresholds, collision strategy, and expected versus worst-case performance.

21

How to detect linked list cycles using a hash table?

Hash-table cycle detection tracks the identity of every visited node. If traversal reaches a node already recorded in the hash table, the linked list contains a cycle. Here, a “cyclic list” means a linked list whose next pointers eventually revisit an earlier node.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm traverses the linked list one node at a time:

  1. Create an empty hash table for visited nodes.

  2. Calculate the current node’s identity, such as id(current).

  3. Check whether that identity is already in the table.

  4. If it exists, return True because the node was visited before.

  5. Otherwise, insert its identity and follow current.next.

  6. If next becomes None, return False.

Node identity matters rather than node value. Two different nodes containing "A" do not create a cycle merely because their values match.

Hash Table Internals

A hash table contains buckets, and a hash function maps each key to a bucket index:

  • Buckets: The table stores a collection of buckets, with each bucket containing the keys assigned to it.

  • Hash function: hash(key) % capacity converts a key into an index. The implementation below uses id(node), an integer identifying the node while it remains alive.

  • Load factor: This is size / capacity. The sample table resizes when its load factor would exceed 0.75.

  • Resizing and rehashing: When the table grows, its capacity doubles and every key is recalculated and inserted into the new bucket array. A resize costs O(n), but the cost is spread across insertions, making insertion O(1) amortized.

  • Separate chaining: The sample implementation stores colliding keys in a list within the same bucket.

Collision strategy How collisions are handled Trade-off
Separate chaining Multiple keys share a bucket Simple to implement, but long chains increase lookup time
Linear probing Check consecutive buckets Cache-friendly, but primary clustering can occur
Quadratic probing Check buckets at increasing square offsets Reduces primary clustering but uses more probes
Double hashing Use a second hash function for the probe sequence Distributes keys more evenly

Python’s dict uses open addressing and preserves insertion order, guaranteed since Python 3.7. Python’s set is also hash-table based. For an interview implementation, the built-in set is usually sufficient unless the interviewer specifically requests a custom hash table.

Hash-table keys must be hashable. Lists are mutable and therefore unhashable, while tuples can be used as keys when all their elements are hashable.

Example Walkthrough

For the cycle A → B → C → A:

Step Current node Already visited? Action
1 A No Add A
2 B No Add B
3 C No Add C
4 A Yes Return True

Complexity

For n reachable nodes:

  • Best case: O(1), such as when a self-cycle is detected after a constant number of operations.

  • Average case: O(n), because the traversal visits at most n distinct nodes and each hash-table operation takes O(1) on average. An acyclic list with n nodes takes O(n).

  • Worst case: O(n²), because a hash-table operation can take O(n) if all keys collide into one bucket.

  • Space: O(n) auxiliary space for the hash table. The input nodes are not counted, and no recursion stack is used because the traversal is iterative.

An individual hash-table lookup, insertion, or deletion takes O(1) best and average time, but O(n) worst-case time.

Code Example

from __future__ import annotations


class Node:
    def __init__(self, value: object, next_node: Node | None = None) -> None:
        self.value = value
        self.next = next_node


class HashSet:
    """Separate-chaining hash set for integer keys."""

    def __init__(self, capacity: int = 8) -> None:
        if capacity < 1:
            raise ValueError("capacity must be positive")

        self._capacity = capacity
        self._threshold = capacity * 3 // 4
        self._buckets: list[list[int]] = [[] for _ in range(capacity)]
        self._size = 0

    def _index(self, key: int) -> int:
        return hash(key) % self._capacity

    def contains(self, key: int) -> bool:
        return key in self._buckets[self._index(key)]

    def add(self, key: int) -> None:
        bucket = self._buckets[self._index(key)]
        if key in bucket:
            return

        bucket.append(key)
        self._size += 1

        if self._size > self._threshold:
            self._resize()

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._capacity *= 2
        self._threshold = self._capacity * 3 // 4
        self._buckets = [[] for _ in range(self._capacity)]

        # Rehash every existing key using the new capacity.
        for bucket in old_buckets:
            for key in bucket:
                self._buckets[self._index(key)].append(key)


def has_cycle(head: Node | None) -> bool:
    """Return whether the linked list contains a cycle."""
    visited = HashSet()
    current = head

    while current is not None:
        node_id = id(current)

        if visited.contains(node_id):
            return True

        visited.add(node_id)
        current = current.next

    return False


# Example: A -> B -> C -> A
first = Node("A")
second = Node("B")
third = Node("C")
first.next = second
second.next = third
third.next = first

print(has_cycle(first))  # True

Common Pitfalls

  • Using values instead of identities: Repeated values do not indicate a repeated node.

  • Forgetting the empty case: has_cycle(None) correctly returns False.

  • Self-cycles: A node whose next points to itself must return True.

  • Hashability: Use id(node) or hashable node objects; lists cannot be hash-table keys.

  • Input assumptions: Sorting is irrelevant to cycle detection, and negative values have no effect because node identity is used.

  • Graph extensions: A disconnected graph requires checking each component separately; the function above handles one linked-list chain.

  • Recursion: An iterative solution avoids Python’s recursion-depth limit.

22

Remove duplicate values from an unsorted linked list using a hash table

A hash table tracks values already encountered while traversing the linked list, allowing each duplicate to be removed in average constant time. Keep the first occurrence of every value so the original relative order is preserved.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hash Tables Work

A hash table stores keys in an array of buckets:

  1. A hash function converts the key into an integer.

  2. That integer determines the bucket index.

  3. If two keys produce the same index, a collision occurs.

The implementation below uses separate chaining, where each bucket is a list containing all keys that hash to that index. Other common collision strategies include:

  • Open addressing with linear probing: check the next bucket sequentially.

  • Quadratic probing: check buckets using squared offsets.

  • Double hashing: use a second hash function to determine the probe sequence.

The load factor is:

load factor = number of stored keys / number of buckets

When the load factor exceeds a threshold, the table resizes by allocating a larger bucket array and rehashing every key. Rehashing is amortized O(1) per insertion because the table grows geometrically.

Algorithm

For each node:

  • If its value is already in the hash table, bypass the node by linking its predecessor directly to its successor.

  • Otherwise, insert the value into the hash table and advance the predecessor.

  • Always move the current pointer to the next node.

The traversal works for unsorted, already-sorted, and partially sorted lists because it does not depend on ordering.

For the list 1 -> 2 -> 1 -> 3 -> 2:

  1. Visit 1: it is unseen, so keep it and insert it into the table.

  2. Visit 2: it is unseen, so keep it and insert it into the table.

  3. Visit the second 1: it is a duplicate, so link the first 2 directly to 3.

  4. Visit 3: it is unseen, so keep it and insert it into the table.

  5. Visit the final 2: it is a duplicate, so link 3 directly to None.

The resulting list is 1 -> 2 -> 3.

Complexity

Assume a reasonable hash distribution and controlled load factor:

Operation Best case Average case Worst case
Hash-table lookup O(1) O(1) O(n)
Hash-table insertion O(1) O(1) O(n)
Hash-table deletion O(1) O(1) O(n)
Entire linked-list algorithm O(n) O(n) O(n²)

The average-case linked-list complexity is O(n) because each node requires a constant number of hash-table operations. The worst case is O(n²) when many values collide in one bucket, making each lookup or insertion potentially linear.

Auxiliary space is O(n) for the hash table and cycle-detection set. The input linked list is not counted, and the algorithm is iterative, so no recursion stack is used.

Code Example

from __future__ import annotations

from collections.abc import Hashable
from dataclasses import dataclass


@dataclass(slots=True)
class Node:
    value: Hashable
    next: Node | None = None


class HashTable:
    """A hash table using separate chaining."""

    def __init__(
        self,
        initial_capacity: int = 8,
        max_load_factor: float = 0.75,
    ) -> None:
        if initial_capacity < 1:
            raise ValueError("initial_capacity must be positive")
        if max_load_factor <= 0:
            raise ValueError("max_load_factor must be positive")

        self._buckets: list[list[Hashable]] = [
            [] for _ in range(initial_capacity)
        ]
        self._size = 0
        self._max_load_factor = max_load_factor

    def _index(self, key: Hashable) -> int:
        return hash(key) % len(self._buckets)

    def contains(self, key: Hashable) -> bool:
        bucket = self._buckets[self._index(key)]
        return any(existing == key for existing in bucket)

    def put(self, key: Hashable) -> None:
        if self.contains(key):
            return

        next_load_factor = (self._size + 1) / len(self._buckets)
        if next_load_factor > self._max_load_factor:
            self._resize()

        self._buckets[self._index(key)].append(key)
        self._size += 1

    def _resize(self) -> None:
        new_capacity = len(self._buckets) * 2
        new_buckets: list[list[Hashable]] = [
            [] for _ in range(new_capacity)
        ]

        for bucket in self._buckets:
            for key in bucket:
                new_index = hash(key) % new_capacity
                new_buckets[new_index].append(key)

        self._buckets = new_buckets


def remove_duplicates(head: Node | None) -> Node | None:
    """Remove repeated hashable values, keeping the first occurrence."""
    table = HashTable()
    dummy = Node(0, head)

    previous = dummy
    current = head
    seen_node_ids: set[int] = set()

    while current is not None:
        node_id = id(current)
        if node_id in seen_node_ids:
            raise ValueError("The linked list contains a cycle")
        seen_node_ids.add(node_id)

        if table.contains(current.value):
            previous.next = current.next
        else:
            table.put(current.value)
            previous = current

        current = current.next

    return dummy.next


def to_list(head: Node | None) -> list[Hashable]:
    values: list[Hashable] = []
    current = head

    while current is not None:
        values.append(current.value)
        current = current.next

    return values


# Example:
head = Node(1, Node(2, Node(1, Node(3, Node(2)))))
result = remove_duplicates(head)
print(to_list(result))
# [1, 2, 3]

Common Pitfalls

  • Unhashable values: Lists cannot be hash-table keys because they are mutable and unhashable. Tuples can be used when all their elements are hashable.

  • Mutation during traversal: Save current.next or update previous.next before advancing, otherwise nodes may be skipped.

  • Cycle handling: The example detects and rejects cyclic lists rather than looping forever.

  • Empty and one-element lists: Both are handled naturally and return None and the original node, respectively.

  • Negative values: Negative integers work normally; the modulo operation still selects a valid nonnegative bucket index.

  • Production Python code: Python’s set would provide the same average-case behavior with less code. CPython’s dict uses open addressing and preserves insertion order, guaranteed since Python 3.7; a set is implemented as a hash table of keys.

23

Find common elements in linked lists using a hash table

A hash table supports fast membership checks while the lists are traversed. Under standard set-intersection semantics, the result contains each distinct value found in both lists, preserving its first occurrence in the first list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Traverse the second list and insert every value into a hash-based set.

  2. Traverse the first list.

  3. If a value exists in the set, append it to the result.

  4. Track emitted values so duplicates in either list do not produce duplicate result nodes.

The algorithm does not require the lists to be sorted or to have the same length.

Hash Table Internals

  • Hash function: Converts a key, such as an integer, into a numeric hash used to select a bucket.

  • Buckets: Store the keys assigned to each hash-table position.

  • Load factor: Represents the approximate number of stored keys relative to the number of buckets. A high load factor increases collisions and can trigger resizing.

  • Resizing: Allocates a larger table and rehashes the existing keys. Although one resize can take linear time, spreading its cost across insertions gives amortized constant-time insertion.

  • Collision handling: Two keys may hash to the same bucket.

Collision strategy How it works Main characteristic
Separate chaining Each bucket stores a list of colliding keys Simple, but a long bucket becomes slow
Linear probing Searches consecutive buckets Can cause primary clustering
Quadratic probing Searches using squared offsets Reduces clustering but needs suitable table sizes
Double hashing Uses a second hash for the probe step Usually distributes keys more evenly

CPython’s dict and set use open addressing internally. Dictionaries also preserve insertion order, guaranteed since Python 3.7.

Code Example

from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class ListNode:
    value: int
    next: ListNode | None = None


def iter_nodes(head: ListNode | None) -> Iterator[ListNode]:
    current = head
    while current is not None:
        yield current
        current = current.next


def build_linked_list(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy

    for value in values:
        tail.next = ListNode(value)
        tail = tail.next

    return dummy.next


def find_common_elements(
    first_head: ListNode | None,
    second_head: ListNode | None,
) -> ListNode | None:
    """Return distinct common values in first-list order."""
    if first_head is None or second_head is None:
        return None

    # A set is a hash table containing keys.
    second_values = {node.value for node in iter_nodes(second_head)}
    emitted_values: set[int] = set()

    dummy = ListNode(0)
    tail = dummy
    current = first_head

    while current is not None:
        if (
            current.value in second_values
            and current.value not in emitted_values
        ):
            tail.next = ListNode(current.value)
            tail = tail.next
            emitted_values.add(current.value)

        current = current.next

    return dummy.next


first = build_linked_list([1, 2, 3, 2, 4])
second = build_linked_list([2, 3, 5, 2])

result = find_common_elements(first, second)
print([node.value for node in iter_nodes(result)])  # [2, 3]

Complexity

Let n be the first list’s length, m the second list’s length, d the number of distinct values in the second list, and k the number of distinct common values.

  • Best case: Θ(n + m) when both lists are nonempty because both are scanned; Θ(1) when either list is empty.

  • Average/expected case: Θ(n + m), since each hash-table insertion and membership check takes O(1) expected time.

  • Worst case: Θ(m² + nm) for nonempty lists in a pathological collision pattern, because a set operation may inspect Θ(m) entries.

  • Auxiliary space: Θ(d + k) for the two sets, excluding the input lists and returned list; the worst case is Θ(m + k).

  • Output space: Θ(k).

  • Recursion stack: Θ(1), because the implementation is iterative.

Hash-table insertion is amortized O(1) when resizing is included.

Walkthrough

For 1 → 2 → 3 → 2 → 4 and 2 → 3 → 5 → 2:

  1. Store the second list’s values in a set: {2, 3, 5}.

  2. Visit 1: it is not in the set, so skip it.

  3. Visit 2: it is common, so append 2.

  4. Visit 3: it is common, so append 3.

  5. Visit the second 2: skip it because 2 was already emitted.

  6. Visit 4: skip it.

The result is 2 → 3.

Common Pitfalls

  • Duplicate semantics: Decide whether duplicates matter. This implementation returns each common value only once; a different requirement might require matching duplicate counts.

  • Mutating inputs: The implementation only creates new result nodes and does not modify either input list.

  • Hashable keys: Python hash-table keys must be hashable. Lists cannot be keys because they are mutable; tuples can be keys when their elements are hashable.

  • Edge cases: Empty lists return None, single-element lists work, negative values are valid, and the lists need not be sorted. Output order follows the first list.

  • Assumptions: Standard linked lists are acyclic. Cyclic lists require separate cycle detection, while graph concepts such as disconnected components do not apply.

24

How can a hash table pair socks by color?

A hash table pairs socks efficiently by recording the first unmatched sock of each color. When another sock of the same color appears, the two socks can be matched immediately, avoiding an exhaustive comparison of every pair.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Treat each sock’s color or type as a key and its position in the pile as the value.

For each sock:

  1. Compute the color’s hash value.

  2. Look for that color in the hash table.

  3. If it is absent, store the current sock’s index.

  4. If it is already present, remove the stored entry and create a pair.

  5. A sock left in the table after processing the pile has no matching partner.

Hash Table Internals

  • Hash function: Converts a key into an integer. The example uses Python’s hash() and a bit mask to select a bucket.

  • Buckets: The hash table contains a list of buckets. This implementation uses separate chaining, so colliding keys are stored in the same bucket’s list.

  • Load factor: The number of stored entries divided by the number of buckets. The implementation resizes when the load factor exceeds 0.75.

  • Resizing: When the table grows, it doubles its capacity and rehashing every key into a new bucket. Resizing is occasionally expensive, but its cost is amortized across insertions, giving amortized O(1) insertion.

  • Collision handling: Separate chaining stores collisions in bucket lists. Open addressing instead stores all entries in one array and uses techniques such as linear probing, quadratic probing, or double hashing.

Python’s dict uses open addressing and preserves insertion order, guaranteed since Python 3.7. A set is also hash-based and stores keys.

Keys must be hashable. Integers and strings can be keys, and an immutable tuple can be a key when all its elements are hashable. Lists cannot be keys because they are mutable and therefore unhashable.

Algorithm Walkthrough

Given [4, 7, 4, 9, 7]:

Sock index Color Unmatched colors New pair
0 4 {4: 0} None
1 7 {4: 0, 7: 1} None
2 4 {7: 1} (0, 2)
3 9 {7: 1, 9: 3} None
4 7 {9: 3} (1, 4)

The final unmatched sock is at index 3.

Complexity

Approach Time Extra space Use when
Compare every pair O(n²) best, average, and worst case O(1) Very small inputs
Hash table O(n) best and average; O(n²) worst case O(n) General pairing
  • Best case: O(n) because every sock must be inspected, and the hash distribution is good.

  • Average case: O(n) because each insertion, lookup, and deletion takes O(1) on average.

  • Worst case: O(n²) when many keys collide in the same bucket.

  • Space: O(n) auxiliary space for the hash table. The input pile is not counted, and no recursion is used, so recursion-stack space is O(1).

Code Example

from collections.abc import Hashable

_MISSING = object()


class _ChainingHashMap:
    def __init__(self, initial_capacity: int = 8) -> None:
        if initial_capacity < 2:
            raise ValueError("initial_capacity must be at least 2")

        self._capacity = 1 << (initial_capacity - 1).bit_length()
        self._load_factor_limit = 0.75
        self._size = 0
        self._buckets: list[list[tuple[Hashable, int]]] = [
            [] for _ in range(self._capacity)
        ]

    def _bucket_index(self, key: Hashable) -> int:
        return hash(key) & (self._capacity - 1)

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]

        for bucket in old_buckets:
            for key, value in bucket:
                self._buckets[self._bucket_index(key)].append((key, value))

    def get(self, key: Hashable) -> int | object:
        bucket = self._buckets[self._bucket_index(key)]

        for stored_key, value in bucket:
            if stored_key == key:
                return value

        return _MISSING

    def put(self, key: Hashable, value: int) -> None:
        bucket = self._buckets[self._bucket_index(key)]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[position] = (key, value)
                return

        bucket.append((key, value))
        self._size += 1

        if self._size / self._capacity > self._load_factor_limit:
            self._resize()

    def remove(self, key: Hashable) -> None:
        bucket = self._buckets[self._bucket_index(key)]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(position)
                self._size -= 1
                return


def pair_socks(socks: list[int]) -> tuple[list[tuple[int, int]], list[int]]:
    """Return matching sock index pairs and indices of unmatched socks."""
    unmatched_by_color = _ChainingHashMap()
    pairs: list[tuple[int, int]] = []

    for index, color in enumerate(socks):
        previous_index = unmatched_by_color.get(color)

        if previous_index is _MISSING:
            unmatched_by_color.put(color, index)
        else:
            unmatched_by_color.remove(color)
            pairs.append((previous_index, index))

    unmatched = [
        index
        for index, color in enumerate(socks)
        if unmatched_by_color.get(color) == index
    ]

    return pairs, unmatched


pair_socks([4, 7, 4, 9, 7])
# ([(0, 2), (1, 4)], [3])

Common Pitfalls

  • Empty input: The result is ([], []).

  • One sock: It remains unmatched, so the result is ([], [0]).

  • Duplicate colors: Pairs are created in encounter order; an odd number of socks of one color leaves exactly one unmatched sock.

  • Negative color values: They work normally because they are valid hashable keys.

  • Already sorted input: No special handling is needed; correctness and complexity remain unchanged.

  • Assuming O(1) is guaranteed: Hash-table operations are O(1) on average, not in the worst case.

  • Using mutable keys: Lists and dictionaries cannot be hash-table keys.

  • Mutating the input: The implementation only reads the pile and returns new result lists.

25

How are hash tables used in caching implementations?

A hash table maps cache keys to stored values, allowing repeated requests to find cached data without recomputing it. Lookup, insertion, and deletion take O(1) time on average when the load factor remains bounded.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hash Tables Support Caching

A cache normally performs four operations:

  1. Lookup: Check whether a key exists.

  2. Hit: Return the cached value immediately.

  3. Miss: Compute the value using the underlying operation.

  4. Insert: Store the new value and apply an eviction policy when the cache is full.

The hash function converts a key into a bucket index. Because keys are hashed rather than compared linearly, a hit avoids scanning the entire cache.

Internals, Collisions, and Resizing

A typical hash table contains:

  • Hash function: Maps a key to an integer, commonly hash(key).

  • Buckets: Array positions where entries are stored.

  • Load factor: entry_count / bucket_count. A high load factor increases collisions and lookup time.

  • Resize operation: When the load factor exceeds a threshold, the table allocates more buckets and rehashes every key.

Different hash tables handle collisions differently:

Strategy How collisions are handled
Separate chaining Each bucket stores a list of entries
Linear probing Checks the next bucket sequentially
Quadratic probing Checks buckets using squared offsets
Double hashing Uses a second hash function to calculate the probe sequence

Python’s dict uses open addressing and preserves insertion order, guaranteed since Python 3.7. A Python set is also a hash table, but stores keys rather than key-value pairs.

Dictionary keys must be hashable. Tuples of hashable elements can be keys, while lists cannot because they are mutable and unhashable.

Complexity

For a cache containing n entries:

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) O(1) amortized O(n)
Delete O(1) O(1) O(n)

The average assumes good hash distribution and a controlled load factor. The worst case occurs when many entries collide into one bucket or chain.

Resizing takes O(n) when it occurs, but doubling the bucket count makes insertion O(1) amortized across a sequence of insertions.

Space usage is O(n) for entries, buckets, and eviction metadata. The recursion stack uses O(1) space because these operations are iterative. The input is not counted separately, although the memory occupied by cached values still depends on their size.

Typical Use Case

An API gateway can cache responses using a key such as:

("GET", url, query_parameters, tenant_id, locale)

On a hit, the gateway returns the stored response. On a miss, it calls the service and stores the result with a time-to-live. Including tenant_id and authorization-related information in the key prevents one user’s data from being returned to another.

Code Example

This implementation uses separate chaining, supports resizing, and applies FIFO eviction.

from collections import deque
from collections.abc import Hashable
from typing import Generic, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class _HashMap(Generic[K, V]):
    """Hash map using separate chaining."""

    def __init__(self) -> None:
        self._buckets: list[list[tuple[K, V]]] = [[]]
        self._size = 0

    def _index(self, key: K) -> int:
        return hash(key) % len(self._buckets)

    def get(self, key: K) -> tuple[bool, V | None]:
        """Return whether the key exists and its stored value."""
        for stored_key, value in self._buckets[self._index(key)]:
            if stored_key == key:
                return True, value
        return False, None

    def set(self, key: K, value: V) -> None:
        """Insert or update a key."""
        bucket = self._buckets[self._index(key)]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[position] = (key, value)
                return

        bucket.append((key, value))
        self._size += 1

        if self._size > len(self._buckets) * 0.75:
            self._resize()

    def delete(self, key: K) -> bool:
        """Delete a key, returning whether it existed."""
        bucket = self._buckets[self._index(key)]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                del bucket[position]
                self._size -= 1
                return True

        return False

    def _resize(self) -> None:
        """Double the bucket count and rehash every entry."""
        old_buckets = self._buckets
        self._buckets = [[] for _ in range(len(old_buckets) * 2)]

        for bucket in old_buckets:
            for key, value in bucket:
                self._buckets[self._index(key)].append((key, value))


class FIFOCache(Generic[K, V]):
    """Bounded cache using a hash map and FIFO eviction."""

    def __init__(self, max_size: int) -> None:
        if max_size <= 0:
            raise ValueError("max_size must be positive")

        self._max_size = max_size
        self._data = _HashMap[K, V]()
        self._insertion_order: deque[K] = deque()

    def get(self, key: K) -> V | None:
        """Return the cached value or None for a miss."""
        found, value = self._data.get(key)
        return value if found else None

    def put(self, key: K, value: V) -> None:
        """Store a value and evict the oldest entry when full."""
        found, _ = self._data.get(key)
        if found:
            self._data.set(key, value)
            return

        self._data.set(key, value)
        self._insertion_order.append(key)

        if len(self._insertion_order) > self._max_size:
            oldest_key = self._insertion_order.popleft()
            self._data.delete(oldest_key)


cache = FIFOCache[str, int](max_size=3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.put("d", 4)  # Evicts "a", the oldest insertion.

print(cache.get("a"), cache.get("b"), cache.get("d"))
# Output: None 2 4

Common Pitfalls

  • Ignoring the load factor: A table that never resizes develops long collision chains.

  • Using mutable keys: Lists and dictionaries cannot be dictionary keys.

  • Sharing sensitive cache entries: Include tenant, user, or permission scope in the key.

  • Ignoring expiration: Cached data can become stale; production caches commonly support TTLs.

  • Confusing FIFO with LRU: The example evicts the oldest insertion. An LRU cache updates recency on every hit.

  • Using None as an ambiguous miss marker: If None is a valid cached value, return a (found, value) result or use a unique sentinel.

26

How to check whether two strings are anagrams using a hash table?

A hash table can store the frequency of each character in the first string, then consume those counts while scanning the second string. The strings are anagrams exactly when their lengths match and every character occurs the same number of times in both.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Compare the string lengths. If they differ, the strings cannot be anagrams.

  2. Insert each character from the first string into a hash table and increment its count.

  3. For every character in the second string:

  4. If its count is missing or zero, return False.

  5. Otherwise, decrement its count.

  6. If every character is matched successfully, return True.

For example, for "listen" and "silent", the initial counts are l=1, i=1, s=1, t=1, e=1, and n=1. Each character in "silent" consumes one matching count, so the result is True.

Hash Table Internals

  • Hash function: Converts a character key into a numeric hash used to select a bucket or initial table position.

  • Buckets: The hash table contains a fixed or growable array of slots. Each bucket stores one entry in open addressing or a collection of entries in separate chaining.

  • Load factor: The ratio of stored entries to available buckets. As it increases, collisions become more likely.

  • Resizing and rehashing: When the load factor becomes too high, the table allocates a larger bucket array and reinserts entries using their hashes. This makes individual insertions amortized O(1) because occasional expensive resizes are spread across many operations.

  • Collisions: Different keys may produce the same initial hash position.

Collision strategy How it works Main trade-off
Separate chaining Each bucket stores a list of colliding entries Simple but uses additional memory for bucket lists
Linear probing Checks the next bucket sequentially Can cause primary clustering
Quadratic probing Checks buckets using a quadratic sequence Reduces clustering but may probe empty slots inefficiently
Double hashing Uses another hash function to determine the probe step Usually distributes keys well

Python’s dict uses open addressing, preserves insertion order, and supports amortized O(1) insertions. Dictionary keys must be hashable: strings and tuples containing hashable elements can be keys, while lists cannot because they are mutable.

Code Example

def are_anagrams(first: str, second: str) -> bool:
    """Return whether two strings contain identical characters and counts."""
    if len(first) != len(second):
        return False

    counts: dict[str, int] = {}

    for character in first:
        counts[character] = counts.get(character, 0) + 1

    for character in second:
        remaining = counts.get(character, 0)
        if remaining == 0:
            return False
        counts[character] = remaining - 1

    return True


print(are_anagrams("listen", "silent"))  # True

Complexity and Edge Cases

Let n and m be the string lengths and k the number of distinct characters stored in the table.

  • Best time: O(1) when the lengths differ immediately; otherwise O(n + m) because the characters must be examined.

  • Average time: O(n + m) because each hash-table operation takes O(1) on average and there are O(n + m) operations.

  • Worst time: O(N²) where N = n + m; theoretically, each hash-table operation can degrade to O(N) under severe collisions, and there are O(N) operations.

  • Auxiliary space: O(k + 1) for the hash table. Input strings are not counted, and there is no recursion stack.

  • Empty strings: Two empty strings are anagrams; one empty and one nonempty are not.

  • One character: Matching characters produce True; different characters produce False.

  • Duplicates: Counts correctly reject strings such as "aabb" and "abbb".

  • Case and whitespace: The algorithm is case-sensitive and treats whitespace as a character.

  • Unicode: Characters are compared by Python Unicode code point. Apply explicit normalization beforehand if canonically equivalent representations should match.

Common Pitfalls

  • Comparing only character sets and ignoring duplicate counts can incorrectly classify "aabb" and "abbb" as anagrams.

  • Using lowercase conversion changes the original matching rules; normalize only when the problem requires it.

  • Assuming a set is sufficient overlooks frequency differences.

  • Failing to compare lengths can allow missing characters to be missed.

  • Interviewers may follow up by asking for case-insensitive matching, Unicode normalization, or an implementation using separate chaining instead of Python’s dict.

27

How do you implement autocomplete using a hash table in Python?

Autocomplete can be implemented with a hash table that maps each prefix to the words beginning with it. The example below uses a custom separate-chaining table for the prefix index and ranks matches by descending frequency at query time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For every word, generate all its prefixes and add the word to the corresponding prefix bucket. For example, python is stored under p, py, pyt, pyth, and python.

When a user types py, the hash table retrieves the bucket for py and returns the highest-frequency matches. Ties are ordered lexicographically.

  • Hash function: Python’s built-in hash() converts a hashable key into an integer.

  • Buckets: The table contains an array of buckets; separate chaining stores colliding entries in lists.

  • Load factor: The table resizes when size / capacity exceeds 0.75.

  • Resizing: Capacity doubles, and every key is rehashed into the new bucket array.

  • Collision alternatives: Open addressing can use linear probing, quadratic probing, or double hashing. CPython’s built-in dict and set use open addressing; dictionaries preserve insertion order, guaranteed since Python 3.7.

Complexity

Let L be the added word’s length, P the query prefix length, E the number of entries in the outer prefix table, C the number of matching candidates, and k the requested result count. Standard hash-table bounds treat stored-key hashing and equality as O(1); string slicing and normalization are counted separately.

Operation Best case Average case Worst case Space
Hash-table lookup O(1) O(1) O(E) O(1) auxiliary
Hash-table insertion O(1) O(1) amortized O(E) O(E) transiently during resizing
suggest(prefix, limit) O(P + C log(k + 1)) O(P + C log(k + 1)) O(P + E + C log(k + 1)) O(min(C, k)) auxiliary
add(word) O(L²) O(L²) amortized O(L² + LE) O(L²) persistent space; O(E) transiently during resizing

Creating all prefixes requires O(L²) characters and work because their lengths sum to 1 + 2 + ... + L. The complete index uses O(Σ Lᵢ²) space including stored prefix text, excluding the original input. No recursion stack is used.

Code Example

import heapq
from collections.abc import Hashable, Iterator
from typing import Generic, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class ChainingHashTable(Generic[K, V]):
    """A hash table using separate chaining and automatic resizing."""

    def __init__(self, initial_capacity: int = 8) -> None:
        if initial_capacity < 1:
            raise ValueError("initial_capacity must be positive")

        self._capacity = initial_capacity
        self._buckets: list[list[tuple[K, V]]] = [
            [] for _ in range(initial_capacity)
        ]
        self._size = 0

    def _index(self, key: K) -> int:
        return hash(key) % self._capacity

    def get(self, key: K) -> V | None:
        for stored_key, value in self._buckets[self._index(key)]:
            if stored_key == key:
                return value
        return None

    def put(self, key: K, value: V) -> None:
        bucket = self._buckets[self._index(key)]

        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[index] = (key, value)
                return

        if (self._size + 1) / self._capacity > 0.75:
            self._resize()

        self._buckets[self._index(key)].append((key, value))
        self._size += 1

    def items(self) -> Iterator[tuple[K, V]]:
        for bucket in self._buckets:
            yield from bucket

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]

        for bucket in old_buckets:
            for key, value in bucket:
                self._buckets[self._index(key)].append((key, value))


class Autocomplete:
    """Provide frequency-ranked autocomplete suggestions."""

    def __init__(self) -> None:
        self._prefixes: ChainingHashTable[str, dict[str, int]] = (
            ChainingHashTable()
        )
        self._frequencies: ChainingHashTable[str, int] = ChainingHashTable()

    def add(self, word: str, frequency: int = 1) -> None:
        """Add or update a word and its prefix suggestions."""
        normalized_word = word.casefold().strip()

        if not normalized_word:
            raise ValueError("word must not be empty")
        if frequency <= 0:
            raise ValueError("frequency must be positive")

        self._frequencies.put(normalized_word, frequency)

        for prefix_length in range(1, len(normalized_word) + 1):
            prefix = normalized_word[:prefix_length]
            bucket = self._prefixes.get(prefix)

            if bucket is None:
                bucket = {}
                self._prefixes.put(prefix, bucket)

            bucket[normalized_word] = frequency

    def suggest(self, prefix: str, limit: int = 5) -> list[str]:
        """Return up to limit suggestions matching the prefix."""
        if limit < 0:
            raise ValueError("limit must not be negative")
        if limit == 0:
            return []

        normalized_prefix = prefix.casefold().strip()

        if normalized_prefix:
            bucket = self._prefixes.get(normalized_prefix)
            suggestions = bucket.items() if bucket is not None else ()
        else:
            suggestions = self._frequencies.items()

        ranked = heapq.nsmallest(
            limit,
            suggestions,
            key=lambda item: (-item[1], item[0]),
        )
        return [word for word, _ in ranked]


def autocomplete_example() -> list[str]:
    """Build a small index and return its top two suggestions."""
    autocomplete = Autocomplete()
    autocomplete.add("python", frequency=10)
    autocomplete.add("pytest", frequency=7)
    autocomplete.add("java", frequency=8)
    return autocomplete.suggest("py", limit=2)


print(autocomplete_example())
# ['python', 'pytest']

Common Pitfalls

  • Unhashable keys: Lists cannot be dictionary or hash-table keys because they are unhashable. Tuples are hashable only when all their elements are hashable.

  • Duplicate words: Re-adding a word updates its frequency rather than creating duplicate suggestions.

  • Missing prefixes: Every prefix length must be indexed, not only complete words.

  • Empty input: Empty words are rejected, while an empty search prefix returns the most frequent words.

  • One element: A single indexed word is returned for its corresponding prefixes.

  • Invalid values: Frequencies must be positive, and limits must be nonnegative.

  • Poor hashing: A poorly distributed hash function can create long collision chains and degrade operations to O(E).

Interview Tips

  • Explain why resizing is amortized O(1) per inserted entry: doubling requires O(E) work only occasionally.

  • Compare separate chaining with open addressing, including probe sequences and deletion considerations.

  • Discuss how ranking by frequency, recency, or popularity changes the final selection step.

  • Mention that storing every prefix can consume substantial space; a trie is an alternative when prefix traversal is more important than direct hash-table lookup.

28

How can a hash table be used in a CDN implementation?

A hash table lets a CDN map a cache key to object metadata, a storage location, an origin, or another edge server. It enables fast request routing without scanning every cached object.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role in a CDN

A CDN commonly uses hash tables for several related tasks:

  • Cache lookup: Maps a normalized URL or cache key to cached content metadata, storage location, TTL, and validation information.

  • Origin routing: Maps a hostname, URL prefix, or cache key to the appropriate origin server.

  • Content placement: Maps a content digest such as sha256:abc123 to the object stored at a particular node or storage service.

  • Invalidation: Tracks objects affected by a purge request.

  • Deduplication: Ensures that identical content, identified by its digest, is stored or reused only once.

The hash table usually stores metadata and pointers rather than the complete content payload. Large objects remain in cache nodes or object storage.

Request Flow

For a request such as https://media.example.com/videos/intro.mp4, a simplified flow is:

  1. Normalize the URL into a cache key, usually media.example.com/videos/intro.mp4.

  2. Look up the key in the edge node’s cache hash table.

  3. On a cache hit, retrieve the object using its storage key and validate its TTL or ETag.

  4. On a cache miss, look up the origin or shielding server and fetch the content.

  5. Store the fetched object under its content digest and associate it with the request key.

In a distributed CDN, consistent hashing or a hash ring may additionally determine which cache node owns a key. That is separate from the ordinary hash table used for local metadata lookup.

Hash Table Internals

A hash function converts the cache key into an integer hash. A bucket index is derived from that hash, and the table searches the corresponding bucket if a collision occurs.

Collision strategy How it works Trade-off
Separate chaining Each bucket stores a list of entries with the same hash Simple to implement, but uses extra memory
Linear probing Checks (hash + i) mod table_size Cache-friendly but vulnerable to clustering
Quadratic probing Checks (hash + i²) mod table_size Reduces some clustering but may miss available slots
Double hashing Uses a second hash to determine the probe sequence Distributes keys well but costs an additional hash calculation

The load factor is the ratio of stored entries to available buckets. When it exceeds an implementation-defined threshold, the table resizes. Resizing allocates a larger structure and redistributes entries, giving insertion amortized O(1) performance over a sequence of operations.

Python dictionaries use open addressing and preserve insertion order, which has been guaranteed since Python 3.7. Dictionary keys must be hashable: tuples can be keys because they are immutable, while lists cannot because they are mutable and unhashable.

Complexity

Assuming constant-time key hashing and comparison:

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) O(1) amortized O(n)
Delete O(1) O(1) O(n)

The best case occurs when the target bucket is immediately available. The average case assumes a good hash function and reasonably balanced buckets. The worst case occurs when many keys collide and the table must inspect O(n) entries.

Hash-table space is O(n) for n stored entries. This excludes the input and the CDN’s content payloads; no recursive stack is used, so the stack contributes O(1) additional space.

Code Example

from dataclasses import dataclass
from urllib.parse import urlsplit


@dataclass(frozen=True)
class CacheEntry:
    storage_key: str
    etag: str | None = None


def resolve_content(
    url: str,
    cache: dict[str, CacheEntry],
    origins: dict[str, str],
) -> tuple[str, str]:
    """Resolve a URL to cached content or to its configured origin."""
    if not url.strip():
        raise ValueError("URL must not be empty")

    parsed = urlsplit(url)
    if parsed.scheme not in {"http", "https"} or parsed.hostname is None:
        raise ValueError("URL must use HTTP or HTTPS and include a hostname")

    host = parsed.hostname.lower()
    path = parsed.path or "/"
    cache_key = f"{host}{path}"

    cached_entry = cache.get(cache_key)
    if cached_entry is not None:
        return cached_entry.storage_key, "cache hit"

    origin = origins.get(cache_key)
    if origin is None:
        raise LookupError(f"No route exists for {cache_key}")

    return origin, "origin miss"


cache = {
    "media.example.com/videos/intro.mp4":
        CacheEntry("objects/sha256:abc123", "etag-42")
}
origins = {
    "media.example.com/videos/intro.mp4":
        "https://origin.example.net/videos/intro.mp4"
}

print(resolve_content(
    "https://MEDIA.example.com/videos/intro.mp4",
    cache,
    origins,
))
# Expected output: ('objects/sha256:abc123', 'cache hit')

Common Pitfalls

  • Cache-key ambiguity: Query strings, default ports, redirects, and trailing slashes must follow an explicit normalization policy. This example deliberately excludes query strings.

  • Invalid URLs: Empty, malformed, or unsupported URLs should be rejected before lookup.

  • Duplicate configuration keys: In a Python dictionary, a later assignment replaces the previous value.

  • Incorrect invalidation: Removing only the request-key entry may leave an orphaned content-addressed object.

  • Assuming worst-case O(1): Collision-heavy keys can degrade operations to O(n).

  • Unbounded metadata growth: TTLs, purging, and deduplication policies must prevent stale or orphaned entries from accumulating.

  • Irrelevant edge cases: Negative numbers, sorted input, disconnected graphs, and cycles do not apply to hash-table-based CDN routing.

29

HashMap vs HashTable differences in Java

The main difference is that HashMap is unsynchronized and allows null keys and values, while HashTable is synchronized and does not allow nulls. HashMap is the modern, recommended choice for single-threaded or externally synchronized use, whereas HashTable is a legacy class retained for backward compatibility.

Read full answer

Applies toJava 21

Core Differences

  • Synchronization: HashMap is not thread-safe, allowing faster access in single-threaded contexts; HashTable is synchronized, making it safe for concurrent use without external locking.

  • Null handling: HashMap permits one null key and multiple null values; HashTable throws a NullPointerException for null keys or values.

  • Performance: HashMap generally outperforms HashTable because it avoids the overhead of built-in synchronization.

  • Legacy status: HashMap was introduced in Java 1.2 as a replacement for HashTable, which dates back to Java 1.0.

Feature HashMap HashTable
Thread safety Not synchronized Synchronized
Null keys Allowed (one) Not allowed
Null values Allowed (multiple) Not allowed
Iterator Fail-fast Fail-fast
Performance Faster Slower due to locking

Internal Implementation

  • Hash function: Both use hashCode() and equals() to determine bucket placement.

  • Buckets: Both store entries in an array of buckets, resolving collisions via separate chaining.

  • Load factor: Both default to a load factor of 0.75, triggering resizing when exceeded.

  • Resizing: Both resize by doubling the table capacity and rehashing entries, which is amortized O(1) for insertions.

  • Collision handling: HashMap uses separate chaining with linked lists, converting to balanced trees when a bucket exceeds a threshold (Java 8+); HashTable uses simple linked lists without treeification.

Time and Space Complexity

  • Average case: O(1) for get, put, and remove, assuming a good hash function distributes keys evenly.

  • Worst case: O(n) when all keys collide into a single bucket, though HashMap mitigates this with treeified buckets.

  • Space: O(n) to store n entries, plus overhead for the underlying array and linked list nodes.

  • Load factor impact: A higher load factor reduces space but increases collision risk; the default 0.75 balances both.

When to Use Which

  • Use HashMap for most applications, especially single-threaded code or when you manage synchronization externally.

  • Use HashTable only when maintaining compatibility with legacy code that requires thread safety without external locking.

  • Consider ConcurrentHashMap for high-concurrency scenarios where you need thread safety without locking the entire map.

Common Pitfalls

  • Mutating input: Do not modify keys while they are in the map, as it can break hash consistency.

  • Null keys: Passing null to HashTable methods throws a NullPointerException; HashMap accepts them.

  • Concurrency: Using HashMap in a multi-threaded environment without synchronization can cause data corruption; prefer ConcurrentHashMap instead.

  • Follow-up: Interviewers often ask about ConcurrentHashMap or how to make HashMap thread-safe.

  • Iteration order: HashMap does not guarantee iteration order; use LinkedHashMap if order matters.

30

What is cuckoo hashing and when should you use it?

Cuckoo hashing stores each key in one of two possible locations, using two hash functions. When both locations are occupied, conflicting keys are relocated to their alternate locations, allowing lookups to examine only a small, fixed number of slots.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Cuckoo Hashing Works

  • Two hash tables and two choices: A key x has candidate positions h1(x) and h2(x), one in each table.

  • Buckets: Each table is an array of fixed-size slots. Each slot holds at most one key.

  • Collision handling: If one candidate slot is empty, the key is inserted there. Otherwise, an existing occupant is moved to its alternate position, possibly displacing another key.

  • Cycles: Relocations can form a cycle in which every key needs another key’s slot. Implementations detect this failure and may resize the tables or use additional hash functions.

  • Load factor: A common practical limit is about 0.5; exceeding it increases relocation and insertion failures.

  • Resizing: Tables grow and every key is rehashed. A resize costs O(n), but doubling the capacity makes insertion amortized O(1).

A small example:

  1. Insert "cat": it hashes to slot 2 in table 1 and slot 4 in table 2. Both are empty, so "cat" goes to slot 2 in table 1.

  2. Insert "dog": it hashes to slot 2 in table 1 and slot 4 in table 2. Slot 2 in table 1 is occupied by "cat", so "cat" is moved to its alternate slot (slot 4 in table 2). "dog" then occupies slot 2 in table 1.

Complexity

Assuming constant-time hashing and key comparison:

Operation Best Average Worst Reason
Lookup O(1) O(1) O(1) for direct two-slot cuckoo hashing Only two candidate slots are checked
Insert O(1) Expected O(1) O(n) A failed insertion may relocate many keys or rebuild the tables
Delete O(1) O(1) O(1) Removing a key requires checking two slots
Resize O(n) O(n) O(n) Every key is rehashed
  • Space: O(n), excluding the input; resizing temporarily requires O(n) additional space.

  • Generic hash tables using chaining or probing can degrade to O(n) per operation under pathological collisions. Direct-slot cuckoo lookup and deletion still inspect only two candidate positions.

Comparison and Advantages

Strategy Collision handling Trade-off
Separate chaining Store colliding keys in a bucket list Predictable but requires pointers and can create long lists
Linear/quadratic probing Search nearby slots in one array Simple, but linear probing creates clusters
Double hashing Use another hash to choose the probe sequence Reduces clustering, but each lookup performs multiple probes
Cuckoo hashing Relocate occupants to an alternate hash location Fast lookups and good cache locality; insertion can be expensive

Cuckoo hashing is advantageous when:

  • Lookups and deletions dominate the workload.

  • Low latency and cache efficiency are important.

  • Keys have well-distributed hashes and the load factor can be controlled.

It is less suitable for adversarial inputs, frequent insertion failures, or systems requiring guaranteed insertion without resizing.

Common Pitfalls

  • Unhashable keys: Lists cannot be dictionary or hash-set keys because they are mutable; tuples can be keys when all their elements are hashable.

  • Ignoring relocation cost: Lookup is fast, but insertion may move many keys.

  • Using a high load factor: More keys increase collisions, relocation, and insertion failures.

  • Assuming deterministic hashes are safe: Adversarial or correlated hashes can produce poor placement.

  • Interview follow-ups: Expect questions about cycle detection, rehashing, load-factor selection, tombstone handling, and comparisons with chaining and open addressing.

31

How do skip lists work compared with hash tables?

A skip list is a probabilistic, ordered data structure that searches multiple sorted levels to achieve expected (O(log n)) performance. Unlike a hash table, it maintains sorted order and supports efficient range queries, while hash tables generally provide faster expected lookups without ordering guarantees.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Skip Lists Work

  • Level 0 contains every key in sorted order.

  • Higher levels contain randomly promoted subsets of keys.

  • Each node forms a tower spanning the levels where it appears.

  • Search starts at the highest level, advances while the next key is smaller, then descends until the key is found or absent.

  • Insertion chooses a random tower height using a promotion probability, commonly (0.5).

  • Deletion removes the node from every level in its tower.

The expected height is (O(log n)), so a search examines only a small subset of nodes. A poorly balanced or adversarial structure can degrade to a linked list.

Small Walkthrough

Suppose the keys are 1, 3, and 4, and 1 and 4 are promoted:

  1. Base level: 1 -> 3 -> 4

  2. Upper level: 1 -> 4

  3. Searching for 3 starts above, sees that 4 is too large, descends, and finds 3 on the base level.

Hash Table Internals

A hash table computes a key’s hash value and maps it to one of its buckets.

  • Load factor: the ratio of stored entries to available buckets. A higher load factor means more collisions and longer probes.

  • Separate chaining: each bucket owns a linked list or tree of colliding entries.

  • Open addressing: entries are stored directly in the table, and collisions are resolved by probing another slot.

  • Linear probing: checks consecutive slots.

  • Quadratic probing: checks slots using a quadratic sequence.

  • Double hashing: uses another hash-derived step size.

  • Resizing: when the load factor becomes too high, the table allocates more buckets and rehashing every key. Across a sequence of insertions, resizing makes insertion amortized (O(1)).

Python’s dict uses an open-addressed implementation and preserves insertion order, guaranteed since Python 3.7. A set is a hash table containing keys. Keys must be hashable; tuples can be keys when their elements are hashable, but lists cannot be keys. Mutating a key’s hash-relevant contents while it is stored can make it unreachable.

Skip Lists vs. Hash Tables

Operation or property Skip list Hash table
Lookup Best/expected (O(log n)); worst (O(n)) Best/average (O(1)); worst (O(n))
Insert Expected (O(log n)); worst (O(n)) Average (O(1)), amortized (O(1)); worst (O(n))
Delete Expected (O(log n)); worst (O(n)) Average (O(1)); worst (O(n))
Ordering Keys remain sorted General hash tables are unordered; Python dict preserves insertion order
Range query (O(log n + k)) for (k) results Usually requires scanning all entries
Space Expected (O(n)) (O(n))

All space bounds exclude the input collection. Both structures use (O(n)) storage, but hash-table lookup is preferable when only exact-key access is needed. Skip lists are useful when ordering, predecessor/successor operations, or range scans matter.

Common Pitfalls

  • Do not assume a hash table supports range queries; even Python’s dict, which preserves insertion order, does not keep keys sorted.

  • Never mutate the contents of a stored hash key.

  • Decide whether duplicate skip-list keys are rejected, replaced, or stored as separate nodes.

  • Empty and single-element lists work correctly, and negative or already-sorted integer keys require no special handling.

  • Skip-list search and insertion are naturally iterative, so they need no recursion stack. Interviewers commonly follow up about promotion probability, resizing, worst-case behavior, and choosing between ordering and constant-time lookup.

32

What is a Dynamic Perfect Hash Table?

A dynamic perfect hash table maintains a collision-free mapping from keys to table slots while supporting updates such as insertion and deletion. Unlike an ordinary hash table, every stored key has a unique destination, so the final table needs neither collision chains nor long probe sequences.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

A perfect hash function has this property for the current key set:

h(key) is unique for every stored key.

Consequently, each key maps directly to its final slot. The table is dynamic when it can preserve this property after keys are added or removed.

A static perfect hash table is optimized for a fixed key set. Dynamic perfect hashing supports updates through techniques such as local restructuring, reseeding, or rebuilding.

Internal Design

Although implementations vary, common components are:

  • Hash function: Maps a key to a candidate location. Lookup remains O(1) when hashing and key comparison take constant time.

  • Buckets or first-level groups: A family of hash functions distributes keys into manageable groups.

  • Second-level hash function: Maps the keys within each group to distinct slots in that group’s secondary table.

  • Perfect final mapping: No two keys occupy the same final slot, so the final tables need neither chaining nor probing.

  • Load factor: A minimal perfect table has one key per slot and therefore a load factor of 1; implementations that reserve spare slots can have a lower load factor.

  • Rebuilding or reseeding: An update that breaks the perfect mapping may trigger local repair or reconstruction.

A small FKS-style example is:

  1. Start with the keys ant, bee, and cat.

  2. A first-level hash function groups ant and bee together while placing cat in another group.

  3. A second-level hash function assigns ant and bee distinct positions in their group’s secondary table; cat is assigned a position in its own table.

  4. Lookup computes both hash levels and directly identifies the final slot. If a new key collides with an existing key in its group, the affected group is repaired or rebuilt.

Collision Handling

Ordinary hash tables handle collisions in two common ways:

Strategy How collisions are handled Typical result
Separate chaining Store colliding keys in a list at the bucket O(1) average, O(n) worst-case lookup
Open addressing Probe other slots using linear probing, quadratic probing, or double hashing O(1) average, O(n) worst-case lookup

A perfect hash table does not retain collisions in its final mapping. A candidate function that produces collisions is rejected, reseeded, or repaired.

Complexity

Assuming constant-time hashing and constant-size keys:

Operation Best Average Worst
Lookup in a constructed perfect table O(1) O(1) O(1)
Insertion or deletion in a suitable dynamic scheme O(1) when no restructuring is needed O(1) expected amortized O(n) for a rebuild-based update
Ordinary hash-table lookup O(1) O(1) O(n)
Ordinary hash-table insertion or deletion O(1) O(1) amortized O(n)

There is no universal worst-case update bound for every dynamic perfect-hashing algorithm; repeated seed selection can make the total bound scheme-dependent. A single rebuild over n keys costs O(n) time.

Space usage is typically O(n) for the tables and auxiliary metadata. Excluding the input, this is O(n); including the input, it remains O(n). The recursion stack depends on the implementation: it is O(1) for an iterative implementation and can be O(n) for a recursive one, without changing the overall O(n) space bound.

Resizing and Practical Trade-offs

Ordinary hash tables commonly double their capacity and rehash all entries. Repeated growth makes insertion O(1) amortized even though one resize costs O(n).

Perfect hash tables use different update strategies:

  • Small updates may be handled by local restructuring.

  • A failed update may trigger reseeding or rebuilding.

  • Batching updates and rebuilding after a threshold can make update cost amortized.

  • A rebuild creates a larger latency spike than an ordinary insertion.

The benefit is fast, collision-free lookup. The cost is more complex construction, greater implementation overhead, and sensitivity to poor or adversarial hash functions.

Interview Tips

  • Perfect hashing guarantees no collisions in the final mapping; it does not imply cryptographic security.

  • Dynamic refers to supporting updates while preserving the perfect-mapping property.

  • Dynamic perfect hashing differs from extendible hashing, which uses directory indirection and bucket growth rather than requiring a globally perfect mapping.

  • Python’s dict is not a dynamic perfect hash table: it uses open addressing, manages collisions internally, and preserves insertion order.

  • Dictionary keys must be hashable. Lists cannot be keys because they are mutable; tuples can be keys when all their elements are hashable.

  • A common follow-up asks how updates are handled; discuss reseeding, local restructuring, amortized update cost, and occasional O(n) rebuilds.

33

When to use a Bloom Filter versus a hash table?

A Bloom Filter is a compact probabilistic membership structure suited to screening a large, mostly immutable dataset when false positives are acceptable. A hash table is the appropriate choice when exact membership, associated values, updates, or deletion are required.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Bloom Filters Work

A Bloom Filter contains a bit array of size m and uses k hash functions or hash-derived positions for each item:

  1. Insertion computes the item’s k positions and sets each bit to 1.

  2. Lookup computes the same positions.

  3. If any bit is 0, the item is definitely absent.

  4. If every bit is 1, the item is probably present, but a false positive is possible.

With no deletions and consistent hashing and serialization, a standard Bloom Filter has no false negatives. Its approximate false-positive probability is:

p ≈ (1 - e^(-kn/m))^k

For an expected population of n items and target false-positive rate p, common sizing formulas are:

  • m = ceil(-n × ln(p) / ln(2)²) bits

  • k = ceil((m / n) × ln(2))

For example, with eight bits, adding "cat" at positions 1 and 5 and "dog" at positions 3 and 7 sets four bits. A later item hashing to positions 2 and 6 is definitely absent because both bits remain 0.

When to Use Each

Use a Bloom Filter when:

  • The dataset is large enough that storing every key would consume substantial memory.

  • Most membership checks concern absent items, so many expensive database or disk lookups can be skipped.

  • False positives are acceptable but false negatives are not.

  • The set is mostly immutable, or rebuilding it after changes is acceptable.

Typical uses include screening URLs, file chunks, cache keys, and database identifiers before consulting an authoritative store.

Use a hash table when:

  • The answer must be exact.

  • The application needs the value associated with a key.

  • Entries must be inserted, updated, or deleted frequently.

  • The complete key set reasonably fits in memory.

A Bloom Filter is therefore usually a pre-filter in front of a hash table or database, not a replacement for one.

Behavior, Complexity, and Storage

Property or operation Bloom Filter Hash Table
Membership result Possibly present; false positives are possible Exact after collisions are resolved
False negatives None under normal, deletion-free operation None for correctly implemented lookup
Lookup time O(k) best, average, and worst O(1) best and average; O(n) worst
Insertion time O(k) best, average, and worst O(1) best and average; O(n) worst
Deletion time Not supported by a standard Bloom Filter O(1) best and average; O(n) worst
Space O(m) bits O(n) stored entries, plus key and value payloads as applicable

These bounds exclude input storage and assume constant-time hash-position and bucket access. Hashing an L-byte key adds O(L) when one hash is reused to derive Bloom Filter positions; independent hashes that each scan the key can cost O(kL).

Hash-table average operations are O(1) because good hashing, controlled load factors, and effective collision resolution keep the expected number of probes constant. The worst case is O(n) when many keys collide. A geometrically growing table occasionally spends O(n) to resize and rehash, giving amortized O(1) insertion time. Neither structure needs recursion, so its recursion-stack space is O(1).

Hash Table Internals

A hash function maps each key to a bucket or array position. The load factor is the number of stored entries divided by the table’s capacity.

  • Separate chaining stores colliding entries in a list or linked list associated with each bucket.

  • Open addressing stores colliding entries in other array slots found through linear probing, quadratic probing, or double hashing.

Open addressing generally works well at lower load factors, while chaining tolerates higher load factors naturally. When the load factor crosses a threshold, a table can allocate more capacity and rehash its entries into the new structure.

In CPython’s Python 3.12 implementation, dictionaries and sets use open addressing; a set is a hash table of keys. Dictionaries preserve insertion order, guaranteed by the Python language since version 3.7. Keys need only be hashable, not necessarily immutable: lists cannot be dictionary keys, tuples can be keys when all their elements are hashable, and custom mutable objects can technically be hashable. Such custom keys should not have hash-relevant mutations that make later lookups unreliable.

Common Pitfalls and Interview Tips

  • A positive Bloom Filter result does not prove presence; verify it against an authoritative structure.

  • Keep serialization, hash functions, bit count, and hash count consistent. Changing the filter configuration requires rebuilding it from known items.

  • Standard Bloom Filters do not support deletion; Counting Bloom Filters provide approximate deletion support.

  • Bloom Filters are unsuitable as exact security allowlists because false positives are possible.

  • Empty and one-item structures are valid. Duplicate Bloom Filter insertions are idempotent, negative numeric keys are valid when hashable, and sorted versus unsorted input does not change average hash-table complexity.

  • Disconnected graphs and cycles do not apply because neither structure has graph-traversal semantics.

  • Common follow-up topics include sizing, false-positive probability, deletion, concurrency, collision strategies, and amortized resizing.

34

How does the Pigeonhole Principle relate to hashing?

The Pigeonhole Principle states that placing more objects than containers into those containers forces at least one container to hold multiple objects. In hashing, this explains why collisions are unavoidable when there are more keys than available hash buckets.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Principle

If n objects are placed into m containers and n > m, at least one container must contain at least two objects. More generally, if each container may hold at most one object, n + 1 objects guarantee a collision.

For example, four users might be assigned to three server shards. At least one shard must receive more than one user.

Connection to Hash Tables

A hash table uses:

  • A hash function to transform a key into a numeric hash value.

  • Buckets to store entries at selected indices.

  • A load factor to compare the number of stored entries with the number of buckets.

  • A collision-handling strategy to store multiple entries associated with the same bucket.

A simplified example with bucket count 3:

Key hash(key) % 3 Bucket
10 1 1
20 2 2
30 0 0
40 1 1

Keys 10 and 40 map to the same bucket, so they collide. The table must then determine whether their keys are actually equal and store or locate them appropriately.

Collision Handling

Strategy How it works Main trade-off
Separate chaining Each bucket contains a list or linked structure of entries Simple, but poor cache locality and potentially long chains
Linear probing Check the next bucket sequentially after a collision Fast in practice, but clustering can increase probe counts
Quadratic probing Check buckets using a quadratic sequence of offsets Reduces clustering somewhat but requires careful probe design
Double hashing Use a second hash function to determine the probe step Better distribution, but more computation and implementation complexity

Hash functions must ideally distribute keys uniformly, but no hash function can eliminate collisions for every possible input.

Load Factor and Resizing

The load factor is commonly expressed as:

load factor = number of stored entries / number of buckets

As the load factor increases, collisions and probe lengths become more likely. Many hash tables therefore resize or rehash their storage when the load factor crosses a threshold. This threshold varies by implementation.

During resizing, the table allocates a larger bucket array and recomputes each key’s bucket using the new capacity. Rehashing all entries costs O(n) for that resize event. Because resizing occurs only occasionally, insertion has amortized O(1) time, even though an individual insertion that triggers resizing can take O(n).

Python Keys and Complexity

Python dictionaries and sets use hash tables. In CPython, dict uses open addressing with a compact entry layout, and dictionaries preserve insertion order as a guaranteed language feature since Python 3.7.

Keys must be hashable. Built-in mutable containers such as lists are unhashable because their contents can change after being stored. Tuples can be used as keys when all their elements are hashable.

  • Average lookup, insertion, and deletion: O(1) because a good hash function distributes entries and the load factor remains controlled.

  • Worst-case lookup, insertion, and deletion: O(n) when many keys collide or probes follow a long collision sequence.

  • Space: O(n) for buckets and stored entries, excluding the input itself.

  • Iteration: O(n) to visit all entries.

Common Pitfalls

  • Treating the Pigeonhole Principle as proof that hashing is ineffective; it explains why collision handling is necessary.

  • Assuming equal hash values always mean equal keys. Different keys can collide, so the table must also compare keys.

  • Assuming resizing makes every insertion constant time. Individual resizing operations cost O(n), while the amortized insertion cost is O(1).

  • Using a poor hash function that creates systematic bucket clusters.

  • Forgetting hashability rules: lists cannot be dictionary keys, but tuples can be used if their elements are hashable.

  • Interviewers commonly follow up with “What is the load factor?”, “How are collisions resolved?”, or “Why are dictionary operations expected to be O(1)?”

35

What advantages does a trie offer compared with a hash table?

A trie, or prefix tree, is often preferable to a hash table when operations depend on shared prefixes, such as autocomplete, prefix search, or longest-prefix matching. Hash tables are generally better for exact-key lookup and usually consume less memory.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Internal Model

  • Hash table: A hash function maps each key to a bucket.

  • Collisions are commonly handled with separate chaining using linked lists or buckets, or with open addressing using linear probing, quadratic probing, or double hashing.

  • The load factor measures occupied capacity. When it exceeds a threshold, the table resizes and rehashes its entries.

  • Resizing contributes amortized O(1) insertion cost under normal assumptions, although one individual resize can take O(n).

  • Python’s dict uses an open-addressing implementation and has preserved insertion order since Python 3.7. A Python set is a hash table of keys.

  • Dict and set keys must be hashable. Python lists are unhashable, while tuples can be used as keys when all their elements are hashable.

  • Trie: Each node represents a prefix and stores outgoing edges keyed by characters or symbols.

  • The root represents the empty prefix.

  • A path from the root spells a key.

  • A terminal marker identifies complete keys, so one key can be a prefix of another.

  • Searching examines symbols directly rather than relying on a hash function or resolving key-equality collisions.

Prefix Example

Suppose these strings are inserted:

Stored key Trie path Status
cat c → a → t Terminal after t
car c → a → r Terminal after r
card c → a → r → d Terminal after d

Searching for car follows c → a → r and reaches a terminal node in O(m) time, where m = 3 is the key length. Searching for ca reaches a valid prefix but no terminal node, allowing the application to enumerate cat, car, and card. A hash table would need to inspect stored keys individually to perform this prefix operation.

Advantages of Tries

Requirement Trie Hash table
Exact lookup O(m) worst case, where m is key length O(1) average after hashing; O(n) worst case
Find keys with a prefix O(p + L), where p is prefix length and L is the total returned character count Usually requires scanning all keys
Longest matching prefix Natural O(m) traversal Requires an additional index or scanning
Lexicographic traversal Natural through ordered child traversal Requires sorting
Collision behavior No key-equality collisions Depends on collision handling
Memory usage Often high because many nodes contain sparse edges Usually lower for complete records
Non-string data Requires an alphabet or encoding, such as integer symbols Supports any hashable Python object

A trie also avoids hash-collision behavior entirely. Its lookup bound depends on the key length rather than the number of stored keys, making it predictable under adversarial inputs.

Complexity Details

For a trie containing strings with total length S:

  • Successful exact lookup: Best, average, and worst case are O(m) because the complete key path must be consumed.

  • Unsuccessful exact lookup: Best case is O(1) when the first missing edge is detected; average and worst case are O(m).

  • Insertion: Best, average, and worst case are O(m) for a nonempty key because every character must be traversed or created.

  • Deletion: Best, average, and worst case are O(m) for a nonempty key because the path must be traversed before clearing its terminal marker.

  • Prefix search: O(p + L) when returning matching strings, where L is the total number of returned characters.

  • Space: O(S), excluding the input and stored payloads. No recursion stack is required.

For a hash table containing n keys:

  • Lookup, insertion, and deletion after hashing: Best and average case are O(1); worst case is O(n) when entries collide into one bucket or probing sequence.

  • Hashing cost: Hashing a new length-m string normally costs O(m). Cached string hashes can reduce repeated hashing.

  • Resizing: An individual insertion can take O(n), but resizing contributes amortized O(1) to overall insertions under normal assumptions.

  • Prefix enumeration without an index: Requires O(n) key checks plus the character-comparison cost of checking each candidate.

  • Space: O(n) auxiliary table metadata, excluding the input and stored key payloads. No recursion stack is used.

Trade-offs and Use Cases

Choose a trie when prefix behavior is central:

  • Search-engine typeahead

  • Autocomplete

  • Longest-prefix routing

  • Dictionary lookup by word stem

  • Fixed-length network-routing prefixes

  • Finding all keys sharing a prefix

Choose a hash table when the primary operation is exact membership or retrieval:

  • Mapping users to records

  • Counting frequencies

  • Caching values by complete key

  • Looking up arbitrary hashable objects

  • Storing relatively few complete keys

A trie is not automatically faster: hashing a short key and accessing one bucket can be cheaper than traversing several trie nodes, and trie implementations can consume substantial memory.

Common Pitfalls

  • Confusing prefix matches with complete matches: Use terminal markers; finding a path alone does not prove that the complete key exists.

  • Ignoring key length: The expected O(1) hash-table bound excludes the cost of hashing a new string.

  • Underestimating trie memory: Each node may require several pointers or map entries even when it has only one child.

  • Forgetting normalization: Case folding, Unicode normalization, and tokenization must happen consistently before insertion and lookup.

  • Handling empty values: An empty string can be represented by marking the root terminal, and an empty prefix query can match every stored key.

  • Handling simple cases: A one-character key uses a single edge; duplicate insertions are idempotent when the terminal marker is a Boolean, or can be counted explicitly if frequencies are needed.

  • Choosing the wrong structure: Exact lookup usually favors a hash table, while prefix-oriented queries usually favor a trie.

  • Interview follow-ups: Expect questions about collision handling, load factors, rehashing, prefix enumeration, memory optimization, and how Python’s dict differs from a trie.

36

How does Robin Hood hashing affect performance and collision resolution?

Robin Hood hashing is an open-addressing collision-resolution technique that orders colliding entries by probe distance, swapping a resident entry when the incoming entry has traveled farther. This reduces probe-length variance and enables early termination during lookup, but it does not eliminate clustering or change open addressing’s O(n) worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A hash table contains an array of slots or buckets. A hash function maps each key to a home slot, and its probe distance is the zero-based number of linear probe steps from that home slot to its current position.

With ordinary linear probing, a colliding key occupies the next available slot. Robin Hood hashing changes the placement rule:

  • Compare the incoming entry’s probe distance with the resident entry’s probe distance.

  • If the incoming entry has traveled farther, swap the entries.

  • Continue probing with the displaced entry.

  • Stop when an empty slot is found.

The swaps balance probe distances within a cluster, although a resident entry can move farther from its home during a swap. The resulting invariant also permits early lookup termination: if an encountered entry has a smaller probe distance than the current search position, the searched key cannot be present later in that cluster.

For example:

  1. Key A has home slot 1 and occupies slot 2, giving it probe distance 1.

  2. Key B has home slot 0 and reaches slot 2, giving it probe distance 2.

  3. B has traveled farther, so B takes slot 2 and A is displaced to continue probing.

Collision-Resolution Alternatives

Strategy Collision handling Typical performance Main characteristic
Separate chaining Each bucket stores a list of colliding entries O(1) average, O(n) worst case Simple deletion, but extra list overhead
Linear probing Continue to the next slot O(1) average, O(n) worst case Simple, but vulnerable to primary clustering
Quadratic probing Probe using squared offsets O(1) average, O(n) worst case Reduces primary clustering but can create secondary clustering
Double hashing Use a second hash for the probe step O(1) average, O(n) worst case Usually distributes keys more evenly
Robin Hood hashing Swap entries according to probe distance O(1) average, O(n) worst case Reduces probe-length variance and supports early termination

Performance and Resizing

The load factor is the number of stored entries divided by the number of slots. A high load factor increases clustering and probe lengths. Implementations therefore resize when the load factor exceeds a chosen threshold.

  • Best case: O(1) per operation when the home slot is available.

  • Average case: O(1) per operation with a good hash function, controlled load factor, and effective deletion handling.

  • Worst case: O(n) per operation when many keys collide or form a large cluster.

  • Amortized insertion: O(1) when the table grows geometrically, such as by doubling.

  • Space: O(n) for the table. Resizing temporarily requires O(n) additional space. The input is not counted, and no recursion stack is used.

Rehashing an existing table with n entries costs O(n). With geometric growth, the total work across n insertions is O(n), or O(1) amortized per insertion. Robin Hood hashing can require more swaps during insertion, while deletion must use tombstones or backward shifting to preserve lookup invariants.

Python 3.12 Notes

In CPython 3.12, dict uses an open-addressed hash table and guarantees insertion order; it is not a Robin Hood hash table. A set is also a hash table, but it stores keys rather than key-value pairs.

Dictionary and set keys must be hashable. Lists are unhashable because their contents can change, which would also invalidate a stored hash. Tuples can be keys when every element is hashable. Custom mutable objects should not be mutated in ways that change their hash or equality while stored.

Common Pitfalls

  • Unhashable keys: Lists cannot be hash-map keys; tuples are valid only when all their elements are hashable.

  • Unstable hashes: Do not mutate a stored key in a way that changes its hash.

  • Ignoring load factor: A nearly full table causes long clusters and poor performance.

  • Incorrect deletion: Tombstones can accumulate, so backward-shift deletion or periodic rehashing is important.

  • Assuming perfect distribution: Robin Hood hashing balances probe distances but cannot prevent poor hashing or collisions.

  • Edge cases: Empty and one-element tables should work correctly; duplicate keys update the existing entry; negative hash values require normalized indexing; sorted input is unnecessary for a hash table.

  • Common follow-ups: Interviewers often ask about load-factor thresholds, resizing policy, deletion strategies, and how Python’s built-in hash tables differ from Robin Hood hashing.

37

What is Linear Hashing and how does it handle growing datasets?

Linear hashing is an extensible hashing technique that grows a hash table gradually by splitting one bucket at a time instead of rehashing the entire table at once. It is useful when the number of records is unknown or changes significantly over time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A hash table contains buckets, and a hash function maps each key to a bucket address. A load factor measures how full the table is:

load factor = number of stored entries / number of buckets

When the load factor exceeds a configured threshold, the implementation performs a split:

  1. Select the bucket at the current split pointer.

  2. Create one additional bucket.

  3. Redistribute that bucket’s entries according to an additional hash bit.

  4. Advance the split pointer.

  5. After all buckets at the current level have been split, increase the level and double the logical bucket capacity.

This provides gradual growth rather than the sudden full-table resize performed by many conventional hash tables.

Collision Handling

Linear hashing does not require one particular collision strategy:

  • Separate chaining: Each bucket stores a list of entries whose keys map to that bucket.

  • Open addressing: Entries are stored directly in an array, and collisions are resolved using probing.

  • Linear probing is a probing method, not the same technique as linear hashing. It searches consecutive array positions.

  • Quadratic probing and double hashing are alternative open-addressing strategies.

Keys must be hashable. Python lists are unhashable because they are mutable, while tuples are hashable when their elements are also hashable.

Complexity

Operation Best Average Worst
Lookup O(1) O(1) O(n)
Insert O(1) O(1) amortized O(n)
Delete O(1) O(1) O(n)
  • Average O(1) assumes a reasonably uniform hash function and controlled load factor.

  • Worst O(n) occurs when many keys collide into one chain or bucket.

  • Amortized O(1) insertion accounts for occasional bucket splits and redistribution.

  • Space: O(n), including stored entries and bucket overhead. The input itself is not counted separately.

Python’s dict preserves insertion order, guaranteed since Python 3.7. CPython uses an open-addressed hash-table design, whereas set stores hashable keys in a hash table.

Walkthrough

Assume two initial buckets and a maximum load factor of 1.0:

  1. Insert two entries: the table has two buckets and load factor 2 / 2 = 1.0.

  2. Insert a third entry: the load factor becomes 3 / 2 = 1.5, so the threshold is exceeded.

  3. Split the first bucket: its entries are redistributed using another hash bit, creating a third bucket.

  4. The load factor becomes 3 / 3 = 1.0, so insertion can continue.

  5. Later splits grow the table one bucket at a time, avoiding a sudden full-table rehash.

Common Pitfalls and Interview Tips

  • Do not confuse linear hashing, which grows the bucket directory, with linear probing, which resolves collisions.

  • Keep the load factor below 1.0 to avoid long chains; 0.75 is a common production choice.

  • Store the hash value when implementing a custom table so redistribution does not repeatedly call hash().

  • Handle duplicate keys explicitly instead of inserting multiple entries.

  • Interviewers commonly ask about collision handling, worst-case complexity, the split pointer, and why keys must be hashable.

38

How does consistent hashing distribute data across nodes?

Consistent hashing maps keys and virtual replicas of physical nodes onto a circular hash space. Each key is assigned to the first virtual node encountered clockwise, so adding or removing a node normally remaps only keys in the affected ownership intervals.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Mechanism

  1. A stable hash function maps every key and every node-replica identifier to a fixed-size position.

  2. Each physical node is represented by multiple virtual nodes, such as node-A-0, node-A-1, and so on.

  3. The virtual-node positions are sorted around a circular ring.

  4. To locate a key, hash it and find the first virtual-node position at or after that hash. If none exists, wrap around to the first position.

  5. The physical node owning that virtual node receives the key.

For example, if the ring contains positions 10 for node A, 30 for node B, and 50 for node A, a key hashing to 25 belongs to B, while a key hashing to 57 wraps around and belongs to A.

In this context, a bucket is an interval of hash space assigned to a physical node, not an array slot in an ordinary hash table. Separate chaining and open addressing solve collisions inside hash tables; consistent hashing instead needs deterministic tie-breaking if distinct virtual positions produce the same hash value.

Distribution and Data Movement

Virtual nodes divide each physical node’s possible keys into several smaller intervals. This usually reduces skew compared with placing only one point per server.

Consistent hashing does not have a conventional fixed load factor. With K keys and N physical nodes, a uniform hash distribution gives approximately K / N keys per node on average. More virtual nodes generally reduce variance, although they do not guarantee perfect balance and add routing metadata.

Scheme Owner lookup Expected remapping after one node change Routing space
Modulo hashing O(1) O(K) O(1)
Consistent hashing O(log V) O(K / N) O(V)

Here, V is the total number of virtual-node positions. Adding a node transfers portions of existing nodes’ intervals to the new node; removing one transfers its intervals to the appropriate clockwise owners. Because a physical node has multiple virtual positions, several distinct intervals and successor nodes may be involved.

Complexity

Let V be the total virtual positions, v the virtual nodes per physical node, and K the number of keys:

  • Hashing: O(m) for an m-byte key, or O(1) when treating the hash output as fixed-size.

  • Owner lookup: O(1) best case and O(log V) average and worst case with binary search over a sorted ring.

  • Add or remove a physical node: O(v log V) with a balanced ordered index; rebuilding and sorting the entire ring takes O(V log V).

  • Data migration: best case O(0), expected O(K / N) under uniform hashing, and worst case O(K).

  • Space: O(V) for the ring and node mappings, excluding the input keys. An iterative implementation uses O(1) recursion stack; a recursive balanced-tree implementation may use O(log V) stack space. A separately materialized key-to-owner cache requires another O(K) space.

Consistent hashing should not be described as having amortized O(1) data migration: its expected migration cost is proportional to the fraction of keys affected.

Practical Design

  • Use a stable, high-quality hash whose results agree across processes and restarts. A process-randomized hash such as Python’s built-in hash() is unsuitable for distributed placement.

  • Give each node enough virtual positions to balance distribution variance, then tune the count from measured workloads rather than treating any count as universally optimal.

  • Keep virtual-node identifiers deterministic and versioned so clients can rebuild the same ring.

  • Update membership metadata atomically and invalidate or refresh cached key-to-owner mappings.

  • Combine virtual nodes with replication, rack awareness, and failure detection when availability requirements exceed a single-owner model.

  • Guard against hash collisions and ring-position ties with deterministic ordering rather than overwriting one node with another.

Common Pitfalls

  • Treating expected balance as a guarantee: bad hashing or too few virtual nodes can still cause severe skew.

  • Using unstable hashes: different processes may route the same key to different nodes.

  • Ignoring exact ring-position collisions: deterministic tie-breaking prevents lost virtual nodes.

  • Assuming only one successor is affected: virtual nodes create multiple ownership intervals.

  • Conflating physical failure with virtual-node count: many virtual replicas still represent one physical server and do not replace replication.

  • Forgetting membership changes: stale routing caches can send keys to removed or incorrect nodes.

39

When should you choose a hash table over a binary search tree?

A hash table is preferable when the primary requirement is fast lookup, insertion, and deletion by key and ordered traversal is unnecessary. For example, a web service might map user IDs to profile records; a hash table or Python dict provides average constant-time access, while a binary search tree adds unnecessary ordering overhead.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When a Hash Table Is the Better Choice

A hash table is well suited to operations such as:

  • Looking up a customer by customer ID.

  • Counting word frequencies in a document.

  • Caching results by request or session key.

  • Detecting duplicates using a set.

  • Storing configuration values under string keys.

These workloads mainly ask, “Does this key exist, and what value is associated with it?” They do not usually require keys to remain sorted or support range queries.

A binary search tree (BST) is more appropriate when ordered access matters, such as maintaining sorted iteration, finding the next largest key, or efficiently answering range queries.

Internal Operation

A hash table:

  1. Computes a hash value from the key.

  2. Uses that value to select a bucket or table slot.

  3. Checks that slot for a matching key, usually by comparing both hash and equality.

  4. Stores or retrieves the associated value.

A load factor represents how occupied the table is. When it becomes too high, the implementation may allocate a larger table and rehash existing entries. Rehashing individual entries costs O(n), but spreading that work across insertions makes the total insertion cost amortized O(1).

Different hash tables handle collisions differently:

  • Separate chaining: Each bucket contains a list or collection of entries.

  • Open addressing: All entries live in the table array, and collisions are resolved using techniques such as linear probing, quadratic probing, or double hashing.

Python dict and set use open addressing internally. Python dict also preserves insertion order, a language guarantee since Python 3.7.

Complexity Comparison

For n stored entries:

Operation Hash table Balanced BST
Average lookup O(1) O(log n)
Worst-case lookup O(n) O(log n)
Average insertion O(1) amortized O(log n)
Worst-case insertion O(n) O(log n)
Average deletion O(1) O(log n)
Space O(n) O(n)
Sorted traversal O(n) without sorting O(n)
Range queries Generally O(m) after locating the range O(log n + m)

The hash-table average bound assumes reasonably distributed hashes and approximately constant-time bucket operations. An adversarial set of colliding keys can force worst-case O(n) behavior. Space complexity is O(n) for the table and stored entries, excluding the input itself.

Keys, Duplicates, and Ordering

Hash-table keys must be hashable and normally immutable:

  • Strings, integers, and tuples containing only hashable values can be keys.

  • Lists cannot be keys because they are mutable and unhashable.

  • Tuples can be keys if all their elements are hashable.

  • Duplicate keys update the existing entry rather than creating another independent record.

A hash table does not naturally expose keys in sorted order. Python dict preserves insertion order rather than hash order, which is useful for deterministic iteration but is not the same as sorted order.

Common Pitfalls and Interview Tips

  • Choosing a hash table when sorted traversal or range queries are central requirements.

  • Assuming every hash-table operation is always O(1); worst-case lookup is O(n).

  • Ignoring poor hash distribution, which can increase collisions and reduce performance.

  • Using mutable objects as keys and receiving a TypeError.

  • Forgetting that resizing can make one individual insertion temporarily expensive, even though the amortized cost is O(1).

  • Interviewers commonly ask about collisions, load factors, resizing, hashability, duplicate keys, and why a balanced BST provides more predictable O(log n) worst-case operations.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 39 Hash Tables answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects