LeetCode 711: Number of Distinct Islands II
A clear explanation of counting distinct island shapes under rotation and reflection using normalization and geometric transformations.
Tag
Hashing
56 notes
LeetCode 448: Find All Numbers Disappeared in an Array
Find all missing numbers from 1 to n in O(n) time using in-place index marking.
LeetCode 442: Find All Duplicates in an Array
Find all duplicated numbers in an array in O(n) time and O(1) extra space using index marking.
3. Hashing and Table Search
Hash table lookup strategies, open-addressing and chaining variants, probabilistic filters (Bloom, Cuckoo, XOR), and locality-sensitive similarity search.
Hash Index Probe
Retrieve rows by probing a hash-based index structure using an exact key match.
Hash Join Lookup
Find matching records during a join by probing a hash table built from one relation.
Rabin Karp Search
Search for a pattern in text by comparing rolling hash values before verifying matching windows.
Separate Chaining Search
Resolve hash collisions by storing multiple elements in buckets using linked structures.
Hash Table Lookup
Retrieve a value by computing a hash and probing a table for the corresponding key.
Rolling Hash Search
Search for a pattern in a sequence by maintaining a hash over a sliding window.
MinHash Similarity Search
Estimate set similarity and find similar items using compact MinHash signatures and banding.
SimHash Near Duplicate Search
Find near duplicate documents by comparing compact SimHash fingerprints under Hamming distance.
Locality Sensitive Hashing Search
Search for approximate nearest neighbors by hashing similar items into the same buckets with high probability.
Rendezvous Hashing Lookup
Map a key to the node that receives the highest hash score for that key.
Consistent Hashing Lookup
Map a key to a node by placing both on a hash ring and selecting the next node clockwise.
Binary Fuse Filter Lookup
Test approximate membership using a compact XOR-based filter with improved construction and cache locality.
XOR Filter Lookup
Test approximate membership with a static fingerprint filter built from three hash locations and XOR constraints.
Cuckoo Filter Lookup
Test approximate membership by storing compact fingerprints in cuckoo hash table buckets.
Quotient Filter Lookup
Test approximate membership by splitting a hash fingerprint into quotient and remainder fields.
Counting Bloom Filter Membership
Test membership with a Bloom filter variant that supports deletions using small counters instead of bits.
Bloom Filter Membership
Test set membership with a compact probabilistic bit array that allows false positives but no false negatives.
Minimal Perfect Hashing Lookup
Look up a key using a collision free hash function that maps a static key set to exactly n table positions.
Perfect Hashing Lookup
Look up a key in a static hash table whose hash function has no collisions for the stored key set.
Robin Hood Hashing Lookup
Search in an open addressing hash table that keeps probe distances balanced across keys.
Hopscotch Hashing Lookup
Search in a hash table that maintains elements within a small neighborhood of their home bucket.
Cuckoo Hashing Lookup
Look up a key in a cuckoo hash table by checking a small fixed set of candidate positions.
Double Hashing Search
Resolve hash collisions using a second hash function to define probe steps.
Quadratic Probing Search
Resolve hash collisions by probing with quadratic offsets to reduce clustering.
Linear Probing Search
Resolve hash collisions by scanning sequential slots until the key is found or an empty slot appears.
5.25 Case Studies
Examine hash-based structures in complete systems: streaming pipelines, graph algorithms, caches, and distributed workflows.
5.24 Real-World Hash Table Design
Choose and implement hash tables that perform reliably under mixed key types, uneven access patterns, and adversarial input.
5.23 Cache-Aware Hashing
Design hash table layouts that minimize cache misses and align memory access patterns with hardware behavior.
5.22 Hybrid Hash Structures
Combine hash tables with other data structures to handle skewed distributions, heavy deletions, and mixed workloads.
5.21 Consistent Performance Guarantees
Achieve predictable worst-case bounds for hash-based structures rather than relying solely on average-case expectations.
5.20 Testing Hash Logic
Verify correctness, stability, and performance of hash-based structures through randomized and adversarial test strategies.
5.19 Deterministic Hashing
Produce stable hash values that remain consistent across program runs, machines, builds, and language runtimes.
5.18 Attack Resistance
Defend hash tables against adversarial inputs that force worst-case collision behavior using randomized hashing.
5.17 Cache Behavior
Understand how memory hierarchy effects cause hash table performance to deviate from asymptotic expectations.
5.16 Hash-Based Deduplication
Remove duplicate entries from a dataset or stream efficiently using hash sets for membership tracking.
5.15 Hash Joins
Join two collections by key using a hash table to reduce the cost from quadratic to linear expected time.
5.14 Consistent Hashing
Distribute keys across a dynamic set of nodes so that adding or removing nodes moves only a minimal fraction of keys.
5.13 Count-Min Sketch
Approximate frequency counting for large key streams using a compact probabilistic data structure with bounded error.
5.12 Bloom Filters
Test set membership approximately using a compact bit array and multiple hash functions, with no false negatives and bounded false positives.
5.11 Rolling Hashes
Compute hash values for sliding windows over a sequence in constant time by incrementally updating rather than recomputing.
5.10 Composite Keys
Hash and compare multi-field keys correctly by combining all fields that participate in equality into the hash function.
5.9 Grouping Keys
Partition a collection into groups by key using a hash map that accumulates values into per-key lists or sets.
5.8 Counting Maps
Track frequency counts for keys using a hash map that increments a counter on each insertion of an existing key.
5.7 Maps
Build a hash-based map that associates keys with values and supports insert, lookup, delete, and update in expected constant time.
5.6 Sets
Implement a hash-based set for fast membership testing, insertion, and deletion without associated values.
5.5 Rehashing
Rebuild a hash table's bucket array after resizing so that every stored key satisfies the placement invariant for the new capacity.
5.4 Load Factor and Resizing
Control hash table performance by monitoring the load factor and growing the bucket array before collisions accumulate.
5.3 Collision Handling
Resolve hash collisions using separate chaining or open addressing, with trade-offs in memory, locality, and load tolerance.
5.2 Hash Functions
Design and evaluate hash functions that distribute keys uniformly across buckets while remaining fast to compute.
5.1 Hash Tables
A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.
2.17 Rolling Hashes
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
Chapter 5. Hashing and Maps
Hash tables, hash functions, collision handling, probabilistic structures, and practical design for constant-time key-value access.