Hashing and Hash Tables Questions

How hash tables and hash-based structures work internally, and how to reason about their performance and correctness. Covers hash function properties (determinism, uniform distribution, speed, avalanche effect), cryptographic versus non-cryptographic hash choices, collision resolution (separate chaining, open addressing: linear probing, quadratic probing, double hashing, Robin Hood hashing, cuckoo hashing), load factor and amortized-cost resizing, and what makes an object hashable (the __hash__/__eq__ contract, immutability, custom composite keys). Covers hash-map-backed cache design (LRU and LFU eviction, TTL) and thread-safe concurrent hash maps (lock striping, CAS-based updates, safe concurrent resizing). Also covers hash-based structures beyond arrays and strings: consistent hashing for distributed routing and sharding, hash joins, hash-flooding and algorithmic-complexity security attacks and their mitigations, and probabilistic membership/cardinality structures such as Bloom filters, Cuckoo filters, Count-Min Sketch, and HyperLogLog. Excludes using a hash map purely as an optimization trick inside an array or string problem (two-sum, group anagrams, longest substring without repeating characters); that pattern belongs to Arrays, Strings, and Hashing. This topic is about the hash table itself: how it is built, how it fails under skewed or adversarial input, and how it scales.

HardTechnical
79 practiced

Implement from-scratch a simple hash table in Python supporting put(key, value), get(key), and delete(key) using open addressing (linear probing). Support resizing when load factor exceeds a threshold. Explain complexity, deletion special cases (tombstones), and how resizing preserves correctness.

EasyTechnical
74 practiced

Explain the LRU (Least Recently Used) cache eviction policy. Describe how to implement LRU with O(1) get and put using common data structures, and why LRU is often a good default for many SRE caching use cases. Mention caveats under bursty access patterns.

HardTechnical
70 practiced

Design and implement a Bloom filter for deduplicating seen document IDs during ingestion. Given expected n items and target false positive rate p, compute optimal bit array size m and number of hash functions k. Also implement insert and might_contain operations and discuss limitations such as no deletions and how Counting Bloom Filter addresses that.

EasyTechnical
93 practiced

Implement an LRU cache class with get and put methods in Java (using LinkedHashMap) or Python (using collections.OrderedDict). Requirements: get and put must run in O(1) average time, the cache is capacity-limited, and least-recently-used entries are evicted on overflow. Discuss alternative implementations and concurrency considerations.

MediumTechnical
79 practiced

You're designing a composite key class in Java (e.g., composed of userId, eventType, and date) to be used as a HashMap key. Describe how you'd implement equals() and hashCode(), handling nulls and performance. Explain why immutability of fields matters and what can go wrong if fields are mutated after insertion into a HashMap.

Unlock Full Question Bank

Get access to all 41 Hashing and Hash Tables interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.