On the Analysis of Linear Probing Hashing
| Autor: | Patricio V. Poblete, Alfredo Viola, Philippe Flajolet |
|---|---|
| Rok vydání: | 1998 |
| Předmět: |
General Computer Science
Applied Mathematics Linear probing Order (ring theory) 0102 computer and information sciences Type (model theory) 01 natural sciences Computer Science Applications Combinatorics 010104 statistics & probability Tree (descriptive set theory) Distribution (mathematics) Airy function 010201 computation theory & mathematics Limit (mathematics) 0101 mathematics Connectivity Mathematics |
| Zdroj: | Algorithmica. 22:490-515 |
| ISSN: | 0178-4617 |
| DOI: | 10.1007/pl00009236 |
| Popis: | This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash tables under the linear probing strategy. Two models are considered, that of full tables and that of sparse tables with a fixed filling ratio strictly smaller than one. For full tables, the construction cost has expectation O(n 3/2 ) , the standard deviation is of the same order, and a limit law of the Airy type holds. (The Airy distribution is a semiclassical distribution that is defined in terms of the usual Airy functions or equivalently in terms of Bessel functions of indices $ -\frac{1}{3},\frac{2}{3} $ .) For sparse tables, the construction cost has expectation O(n) , standard deviation O ( $ \sqrt{n} $ ), and a limit law of the Gaussian type. Combinatorial relations with other problems leading to Airy phenomena (like graph connectivity, tree inversions, tree path length, or area under excursions) are also briefly discussed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink