Hashing: an expected bound is a claim about a distribution, and a user-typed key is an adversary

Unit three showed that an operation's name does not fix its cost. Hashing shows the cost depends on who supplies the input: a constant-time lookup says nothing about what decides whether it is true. A hash table's cost is expected over a distribution of keys, and the keys are supplied by whoever calls. A table whose keys a user types is a security surface before it is a data structure, and the keys arrive through an input the designer did not choose: speech input, a predictive keyboard, or a device a family shares.

The bound is a promise about the function, not about the keys

Carter and Wegman (1979) supplied the formulation the literature inherits. Their algorithm chooses a hash function at random from a suitable class. For any sequence of inputs the expected time, averaging over the class, is linear in the length of the sequence. The input is fixed and the function is random, so the bound holds for every input, including an awkward one. It holds only while the function is independent of the keys.

The same guarantee paid for in the worst case

The bound need not be expected. Fredman, Komlos and Szemeredi (1984) represent a static set of n items from a universe of m items in space n + o(n), with membership queries answered in constant time. Their basic construction answers a query with five probes and a table of at most 6n cells. Hashing answers a query in constant time on average, they note; theirs holds the worst case, at build time.

Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert and Tarjan (1994) pose the dynamic version, where a set supports insert, delete and lookup. Their randomised strategy gives constant worst-case lookup, constant amortised expected insertion and deletion, and space proportional to the set size. Deterministic linear-space schemes, they prove, pay at least a logarithmic factor in amortised worst-case time over n operations. That factor rises as k times the k-th root of n when lookup is bounded by k.

Two locations, and the tail rather than the mean

Pagh and Rodler (2004) give a simple dictionary with worst-case constant lookup, in space similar to that of binary search trees. It matches the performance of dynamic perfect hashing. It is open addressing in which keys move back along their probe sequences rather than perfect hashing. An implementation using weaker hash functions competes with the best average-case dictionaries.

The mean is not the whole description. Celis, Larson and Munro (1985) leave the contested slot to whichever element is further from its home position. That choice dramatically reduces the variance of probe counts, and it gives a search needing a constant number of probes on average even for a full table. In their experiments deletions and successful searches stay under 2.57 probes.

Provable hashing need not be slow, and a static table can sit near its floor

The standing objection to universal hashing is cost. Patrascu and Thorup (2011) show that simple tabulation hashing, which combines random table lookups on a key's characters, is not even 4-independent. It still supplies much of what higher independence is used for: Chernoff-type concentration, min-wise hashing, cuckoo hashing. Kirsch and Mitzenmacher (2008) show that two functions combined as h1 plus i times h2 implement a Bloom filter with no loss in the asymptotic false positive probability. The cheap construction is therefore the provable one.

A second result bounds the space instead. Belazzougui, Botelho and Dietzfelbinger (2009) give perfect hash functions with expected representation size close to optimal, construction time linear in the number of keys, and constant worst-case evaluation. They report 1.4 bits per key when the range is 1.23 times the number of keys, and 1.98 bits at 1.01 times. Where the key set is known in advance, the space needed sits near its information-theoretic floor.

The adversary the assumption ignores

Crosby and Wallach (2003) demonstrate the cost of forgetting the precondition. Hash tables degenerate to linked lists under carefully chosen input, and the authors attack the implementations in two versions of Perl, the Squid web proxy and the Bro intrusion detection system. With less bandwidth than a typical dialup modem they brought a dedicated Bro server to its knees. After six minutes of chosen packets it was dropping as much as 71 per cent of its traffic. Their repair, modern universal hashing, performs comparably while being provably secure.

The construction is cheap enough to follow. A fast hash keeps only 32 bits of state and mixes the input one byte at a time. An attacker can therefore search offline for short strings that return that state to where it started. Three such generators, concatenated in any order, all collide. So 46 generators yield 46 cubed, about 97,000 distinct 24-character keys with one hash value. Feeding 90,000 of them to Perl 5.6.1 took around 6,500 seconds. The same program on the keys the other version expected finished in under two seconds.

