What people are saying - Write a review
We haven't found any reviews in the usual places.
THE ANALYSlS OF DOUBLE HASHlNG
1 other sections not shown
analysis argument arithmetic progressions coming assume average number bad insertions Bernoulli trials binomial coefficients bound bucket search coming from H compute configuration Corollary disjoint double hashing elements empty position empty slot expected number extension process Farey series Figure fixed table fixpoint flows hash function hash sequences hash table hashing algorithm hits hypergeometric distribution intersection intervals k-ary clustering techniques KEY[i Knuth2 Lemma length k coming linear probing LlNK[i ln order ln Section load factor number of arithmetic number of comparisons number of probes number of progressions occupied positions open addressing technique oracle overflow area overflow items performance probe path progressions of length progressions of type Proof prove random probes ratio a:b recurrence relation relative errors residual progressions secondary clustering small positive constant specified subset tertiary clustering Theorem Tjm points total number type t coming uniform hashing unsuccessful search Y+Tj