PaperlayerView exact revision on arXiv

Source-linked AI summary

The Power of Simple Tabulation Hashing

Mihai Patrascu, Mikkel Thorup

arXiv:1011.5200v2cs.DS

TL;DR

The paper addresses whether practical hashing schemes can provide strong mathematical guarantees despite simple tabulation's key dependencies. It analyzes simple tabulation across randomized algorithms and finds strong guarantees, with competitive practical performance and implementations matching conceptual simplicity.

  • Problem

    Practical randomized algorithms need hashing schemes that combine simplicity with mathematical performance guarantees, but simple tabulation has significant dependence between keys.

  • Method

    The paper analyzes simple tabulation using concentration results and diverse techniques for table dependencies, including a complex random-graph analysis for cuckoo hashing.

  • Results

    Simple tabulation works in important randomized algorithms, including linear probing and cases previously requiring Ω(lg n)-independence, while remaining competitive with one 64-bit multiplication.

  • Takeaways & Limitations

    The analysis provides provably good implementations that often match an algorithm's conceptual simplicity when hashing is ignored.

  • Takeaways & Limitations

    The results assume a constant number of characters c = O(1), with bounds whose constants depend on c; for combinatorial cubes, exponential dependence on c and γ is inherent.

Abstract

from arXiv · show

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

1 Introduction

Simple tabulation hashing is exceptionally simple and fast, yet supports strong guarantees across concentration, linear probing, cuckoo hashing, minwise independence, and related applications despite substantial key dependencies.

  • Scheme: Simple tabulation hashes c-character keys by XORing independent random table lookups, using O(cu^(1/c)) words and cache-sized tables.The scheme is intended to fit in fast cache and is easy to implement.
  • Analytical approach: The analysis handles dependencies between keys rather than replacing simple tabulation with highly independent hashing.The authors state that this leaves one simple and fast scheme for almost all their needs.
  • Concentration: Chernoff-type concentration holds for hashing into sufficiently many bins, yielding polynomially small tail probabilities and standard maximum-load bounds.Theorem 1 applies when m ≥ n^(1−1/(2c)); the resulting bounds support maximum load O(lg n/lg lg n) w.h.p.
  • Linear probing: Linear probing achieves expected O(1/ε^2) time per operation when m=(1+ε)n, with constant variance for constant ε.This asymptotically matches the bound for truly random hashing and improves on the stated 5-independent comparison.
  • Cuckoo hashing: Cuckoo hashing succeeds with probability 1−O(n^−1/3), while some key sets have failure probability Ω(n^−1/3).The construction supports static dictionaries with linear expected construction time and constant worst-case query time after trying O(1) hash functions.
  • Additional guarantees: Simple tabulation also provides vanishing-error ε-minwise independence and fourth-moment bounds close to truly random hashing.The fourth moment differs by a factor 1+O(4c/m) for a fixed bin and is within a factor at most 2 for a designated query bin.

2 Concentration Bounds

Simple tabulation hashing preserves strong concentration guarantees despite dependence between keys, including for bins selected using a query hash. The analysis uses ordered groups with bounded contributions and independent random shifts, under constant-character assumptions.

  • Hashing into many bins: For hashing n elements into n^(1+ε) bins, simple tabulation preserves an O(1) maximum-load guarantee with high probability.The argument extracts sufficiently large peelable subsets from any overloaded set and uses their independence.
  • Scope and limitations: For combinatorial-cube key subsets, the exponential dependence on c and γ is inherent up to constant factors.This makes the probabilistic analysis sharp in that setting.
  • Chernoff bounds: The fixed-bin proof partitions keys into groups G_α and orders position-characters so every group has size at most n^(1−1/c).After bounding group contributions, each new position-character supplies a random shift, enabling Chernoff analysis.
  • Chernoff bounds: The query-dependent ordering increases the maximal group size only to 2 · n^(1−1/c), without changing the asymptotic concentration analysis.The first nonempty group contains only the query, and subsequent groups retain shifts independent of its hash code.
  • Chernoff bounds: Simple tabulation supports Chernoff-type concentration for bin loads, including bins selected as a function of a query hash.The query-dependent analysis orders query characters first, making later group shifts independent of the query hash while preserving the needed expectations.
  • Scope and limitations: The guarantees assume c = O(1), and the stated Chernoff-style error bounds are polynomially small, m^−γ, for constant γ.The analysis notes that stronger error bounds are possible but become less clean.

