Hashing and Hash Based Data Structures Questions

Comprehensive coverage of hashing and hash based associative data structures including hash tables, hash maps, dictionaries and hash sets. Candidates should explain hashing fundamentals and the role and properties of hash functions, causes of collisions, and common collision resolution strategies such as chaining and open addressing. Discuss load factor, resizing behavior and how these influence amortized performance and memory usage. Describe average case constant time behavior for lookup insertion and deletion and worst case linear time under pathological collision scenarios, and contrast trade offs with alternatives such as balanced search trees and sorting based approaches. Expect practical problem solving using hash based structures for frequency counting, duplicate detection, grouping, membership testing, two sum and pair problems, anagram detection, sliding window frequency problems and cache or memoization designs including least recently used eviction concepts. Be familiar with common language level implementations such as HashMap and HashSet in Java and dictionary and set in Python and be able to reason about implementation pitfalls including unhashable or mutable keys, custom hash and equality semantics, resizing costs, collision attacks and memory overhead. Interviewers will probe time and space trade offs, when a hash based approach is preferable, and optimization strategies when facing pathological inputs.

EasyTechnical

26 practiced

Describe average-case and worst-case time complexity for lookup, insertion, and deletion in hash tables. Explain what causes the worst-case linear behavior and give examples of pathological inputs or attack scenarios that lead to it. How can language/runtime implementations mitigate such worst cases?

Sample Answer

Average case vs worst case (summary)- Average-case for lookup, insertion, deletion: O(1) — with a good hash function and load factor kept constant, operations examine a constant number of buckets or items.- Worst-case for all three: O(n) — if many keys collide into the same bucket, operations may scan or manipulate a long chain/tree of size O(n).

Why worst-case becomes linear- Hash tables depend on distributing keys across buckets. If many keys map to the same bucket (identical or colliding hash codes), operations degrade from constant-time to scanning that bucket’s contents (linked list or similar), giving O(n) time.- Poor resizing policy or very high load factor can exacerbate the effect.

Pathological inputs / attack scenarios- Hash-flooding: an attacker supplies many keys that produce identical or colliding hash values (e.g., strings crafted to collide under a weak hash). Web servers parsing attacker-supplied JSON/form fields can be targeted to force O(n^2) behavior across many operations.- Predictable or trivial hash functions (e.g., returning length or first character) enable easy collision construction.

Mitigations used by language/runtime implementations- Stronger hash functions: use randomized or cryptographic-quality hashing (e.g., SipHash for strings) so attackers can’t predict collisions.- Hash randomization (per-process salt): seeds hashes with secret randomness to make collisions unpredictable across runs.- Bucket structure changes: Java 8+ converts long collision chains into balanced trees (red-black trees) once a threshold is exceeded, guaranteeing O(log n) instead of O(n).- Capacity and load management: keep load factor bounded and rehash proactively to avoid long chains.- Universal hashing or guarded hash families to limit adversarial collision likelihood.- Application-level defenses: rate-limiting, validating or limiting number of keys from untrusted sources, or using alternative data structures (e.g., sorted maps) for untrusted input.

TakeawayAverage-case O(1) relies on good distribution and engineering choices; worst-case O(n) arises from collisions but is mitigated in modern runtimes by randomized hashing, stronger hash functions, structural fallbacks (trees), and defensive application practices.

MediumTechnical

27 practiced

Explain the differences between linear probing, quadratic probing, and double hashing within open addressing. Discuss primary and secondary clustering, probe sequence properties, and how load factor thresholds differ in practice for these schemes.

Sample Answer

Linear probing, quadratic probing and double hashing are three open-addressing strategies for resolving hash collisions. Key differences center on their probe sequences, clustering behavior, and practical load-factor limits.

Probe sequences- Linear probing: h_i(k) = (h(k) + i) mod m — probes consecutive slots.- Quadratic probing: h_i(k) = (h(k) + c1*i + c2*i^2) mod m — probes positions that grow quadratically from the base.- Double hashing: h_i(k) = (h(k) + i * h2(k)) mod m — uses a second hash to produce a stride; if m is prime and h2(k) is nonzero and coprime to m, the sequence permutes the table.

Clustering- Primary clustering: severe in linear probing. Long runs form and new keys falling into a run tend to lengthen it, causing average probe lengths to increase rapidly as load grows.- Secondary clustering: happens in quadratic probing — distinct keys that hash to the same initial slot follow identical probe sequences, so they cluster with each other but not with keys from different starts.- Double hashing: avoids both primary and (largely) secondary clustering because different h2(k) produce different strides; probe sequences differ even for the same initial h(k).

