Loading...
Please wait, while we are loading the content...
Similar Documents
Distributional analysis of Robin Hood linear probing hashing with buckets
| Content Provider | Semantic Scholar |
|---|---|
| Author | Viola, Alfredo Felipe |
| Copyright Year | 2006 |
| Abstract | This paper presents the first distributional analysis of a linear probing hashing scheme with buckets of size b . The exact distribution of the cost of successful searches for a bα -full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size m and n elements. A key element in the analysis is the use of a new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://dmtcs.episciences.org/3386/pdf |
| Alternate Webpage(s) | https://core.ac.uk/download/pdf/51441386.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