Aumasson and Bernstein (2012) supply the function. SipHash is a family of pseudorandom functions optimised for short inputs. Hash-table lookups protected against hash-flooding denial of service are among its target applications. It processes a 16-byte input with a fresh key in 140 cycles on an AMD FX-8150 processor, and the paper proposes that hash tables switch to it.

A controlled error is still the adversary's target

Bloom (1970) opened the second trade, trading the size of the hash area, the time to identify a nonmember and an allowable error frequency. Space is reduced by tolerating a small fraction of errors of commission. Such errors are tolerable where a large amount of data makes a core-resident hash area infeasible, and a much smaller hash area then suffices without a longer reject time. The error is one-sided, since a member always sets its own bits.

Fan, Andersen, Kaminsky and Mitzenmacher (2014) show how much the choice within that trade matters. A Bloom filter cannot delete, and earlier deletion-capable extensions degrade space or performance. Their cuckoo filter adds and removes items while using less space than a space-optimised Bloom filter for many items at moderately low false positive rates. Bender, Farach-Colton, Goswami, Johnson, McCauley and Singh (2018) then return to the adversary inside the approximate structure. The false positive probability holds for a single query, and an adversary can drive the rate towards 1 by repeating false positives. They prove that a small filter with a per-query guarantee independent of past answers is impossible, and they build an adaptive one at no asymptotic cost.

Contested question: is the expected bound a guarantee or a liability?

One position holds that expected time with a keyed function is the right engineering answer. Carter and Wegman (1979) show that a function drawn at random and independently of the keys gives expected linear time for every input sequence. Pagh and Rodler (2004) show a practical implementation competing with the best average-case dictionaries, and Kirsch and Mitzenmacher (2008) show the cheap construction losing nothing. An unkeyed table is an implementation mistake.

The opposing position holds that the expected bound should be replaced by a worst-case one wherever the keys come from outside. Crosby and Wallach (2003) measure the cost of the failure. Fredman, Komlos and Szemeredi (1984) and Dietzfelbinger and colleagues (1994) show the worst case is reachable in linear space, and Aumasson and Bernstein (2012) build the function for the hostile case. A bound that holds for a benign key set is a claim about a distribution the application does not own.

A third disagreement is about what the guarantee is about. Patrascu and Thorup (2011) show a function weaker than 4-independence still concentrates, and Bender and colleagues (2018) show the honest statement in the approximate structure is a probability for every query. A study that treats the key source as part of the specification would settle the disagreement. It would classify one interface's keys as internally generated or influenced by a user or a network peer. It would report the distribution of latency and of false positives over a query sequence, under an adversary who knows the implementation but not the key. No source here reports it.

Judge each side by its evidence. Carter and Wegman (1979) prove expected linear time for every input once the function is independent of the keys, a theorem with a stated precondition. Crosby and Wallach (2003) measure a table driven to a linked list, an exploited failure rather than a projection, and Fredman, Komlos and Szemeredi (1984) and Aumasson and Bernstein (2012) answer it with constructions. The strongest objection is that a keyed function costs work a table with application-generated keys does not need, so the repair is unpaid insurance. While the dispute is open, a designer asks who supplies the keys before choosing the function.

Where the argument is heading

The named work points the same way. Bender and colleagues (2018) turn an adversary against a query sequence into a design requirement at no asymptotic cost. Fan and colleagues (2014) let a filter be edited without giving up its space advantage, and Aumasson and Bernstein (2012) supply the keyed function the universal-hashing line asked for. Ordered trees and spatial indexes in later units, on this unit's own inference, may carry the same assumption.

The sources this unit rests on