Performance and load-factor considerations- Linear probing: excellent cache locality; average successful search ≈ (1 + 1/(1−α))/2 probes, unsuccessful ≈ 1/(1−α)^2 behavior; performance degrades fast as α→1. Practical α limit ~0.5–0.75 (commonly ≤0.7).- Quadratic probing: reduces primary clustering and performs well up to moderate α, but probe sequences may not cover all slots (careful choice of m and constants needed). Typical safe α ≤0.5–0.7 depending on parameters.- Double hashing: best at avoiding clustering, scalable to higher load factors (often used up to α ≈0.8–0.9) with good average probe counts, but less cache-friendly than linear probing.

Implementation notes- Choose table size and hash2 so sequences visit all slots (prime m or ensure gcd(h2(k), m)=1).- For deletions use tombstones; tombstones hurt probing performance across all methods but are manageable.- If cache locality is critical, linear probing often wins despite clustering; if predictable low probes at high loads matter, double hashing is preferable.

EasyTechnical

30 practiced

Write a Java method that counts frequency of words in a list of strings and returns a Map<String, Integer> with counts. Consider case sensitivity, null or empty strings, and memory considerations for extremely large input. Provide clean, idiomatic Java code and explain complexity.

Sample Answer

Approach: iterate the list once, normalize each entry (handle null/empty, optional case folding), and update counts in a HashMap using Map.compute. For extremely large inputs suggest streaming or approximate counters to reduce memory.

java

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

public class WordCounter {
    /**
     * Count frequencies of words in the provided list.
     *
     * @param words         list of strings (may contain nulls)
     * @param caseSensitive whether counts should be case-sensitive
     * @return Map of word -> count
     */
    public static Map<String, Integer> countFrequencies(List<String> words, boolean caseSensitive) {
        Map<String, Integer> freq = new HashMap<>();
        if (words == null) return freq;

        for (String w : words) {
            if (w == null) continue;                 // skip nulls
            String trimmed = w.trim();
            if (trimmed.isEmpty()) continue;        // skip empty or whitespace-only
            String key = caseSensitive ? trimmed : trimmed.toLowerCase();
            freq.compute(key, (k, v) -> v == null ? 1 : v + 1);
        }
        return freq;
    }
}

Key points:- Uses a single pass (one iteration) and in-place HashMap updates.- Handles null list, null entries, empty/whitespace-only strings, and optional case sensitivity.

Time complexity: O(n * m) where n = number of strings, m = average string length for trim/toLowerCase.Space complexity: O(k) where k = number of distinct words stored.

Memory considerations for extremely large input:- Use streaming (process items one-by-one rather than loading into a List).- If distinct keys explode, consider external aggregation (e.g., map-reduce), or probabilistic structures (Count-Min Sketch) to trade accuracy for memory.

HardTechnical

23 practiced

Design a concurrent hash map for multi-threaded access. Discuss approaches such as lock striping/segmented locks, per-bucket locks, lock-free algorithms using CAS, and the approach used by Java ConcurrentHashMap. Address resizing with concurrency, memory ordering, and fairness trade-offs.

Sample Answer

Requirements & constraints:- Concurrent reads/writes with high throughput under contention- Bounded memory overhead, low latency for common ops (get/put/remove)- Correctness: linearizability for individual ops, safe iteration semantics (weakly consistent acceptable)- Scalable to many cores

High-level approaches:1) Per-bucket locks- Simple: one lock per hash bucket (or small group). Fine-grained, good parallelism if keys spread evenly.- Downsides: high memory for many locks, lock overhead for short ops, contention if hot keys.

2) Lock striping / segmented locks- Partition map into S segments each with one lock and independent hash table. Parallelism up to S. Used historically (Java 7 CHM).- Trade-off: simpler resizing per segment; reduces memory vs per-bucket locks but limits parallelism to number of segments; hotspots still contend.

3) Lock-free with CAS (optimistic)- Use atomic compare-and-swap on pointers/word-sized fields, immutable or versioned nodes, and retry loops. Enables wait-free/lock-free reads and mostly-lock-free writes.- Complexity: ABA problems, memory reclamation (hazard pointers/GC), harder to implement for resizing and to reason about fairness.

Java ConcurrentHashMap (post-Java 8) design (practical hybrid):- Uses array of bins; each bin is initially a chained list. Reads are mostly lock-free: volatile reads of table/bin pointers and traversing nodes without locks.- On contention, a bin can be converted to a tree (red-black) to bound pathological lists.- Writes use CAS to install nodes into an empty bin or to replace the bin pointer; if concurrent insert conflicts or long operations occur, fallback uses synchronized lock on a bin (per-bin lock) to serialize complex updates.- Resizing is incremental and concurrent: resizing creates a new table and migrates bins gradually; threads encountering a resizing state help transfer portions (work-stealing style). Uses forwarding nodes to mark moved bins.- Memory visibility: uses volatile fields and ordered CAS to ensure happens-before; ensures readers see consistent snapshots of nodes reachable from volatile table/bin references.- Fairness & trade-offs: CHM favors throughput over strict fairness. Locks used are short and local; no FIFO guarantees. Lock-free reads minimize tail latency but writers may starve in pathological contention; converting to trees reduces worst-case latency per operation.