3 Linear Probing and the Concentration in Arbitrary Intervals

Simple tabulation yields concentration bounds for arbitrary intervals that translate into efficient linear probing. Its probe costs remain within constant-factor behavior of truly random hashing across high- and low-fill regimes.

  • Linear probing: Simple tabulation keeps linear probing within constant-factor performance of truly random hashing at both high and low fill.At high fill, expected insertion probes are O(1/ε^2); at low fill, they are 1 + O(α).
  • Arbitrary intervals: Theorem 8 bounds deviations in every interval containing a specified point, including points determined by a query hash.For δ ≤ 1 the bound is 2e^−Ω(αℓδ^2) + (ℓ/m)^γ; for δ = Ω(1) it is (1 + δ)^−Ω((1+δ)αℓ) + (ℓ/m)^γ.
  • Arbitrary intervals: The interval analysis decomposes ranges into dyadic intervals, whose expected load is μ_j = α2^j, and handles deviations through dangerous subintervals.The decomposition supports applying the bin-concentration theorem across multiple scales.
  • Linear probing: For high fill, probe-run length concentrates around Θ(1/ε^2), with E[R(q,S)^p] = O(1/ε^(2p)) for constant p.The tail bound is 2e^−Ω(ℓε^2) + (ℓ/m)^γ when α ≥ 1/2.
  • Linear probing: For an unsuccessful query at low fill, every constant moment satisfies E[R(q,S)^p] = O(α).The result combines O(α) probability of filling a query-dependent location with exponential decay for larger runs.
  • Linear probing: For a query already in the set, every constant moment satisfies E[R(q,S)^p] = 1 + O(α).This covers the probe-run cost relevant to deletions and successful searches.

4 Cuckoo Hashing

The cuckoo-hashing analysis identifies a constant-sized obstruction and proves that simple tabulation achieves the optimal failure-probability order for every key set, while matching a hard instance.

  • Obstructions: Three keys sharing two left locations and two keys sharing one right pair create six edges occupying only five positions, so cuckoo hashing fails.This obstruction occurs on the 3-dimensional cube instance.
  • Obstructions: The hard cube instance fails with probability Ω(n^-1/3), because the left collision has constant probability and the right collision has probability Ω(1/n^1/3).The two events combine to give the stated lower bound.
  • Main bound: For every set S, the failure probability is O(n^-1/3), matching the hard instance up to constants.Thus the cube obstruction gives the worst possible asymptotic order under simple tabulation.
  • Encoding proof: An encoding argument bounds failure by saving entropy from the hash-function description, using local modifications to operations along obstruction walks.The construction accounts for the initial identifier cost and obtains the required overall saving.
  • Encoding proof: The proof represents failed cuckoo hashing as an overfull component in a bipartite graph, containing either a chorded cycle or two cycles joined by a path.Cuckoo hashing succeeds exactly when every component has at most as many edges as nodes.

5 Minwise Independence

The paper analyzes minwise independence by partitioning hash values into bins and controlling dependencies through character-order exposure, representatives, and collision bounds.

  • Setup: The analysis partitions the output range into n^ℓ bins and focuses on the minimum bin to study whether a query key is smaller than all keys in S.The minimum bin is chosen so that it is nonempty with high probability.
  • Setup: For truly random hashing, conditioning on h(q)=p gives Pr[p < min h(S)] = (1-p)^n.This is the benchmark probability for the minwise analysis.
  • Upper bound: Characters are exposed in a fixed order, making each newly revealed character act as a uniform shift for its associated key group.This permits conditional probability bounds despite dependencies among keys.
  • Upper bound: Representative sets control collisions within groups, while d-boundedness prevents keys from clustering in too few bins.The dynamic representative view sharpens the initial bound based on static representatives.
  • Conclusion: The completed analysis establishes the stated bound on minwise independence.The upper-bound argument combines the group analysis and the auxiliary probability lemma.

6 Fourth Moment Bounds