• Aumasson, J. P. and Bernstein, D. J. (2012). SipHash: A Fast Short-Input PRF. Lecture Notes in Computer Science. doi:10.1007/978-3-642-34931-7_28 Aumasson and Bernstein present SipHash, a family of pseudorandom functions optimised for short inputs and aimed at hash-table lookups protected against hash flooding, processing a 16-byte input with a fresh key in 140 cycles. It is the unit's repair to the security surface.
• Belazzougui, D., Botelho, F. C. and Dietzfelbinger, M. (2009). Hash, Displace, and Compress. Lecture Notes in Computer Science. doi:10.1007/978-3-642-04128-0_61 Belazzougui, Botelho and Dietzfelbinger give perfect hash functions of near-optimal expected size with linear construction time, at 1.4 bits per key when the range is 1.23 times the number of keys. It shows how little space a static table needs.
• Bender, M. A., Farach-Colton, M., Goswami, M., Johnson, R., McCauley, S. and Singh, S. (2018). Bloom Filters, Adaptivity, and the Dictionary Problem. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). doi:10.1109/focs.2018.00026 Bender and colleagues show that a filter's false positive probability holds for a query, and that an adversary can drive the rate towards one by repeating false positives. They prove a per-query guarantee impossible for a small filter.
• Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM. doi:10.1145/362686.362692 Bloom analyses the trade between the size of the hash area, the time to identify a nonmember and an allowable error frequency, showing that tolerating errors of commission permits a much smaller area. It defines the one-sided trade later structures inherit.
• Carter, J. and Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences. doi:10.1016/0022-0000(79)90044-8 Carter and Wegman give an algorithm that chooses its hash function at random from a suitable class, so that for any input sequence the expected time is linear. Its force is conditional: the bound holds only while the function is independent of the keys.
• Celis, P., Larson, P. A. and Munro, J. I. (1985). Robin hood hashing. 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). doi:10.1109/sfcs.1985.48 Celis, Larson and Munro give an insertion procedure for open addressing that leaves the contested slot to whichever element is further from its home position. That reduces the variance of probe counts and gives a search of constant average cost.
• Crosby, S. A. and Wallach, D. S. (2003). Denial of service via algorithmic complexity attacks. USENIX Security Symposium. https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attacks Crosby and Wallach show that attacker-chosen keys can degenerate a hash table into a linked list, and attack the implementations in Perl, Squid and the Bro intrusion detection system. Six minutes of chosen packets cut Bro's throughput by 71 per cent.
• Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H. and Tarjan, R. E. (1994). Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM Journal on Computing. doi:10.1137/s0097539791194094 Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert and Tarjan give a randomised dictionary with constant worst-case lookup, constant amortised expected update and space proportional to the set size, and prove deterministic linear-space schemes pay a logarithmic factor. It is a worst-case guarantee with matching lower bounds.
• Fan, B., Andersen, D. G., Kaminsky, M. and Mitzenmacher, M. D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. doi:10.1145/2674005.2674994 Fan, Andersen, Kaminsky and Mitzenmacher give the cuckoo filter, which adds and removes items while using less space than a space-optimised Bloom filter at moderately low false positive rates. Earlier deletion-capable extensions degrade space or performance.
• Fredman, M. L., Komlos, J. and Szemeredi, E. (1984). Storing a sparse table with O(1) worst case access time. Journal of the ACM. doi:10.1145/828.1884 Fredman, Komlos and Szemeredi give a structure for a static set of n items from a universe of m, occupying space n + o(n), whose membership queries are answered in constant time with five probes. It is a worst-case bound for a known key set.
• Kirsch, A. and Mitzenmacher, M. (2008). Less hashing, same performance: Building a better Bloom filter. Random Structures and Algorithms. doi:10.1002/rsa.20208 Kirsch and Mitzenmacher show that two hash functions h1 and h2 combined as h1 plus i times h2 implement a Bloom filter without any loss in the asymptotic false positive probability. It justifies the shortcut the unit's argument depends on.
• Pagh, R. and Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms. doi:10.1016/j.jalgor.2003.12.002 Pagh and Rodler give a simple dictionary with worst-case constant lookup, matching dynamic perfect hashing in space similar to that of binary search trees, by allowing keys to move back along their probe sequences. It shows what the expected-case argument buys.
• Patrascu, M. and Thorup, M. (2011). The power of simple tabulation hashing. Proceedings of the forty-third annual ACM symposium on Theory of computing. doi:10.1145/1993636.1993638 Patrascu and Thorup show that simple tabulation hashing, which combines random table lookups on a key's characters, is not even 4-independent yet gives Chernoff-type concentration and supports cuckoo hashing. It answers the objection that good hashing must be slow.