Name
Abstract | ||
|---|---|---|
We extend a result of Goldreich and Ron about estimating the collision probability of a hash function. Their estimate has a polynomial tail. We prove that when the load factor is greater than a certain constant, the estimator has a gaussian tail. As an application we find an estimate of an upper bound for the average search time in hashing with chaining, for a particular user (we allow the overall key distribution to be different from the key distribution of a particular user). The estimator has a gaussian tail. |
Year | Venue | Keywords |
|---|---|---|
2003 | Clinical Orthopaedics and Related Research | key distribution,hash function,data structure,hash table,upper bound |
Field | DocType | Volume |
Primary clustering,Discrete mathematics,Double hashing,Rolling hash,Universal hashing,SUHA,K-independent hashing,Hash function,Mathematics,Dynamic perfect hashing | Journal | cs.DS/0303 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dawei Hong | 1 | 85 | 12.80 |
| Jean-Camille Birget | 2 | 815 | 59.09 |
| Shushuang Man | 3 | 61 | 10.13 |