DOAJ
Open Access
2005
Distributional analysis of Robin Hood linear probing hashing with buckets
Alfredo Viola
Abstrak
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.
Topik & Kata Kunci
Penulis (1)
A
Alfredo Viola
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2005
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.3386
- Akses
- Open Access ✓