The fourth-moment analysis extends from fixed bins to bins selected by a query hash, showing how simple tabulation controls dependent four-key configurations and query-dependent selection.

  • Setup: The target is the fourth central moment E[(W-μ)^4] of weighted balls landing in a bin selected by F(h(q)).Here q is a designated query ball and W is the total weight in the selected bin.
  • Fixed-bin bound: Terms containing a key exactly once vanish, leaving only configurations with one key repeated four times or two keys repeated twice.This yields the standard fourth-moment decomposition.
  • Fixed-bin bound: For simple tabulation, configurations involving at most three distinct keys match the corresponding independent expectations because the scheme is 3-independent.Distinct four-key configurations require a combinatorial matrix-type analysis.
  • Query-dependent bin: The query-dependent fourth moment equals the fixed-bin fourth moment plus an additional term for the remaining dependent configuration.This is the principal reduction for a bin chosen through h(q).
  • Query-dependent bin: Among any five distinct keys, one key has a hash independent of the other four, enabling the query-dependent fourth-moment analysis.The proof uses this structural property to factor dependent terms when the query is involved.
  • Limitation: The resulting bound is weaker than the standard Chernoff-style comparison in its tail behavior, with variance O(log n) when ε=1/2.For moments p≥3, the stated bound is O(np-2).

A Experimental Evaluation

The experiments compare simple tabulation with realistic hashing schemes on random and structured inputs, including linear probing and cuckoo hashing.

  • Experimental design: The experiments include simple tabulation alongside other schemes in applications, including cuckoo hashing, which was absent from earlier experiments.The evaluation focuses on common 32- and 64-bit key sizes.
  • Experimental design: The evaluation compares hashing speed on random input and hash quality on dense intervals and the hypercube.The hypercube is treated as a likely worst-case structured input for simple tabulation.

A.1 Multiplication-shift Hashing

Multiplication-shift hashing uses machine multiplication and bit shifts for universal or 2-independent hashing, but stronger independence can require wider arithmetic or multiple multiplications.

  • A.1 Multiplication-shift Hashing: Universal multiplication-shift hashing selects a random odd multiplier and shifts the product to obtain the desired output width.The product is computed modulo 2^ℓ, and right shifting removes the least significant bits.
  • A.1 Multiplication-shift Hashing: Universal multiplication-shift hashing is far from 2-independent because keys differing only in their least significant bit retain that difference after hashing.This limitation follows from the low-bit behavior of multiplication modulo 2^ℓ.
  • A.1 Multiplication-shift Hashing: 2-independent multiplication-shift hashing uses a random 2ℓ-bit multiplier and additive constant, with specialized variants avoiding simulated 128-bit multiplication.For 64-bit keys, a two-part 32-bit representation enables a faster construction using two 64-bit multiplications.

A.2 Polynomial Hashing

Polynomial hashing provides general k-independence through random polynomials over prime fields, while Mersenne primes enable faster bitwise implementations; practical higher-independence hashing remains costly.

  • A.2 Polynomial Hashing: General k-independent hashing uses a degree k −1 polynomial over a prime field with randomly chosen coefficients.The prime is chosen much larger than the desired output domain.
  • A.2 Polynomial Hashing: Mersenne primes of the form 2^i −1 allow polynomial hashing to use shifts and bitwise Boolean operations instead of slow general modular reduction.This provides a faster implementation than arithmetic modulo an arbitrary prime.
  • A.2 Polynomial Hashing: The 5-independent implementation uses p = 2^61 −1 for 32-bit keys and p = 2^89 −1 for 64-bit keys.These parameter choices instantiate the Mersenne-prime scheme for the two key widths.
  • A.2 Polynomial Hashing: Standard 64-bit multiplication may require four multiplications to implement full multiplication modulo 2^61 −1, making specialized 2-independent schemes much faster.The authors do not know a practical generalization for higher independence.

A.3 Tabulation-Based Hashing

Tabulation-based hashing replaces multiplication with cache-sized table lookups. Simple tabulation xors random values indexed by a key’s characters, while derived characters provide higher independence at added complexity.

  • A.3 Tabulation-Based Hashing: Tabulation-based schemes replace multiplications with lookups in tables small enough to fit in fast memory.The design targets efficient access to precomputed random values.
  • A.3 Tabulation-Based Hashing: Simple tabulation divides a key into c characters and returns the xor of one random table value for each character.Its tables are easy to populate with random data, but the scheme is only 3-independent.
  • A.3 Tabulation-Based Hashing: Using 8-bit characters gives better performance than 16-bit characters because the smaller tables fit in the fast L1 cache.The experiments cited by the authors support the 8-bit choice used in their implementation.
  • A.3 Tabulation-Based Hashing: The 5-independent tabulation scheme adds derived characters, requiring 2c −1 lookups for c-character keys.For two characters, the derived character is x_1 + x_2; the resulting scheme is complicated but runs well.

