Overview
2 Review of Hash Tables and Modern Hashing
This chapter motivates hashing as a foundational tool for building fast dictionaries and modern data systems. It contrasts hash tables with arrays, linked lists, and balanced trees, highlighting the expected O(1) cost for lookups, inserts, and deletes when keys are well distributed, and noting the tradeoff that hash tables forgo order-based queries. The text grounds these ideas in contemporary use cases: data deduplication systems that chunk files and fingerprint content to eliminate redundancy, and plagiarism detection that leverages rolling hashes (à la Karp–Rabin) and winnowing to compare many documents efficiently via inverted indexes. Throughout, the chapter stresses practical concerns such as resizing, compact representations, and cache efficiency when scaling to massive datasets.
Core collision-resolution strategies are revisited with a blend of theory and practice. Chaining and open addressing (especially linear probing) are analyzed using balls-into-bins reasoning and k-wise independent hashing, yielding high-probability bounds while explaining why worst cases are rare. The practical takeaway is that memory locality dominates: linear probing’s contiguous probes are cache-friendly, often outperforming theoretically appealing schemes that incur extra cache misses. As a concrete case study, Python’s dict uses power-of-two table sizes with a perturbation-aided probe sequence to avoid clustering and make the common case fast; the chapter also spotlights MurmurHash as a fast, non-cryptographic hash widely used in high-performance data structures.
The chapter then moves to distributed settings, introducing consistent hashing as a way to map both resources and nodes onto a hashring so that joins and failures trigger only local remapping and preserve load balance. A pedagogical implementation shows node insertion, removal, and resource migration via ring distance and successor logic, illustrating why consistent hashing is favored in dynamic systems. Building on that foundation, the Chord protocol augments the ring with logarithmic-size finger tables so lookups complete in O(log n) hops, a design that influenced systems like Dynamo. The section closes with hands-on exercises to construct finger tables, implement efficient lookups, and keep them up to date as the overlay evolves.
: Logging into email and hashing.
: Spellchecking and hashing.
: Network packets and hashing.
: Spam filters and hashing.
: Deduplication process in backup/storage solutions. When a new file arrives, it is split into small chunks. In our example, the file is split into three chunks, and each chunk is hashed (e.g., chunk 1 has chunk-id 0x123, and chunk 2 has chunk-id 0x736.) Chunk-id 0x123 is not found in the hash table. A new entry is created for this particular chunk-id, and the chunk itself is stored. The chunk-id 0x736, having been found in the hash table, is deemed a duplicate and isn’t stored.
: Example of a Karp-Rabin fingerprinting algorithm. We are looking for a pattern p=BBBBC in the larger string t=BBBBBBBBBABBBDBBBBC. The hash of BBBBC is equal to 162 and it is a mismatch for the hash 161 of BBBBB that occurs at the beginning of the long string. As we shift right, we repeatedly encounter hash mismatches until the substring ABBBD, with the hash of 162. Then we check the substrings and establish a false match. At the very end of the string, we again encounter the hash match at BBBBC and upon checking the substrings, we report a true match.
: Rolling hash. Computing the hash for all but the first substring of t is a constant-time operation. For example, BBBDB, we needed to “subtract” A and “add” B to ABBBD.
: An example of insert and search with chaining.
: An example of insert and search with linear probing.
: Using a hash table, we can map resources to nodes and help locate appropriate node for a queried resource (left). The problem arises when nodes join/leave the network (right.)
: Rehashing is not feasible in a highly dynamic context, because one node join/failure triggers re-assignment of all resource-node allocations. In this example, changing the hash table size from 5 to 6 changed node allocations for most resources. The bottom right illustration shows the “in-between” moment when nodes hold some out-of-date and some new resources.
: Mapping resources to nodes in the hashring. The example shows the hashring and nodes whose whose hashes are 5, 12, 18 and 27. Resources a, y and b are assigned to node 5, c and d are assigned to node 12, e is assigned to node 18, and f,h and i are assigned to node 27.
: New node arrival. The resources a and y, with respective hash values 28 and 29, are now being re-assigned to the newly inserted node with the hash value 30.
: Node removal. In this example, the node with the hash value 12 leaves the network, and its resources c and d, with hash values 7 and 10 respectively, are re-assigned to the node with the hash value 18, the previous successor of 12.
: Example finger table for the node 5, on the hashring where R=[0,31]. Node 5 has 5 entries stored in its finger table, for the successors of the points 5+1=6, 5+2=7, 5+4=9, 5+8=13, and 5+16=21. The respective successors are 12, 12, 12, 16 and 27.
: Lookup procedure with a finger tables. To locate resource 29 starting from node 5, we first follow the finger (21=5+16) as it is the finger with smallest distance to 29. Its successor is 27, so the request is forwarded to 27. In the finger table of node 27, we take the finger 2, which gives us exactly 29. Its successor is 30, where the request is finally routed, i.e., if the resource exists, it will be found at node 30.
Summary
- Hash tables are irreplaceable in modern systems, such as networks, databases, storage solutions, text-processing applications and so on. Depending on an application and the workload, hash tables can be designed to suit different needs, such as speed vs. space, simplicity vs optimizing the worst-case, etc.
- There is a large number of collision-resolution techniques, but the most frequently used ones are chaining and linear probing (Section 2.5). Linear probing has benefits when it comes to cache-efficiency. The bigger the hash table, the larger becomes the effect of cache efficiency than the effect of the number of probes on the performance.
- Most production-quality hash tables, such as Python’s
dict(Section 2.6) are about optimizing the common case and do not worry about solving rare pathological cases if they will complicate the common case. - Murmurhash (Section 2.7) is an example of a widely-used fast and simple non-cryptographic hash function, often employed by hash-based data structures we will learn about in this book.
- Consistent hashing (Section 2.8) solves the problem of hash tables that are distributed among many machines, such is the case in peer-to-peer environments. Consistent hashing has been implemented in many peer-to-peer products such as BitTorrent, and also in data store systems such as Amazon’s Dynamo.
FAQ
Why are hash tables and hashing so widely used in modern systems?
They provide near-constant-time expected performance for inserts, lookups, and deletes, which makes them ideal for high-throughput systems. You see hashing everywhere: password verification, spell checking, load-balancing network traffic, spam filtering, deduplication in storage, and similarity detection. Their speed and simplicity explain why most languages and platforms rely on them under the hood.How do common dictionary data structures compare (arrays, linked lists, balanced trees, hash tables)?
- Unsorted arrays: O(1) insert, O(n) lookup/delete; good as append-only logs.- Sorted arrays: O(log n) lookup, O(n) insert/delete; great for static data and binary search.
- Linked lists: O(1) insert/delete if position known; O(n) to find positions.
- Balanced BSTs: O(log n) for all operations plus ordered traversals, range queries.
- Hash tables: O(1) expected for all operations, but no inherent ordering (worst case O(n)).
What does “O(1) expected” mean for hash tables, and why can worst-case O(n) still happen?
Expected O(1) assumes a hash function that spreads keys evenly so buckets stay small on average. The universe of possible keys is far larger than the table, so many keys inevitably map to each bucket; a pathological input could force many keys into one bucket, yielding O(n) scans. In practice, good hash functions and designs make such cases rare, and rehashing or changing the hash family can recover.How do chaining and linear probing resolve collisions, and what are their tradeoffs?
- Chaining: each bucket holds a secondary structure (often a linked list). Fast inserts; lookup/delete cost depends on chain length.- Linear probing (open addressing): items live in the table; on collision, scan forward (wrapping) to find a slot. Excellent locality but requires careful handling of deletes (e.g., tombstones).
- Theory: with uniform hashing, longest chain/run is about O(log n / log log n) with high probability; average probes stay small when load factor is controlled.
Why does linear probing often outperform chaining in practice?
Cache efficiency. Linear probing touches consecutive slots that typically fit within one or a few cache lines, minimizing random memory accesses. Chaining follows pointers to nodes scattered in memory, incurring more cache misses and higher latency. Even if theoretical probe counts are similar, memory locality often decides the real runtime.How does Python’s dict handle hashing and probing to avoid clustering?
Python’s dict uses open addressing with a carefully designed probe sequence that visits all slots and mixes in “perturbation” from higher key bits to avoid patterns and long runs. Table sizes are powers of two for fast indexing, and the probe step pseudo-randomizes the next slot while remaining cheap to compute. The design prioritizes the common case: very few probes, excellent locality, and simple mechanics that are fast in practice.What is MurmurHash and when should I use it?
MurmurHash is a fast, non-cryptographic hash family based on multiply-and-rotate operations. It produces well-distributed 32/64/128-bit hashes and supports seeding, making it a popular choice for data structures (hash tables, Bloom filters), partitioning, and analytics. It is not designed for security; use cryptographic hashes (e.g., SHA-2/3) for authentication or tamper resistance.How is hashing used in deduplication and plagiarism detection?
- Deduplication: Split files into chunks, hash each chunk to a fingerprint, and store only new fingerprints; duplicates reference existing data. This saves space and bandwidth, especially when snapshots differ slightly.- Plagiarism detection (e.g., MOSS): Use rolling hashes (Karp–Rabin) over k-grams, select representative fingerprints (e.g., per window minimums), build an inverted index, and verify only when hashes match. Rolling hashes allow constant-time updates as the window slides.
Algorithms and Data Structures for Massive Datasets ebook for free