Resizing with concurrency:- Avoid global stop-the-world rehash. Use incremental rehashing with help from mutating threads.- Use forwarding markers so readers/writers encountering moved bins can follow to new table.- Ensure size bookkeeping uses atomic counters (LongAdder-style) to avoid contention; compute load factor approximations to trigger resize.

Memory ordering & correctness:- All published pointers/heads must be volatile or set via CAS to establish visibility.- Use immutable node payloads where possible; updates replace node objects to avoid data races on fields.- For lock-free sequences, ensure linearizability by performing the CAS that installs the visible change as the linearization point.- Use memory reclamation strategy appropriate to language: GC simplifies reclamation in Java; C++ needs hazard pointers/epoch-based reclamation.

Fairness trade-offs:- Fine-grained locks and CAS favor throughput and low-latency readers but not fairness—writers can be retried many times.- Introducing fair locks increases overhead, reduces scalability.- Practical choice: optimize the common-case (reads, low-contention writes) with lock-free reads and per-bin short locks; accept weak fairness.

Recommendation:- For Java-like environment, adopt the Java 8 ConcurrentHashMap pattern: volatile table, CAS-based bin installs, per-bin synchronized blocks for complex updates, treeify on contention, and cooperative incremental resizing. This balances implementation complexity, performance, and correctness for production multi-threaded systems.

HardSystem Design

27 practiced

System design: Design a distributed in-memory cache (like memcached) that shards keys across nodes using consistent hashing. Explain client routing vs proxying, how to handle node failures and additions (rebalancing), replication for availability, and strategies for keeping hot keys cached efficiently.

Sample Answer

Requirements & constraints:- Function: low-latency distributed in-memory key-value cache.- Non-functional: millions QPS, low ms latency, high availability, eventual consistency acceptable, scalable cluster size.

High-level design:- Clients compute key -> node mapping using consistent hashing ring (with virtual nodes) and talk directly to the chosen cache node (client routing). Optionally a proxy layer can exist for simpler clients or ACLs; proxies add latency and become scaling/availability concerns.

Consistent hashing & virtual nodes:- Hash(key) maps to ring; each physical node owns multiple vnodes to improve balance. On node join/leave only adjacent key ranges move (proportional to O(1/N) keys).

Client routing vs proxying:- Client routing: clients keep ring metadata; zero-hop lookup, low latency, higher client complexity and need for metadata refresh.- Proxying: clients send to proxies that know ring; simplifies clients, centralizes logic but proxies are extra network hop and require scaling/HA.

Node failures & additions (rebalancing):- Failure detection via gossip + heartbeat. On failure: ring metadata updates; clients/proxies exclude node; replicas (see below) serve keys.- Rebalancing: when node added/removed, only affected vnodes migrate. Use background streaming of key-value pairs (bulk transfer) with rate limiting. Use consistent hashing + vnode-to-node mapping change propagated via versioned metadata; clients fetch updated metadata (push via pub/sub to minimize stale reads).- Use anti-entropy (Merkle trees) and background sync to reconcile.

Replication & availability:- Use replication factor R (e.g., 3). For a key, store on the primary vnode and next R-1 clockwise vnodes. Support quorum options: write to W nodes, read from Rq nodes with W+Rq>R for strong-ish consistency, or async replication for low latency.- Techniques: synchronous replication for critical keys, async for typical. On node failure use hinted handoff: temporarily store writes on nearby nodes and replay to recovered node. Use read-repair on reads to fix stale replicas.

Hot-key handling:- Detect hot keys via local counters or sampled telemetry. Strategies: - Adaptive replication: increase replication factor for hot keys to more nodes to spread load. - Client-side local cache: small LRU per client to absorb reads. - Request coalescing / single-flight at node to de-duplicate concurrent misses. - Sharding a hot key: logical key-splitting or consistent hashing with key-namespace sharding (e.g., append shard id) to split a very hot counter across multiple physical keys with aggregation at application. - Offload very hot items to dedicated nodes or use tiered caches (L1 in-process, L2 cluster).- Eviction: LFU or segmented LRU to keep high-frequency items.

Operational considerations:- Metadata propagation (gossip or centralized config + version), metrics, tracing, circuit breakers, rate limiting.- Security: TLS, auth, ACLs.- Backups: snapshotting for cold recovery; cached data is ephemeral so primary datastore required.

Trade-offs:- Client routing reduces latency but makes clients responsible for topology. Proxying centralizes control but increases latency and complexity.- Strong consistency increases latency; choose hybrid (quorum or per-key policy) based on SLAs.- Rebalancing vs availability: minimize synchronous rebalancing; prefer lazy streaming and eventual convergence.

This design yields a scalable, highly available cache with bounded rebalancing cost, configurable consistency, and targeted hot-key mitigation.

Unlock Full Question Bank

Get access to hundreds of Hashing and Hash Based Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.