title: Phase transition for parking blocks, Brownian excursion and coalescence
abstract: In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n<m), and l=m-n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car c/sub i/ chooses a place p/sub i/ at random, and if p/sub i/ is occupied, c/sub i/ tries successively p/sub i/+1, p/sub i/+2, until it finds an empty place. Pittel [42] proves that when l/m goes to some positive limit beta <1, the size B/sub 1//sup m,l/ of the largest block of consecutive cars satisfies 2( beta -1-log beta ) B/sub 1//sup m,l/=2 log m-3 log log m+ Xi /sub m/, where Xi /sub m/ converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B/sub 1//sup m,l/=o(m) and m-B/sub 1//sup m,l/=o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent
keyphrases: parking blocks Brownian excursion coalescence hashing linear probing empirical processes