A.4 Hashing in Isolation

The isolation experiments compare hash computation across key widths, machines, and independence levels. Simple tabulation is competitive with multiplication-shift hashing and substantially faster than the more complicated 5-independent tabulation scheme for 32-bit keys.

  • A.4 Hashing in Isolation: The experiments measure average hash-computation time for 10 million computations on separate 32-bit and 64-bit computers.The schemes are tested for 32-bit-to-32-bit and 64-bit-to-64-bit hashing.
  • A.4 Hashing in Isolation: The 64-bit computer benefits more when 64-bit multiplication is critical, including universal multiplication-shift, 2-independent multiplication-shift, and 5-independent Mersenne-prime hashing.The comparison concerns the schemes whose implementations depend most directly on 64-bit multiplication.
  • A.4 Hashing in Isolation: For 32-bit keys, simple tabulation performs similarly to 2-independent multiplication-shift on both computers.This comparison evaluates isolated hash computation rather than a full hash-table workload.
  • A.4 Hashing in Isolation: For 32-bit keys, simple tabulation is more than twice as fast as the more complicated 5-independent tabulation scheme.The result holds on both computers tested.
  • A.4 Hashing in Isolation: For 64-bit keys, simple tabulation becomes more than twice as slow because its table space grows from 1KB to 8KB, potentially increasing cache misses.The implementation performs twice as many lookups and uses twice as many tables with twice as large entries.
  • A.4 Hashing in Isolation: Overall, simple tabulation is faster than 2-independent multiplication-shift on the 32-bit computer and less than twice as slow on the 64-bit computer.The authors therefore regard its speed as competitive.

A.5 Linear Probing

Experiments show that simple tabulation remains efficient and tightly concentrated for random and structured inputs, unlike multiplication-shift schemes on dense intervals and hypercubes. It is competitive with fast multiplication-shift hashing and about 20% faster than the fastest 5-independent scheme in linear probing.

  • Experimental setup: The experiments average update time over 10 million insert/delete cycles using 2^20 32-bit keys in a table with 2^21 entries.The table uses 8MB and does not fit in either computer's cache.
  • Random input: The average number of probes per update was tightly concentrated around 3.28 for random input.Across 100 experiments, each data point deviated by less than 1%.
  • Random input: Simple tabulation was about 20% faster than the fastest 5-independent scheme and competitive with the fast multiplication-shift scheme.The common linear-probing table cost limits the possible multiplicative speedup.
  • Structured input: On dense intervals, simple tabulation and 5-independent schemes remained tightly concentrated while multiplication-shift schemes showed significant variation and sometimes used far more probes.The dense-interval input is a structured case known to cause unreliable performance for many simple hashing schemes.
  • Structured input: Simple tabulation stands out among simple fast hashing schemes by not failing on dense intervals, while hypercubes provide a plausible worst-case input for further testing.The hypercube experiment used the set [32]^4 for 2^20 keys.
  • Structured input: Simple tabulation remained robust on structured inputs, although probe deviations grew from below 0.5% with random input to almost 1%.The authors state that experiments cannot establish robustness for every possible input; the analysis gives strong concentration but with large hidden constants.

B Chernoff Bounds with Fixed Means

The paper establishes Chernoff bounds for bounded random variables whose conditional means remain fixed despite dependence. The proof generalizes the standard independent-variable argument by induction and Markov's inequality.

  • Statement: Chernoff bounds hold for possibly dependent variables when each variable's conditional expectation is fixed regardless of preceding values.The variables lie in [0,1], and E[Xi|X<i = x<i] = µi for every preceding assignment.
  • Statement: For X = Σi Xi with mean µ = Σi µi, the proposition gives upper- and lower-tail bounds for every δ > 0.The lower-tail case follows by a symmetric argument.
  • Proof: The proof proceeds by induction on the number of variables, extending the standard proof for independent variables.The conditional-mean assumption supplies the key step for the final variable.
  • Proof: Markov's inequality converts the inductive exponential-moment bound into the desired probability bound.The argument handles the upper tail directly and obtains the lower tail symmetrically.
Loading 1011.5200v2…