Distributional analysis of Robin Hood linear probing hashing with buckets
| Autor: | Alfredo Viola |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2005 |
| Předmět: |
distributional analysis
hashing linear probing buckets [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AD,..., Iss Proceedings (2005) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3386 |
| Popis: | 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 \alpha$ -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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|