INDIVIDUAL DISPLACEMENTS FOR LINEAR PROBING HASHING WITH DIFFERENT INSERTION POLICIES

SVANTE JANSON

Abstract. We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)

We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finite m and n can be obtained from the limits as m, n → ∞.

We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.

1. Introduction

The standard version of hashing with linear probing can be described as follows, where n and m are integers with 0 ≤ n ≤ m. (For a thorough discussion, see Knuth [15, Section 6.4, in particular Algorithm 6.4.L].)

n items x_{1}, …, x_{n} are placed sequentially into a table with m cells 1, …, m, using n integers h_{i} ∈ {1, …, m}, by inserting x_{i} into cell h_{i} if it is empty, and otherwise trying cells h_{i} + 1, h_{i} + 2, …, until an empty cell is found; all positions being interpreted modulo m.

For our probabilistic treatment, we assume that the hash addresses h_{i} are independent random numbers, uniformly distributed on {1, …, m}. In other words, each of the m^{n} possible hash sequences (h_{i})_{1}^{n} has the same probability m^{−n}.

If item x_{i} is inserted into cell q_{i}, then its displacement is d_{i} := (q_{i} − h_{i}) mod m. This is the number of unsuccessful probes when this item is inserted, as well as each time we later search for the item in the table. (The number of probes to find the item in the table is thus d_{i} + 1. This should be noted

Date: June 15, 2003; revised November 21, 2003; June 1, 2005. 1991 Mathematics Subject Classification. Primary: 68W40, 68P10; Secondary: 60C05,

60F05.

This work was first presented at the Knuthfest in honour of Donald Knuth’s 64th birthday in January 2002.

This is a preprint of an article accepted for publication in ACM Transactions on Algorithms \begin{matrix}c \\ ◯ \end{matrix} 2005 by the Association for Computing Machinery, Inc.

when comparing the results below with other papers.) The displacement is a measure of the time (or cost) to find the item in the table; for simplicity we say that the search time is the displacement.

We began our study of hashing with linear probing in [10], where we studied the total displacement ∑_{i} d_{i}. In the present paper, we will study the individual displacements.

It turns out that the version of hashing described above leads to large variations among the displacements, especially for full or almost full tables. Several people have therefore suggested variations of the basic algorithm. We will study three versions of hashing with linear probing, differing in their insertion policies when there is a conflict.

FC First-Come(-First-Served). The usual version described above where the first item that probes a cell is inserted there and remains there. LC Last-Come(-First-Served), see Poblete and Munro [22]. Each new item is inserted where it arrives. If the cell is already occupied, the old inhabitant is moved to the next cell. If that too is occupied, its old inhabitant is moved, etc.

RH Robin Hood, see Celis, Larson and Munro [4] and [15, Answer 6.4-67]. When an item wants a cell that is already occupied by another item, the item (of the two) with the largest current displacement is put in the cell and the other is moved to the next cell, where the same rule applies recursively. (Ties are resolved in either way.) Robin Hood hashing minimizes the variance of the displacements for all linear probing algorithms [3], [23].

Note that the insertion of a sequence of items results in the same set of occupied cells in all three versions, and thus the same total displacement, while the individual displacements may differ. As has been shown before, and is seen by our results below, the Last Come and Robin Hood versions tend to give more evenly distributed displacements, thus reducing extreme values that may be annoying or dangerous. Remark 1.1. It has been suggested [22, 23] that the displacements in the LC and RH versions may be so concentrated around their mean that searches would be quicker using centered probing, first probing cells at the mean displacement from the hash address. This seems to be true for double hashing and random probing, but we will see in Section 11 that for hashing with linear probing, this is not the case.

The situation we consider in this paper is a computer program where a large hash table is constructed once, and then used many times for finding the items. We mainly consider successful searches, although we give results for unsuccessful searches too, and we always assume that each item in the table is equally likely to be requested. We therefore have two levels of randomness: given a hash table T , and its displacements (d_{i}), the time to find a random element in the table is a random variable d(T ) = d_{I}, where I ∈ {1, …, n} is a uniformly distributed random index. As the program runs with many searches in the hash table, the search times are independent observations of this random variable. It is thus interesting to study the distribution of this random variable and its properties such as its mean and variance, and perhaps the probability of extremely large values. Note that this distribution depends on T .

On the other hand, the hash table T is itself random; another run of the program yields another T and another set of displacements. Hence the distribution of the displacement d(T ) is a random distribution and its mean 𝔼(d(T )|T ) and variance Var(d(T )|T ) = 𝔼(d(T )^{2}|T ) − 𝔼(d(T )|T )^{2} are random variables.

As has been noted earlier, see e.g. [10], the asymptotic behaviour of hashing with linear probing when n and m and tend to ∞ depend on the relative size of m and n. We will in the present paper, for simplicity as well as for lack of time and space, only consider the case n/m → α with 0 < α < 1. (This is also the range of most interest for computer applications.) The case n/m → 0 is more degenerate, with most displacements 0, and will be ignored. (It can be treated by similar methods, cf. the discussion of the total displacement in [10].) It will be seen below, that in this range, the dependency on T is negligible. For example, the mean and variance above, which are functions of T , converge after suitable scaling in probability to some constants. In other words, we observe essentially the same distribution of search times for every run of the program.

The case n/m → 1 is mathematically very interesting, and we plan to treat it in a later paper (jointly with Philippe Chassaing). There are two subcases, again cf. [10]: If m − n ≫ \sqrt{n}, the results are similar to those in the present paper (but in some respects simpler); in particular, the random variation between different hash tables T is insignificant. On the other hand, in the almost full case when (m−n)/\sqrt{n} → c for some c ≥ 0, the dependency on T is important and e.g. the mean 𝔼(d(T )|T ) has a non-degenerate limit in distribution. Moreover, this is the Brownian phase, where the limits can be described using Brownian motion and derivatives of it such as the Brownian excursion.

The paper begins with some definitions and other preliminaries in Sections 2 and 3. A general limit theorem is given in Section 4 together with some variations.

In Section 5 we review these limit results in the context of the diagonal Poisson transform introduced by Poblete, Viola and Munro [23, 28]. This will show that the limit as m, n → ∞ with n/m → α of, for example, a certain moment of the displacements in random hash tables, equals a certain generating function (the Poisson transform) of the same moment. By inverting the Poisson transform, we are thus able to derive exact expressions for finite m and n from the limits as m, n → ∞, a rather unusual situation!

The limit distributions for the different versions are found explicitly (more or less) in Sections 6–9. The reader will observe that our results for Last Come are much less satisfactory than for the other versions, and it is possible that others will succeed to find simpler forms of the result.

To illustrate the limit distributions, some numerical probabilities are given in Section 10.

Finally, the mode of the limit distributions are studied in Section 11, with a mixture of theorems, numerically based conjectures and open questions.

n\underline{k} := n(n − 1) ⋯ (n − k + 1) denotes the falling factorial.

Acknowledgements. This paper is part of a joint project with Philippe Chassaing. I am also grateful to Alfredo Viola and Patricio Poblete for helpful discussions. Many related results, including some of the results below, have independently been found by Viola [29] by related but differently formulated methods. The reader is invited to compare (and combine) the two approaches.

2. Preliminaries

By a hash table T we mean not only the final table, but also its construction history; moreover, we consider the three possible results and construction histories under the three different policies together. Formally, a hash table can be regarded as encoded by the numbers m and n and the sequence (h_{1}, …, h_{n}) of hash addresses. We always let m = m(T ) be the number of cells and n = n(T ) the number of items in the table. Thus there are m−n empty cells. We always have 0 ≤ n ≤ m. We sometimes exclude the cases n = 0 or n = m to avoid trivial complications.

Our prime object of study is the random hash table T_{m,n} with m cells and n items (0 ≤ n ≤ m) and the hash addresses h_{1}, …, h_{n} i.i.d. random variables, uniformly distributed on {1, …, m}. (This random hash table thus has a fixed size. In the analysis below we will also meet random hash tables where both the size and the number of items are random, see Section 3.)

We say that a hash table is confined if it leaves the last cell empty. We let T′_{m,n} (n < m) denote a random confined hash table, defined as T_{m,n} conditioned on the last cell being empty. By symmetry, the sequence of displacements has the same distribution for T′_{m,n} as for T_{m,n}.

We denote the three insertion policies defined in the introduction by FC, LC and RH, and use Ξ to denote any of these.

Given a hash table T , random or not, and a policy Ξ ∈ {FC, LC, RH}, we let d_{i}^{Ξ}(T ) be the (final) displacement of the i:th item, 1 ≤ i ≤ n, and

n_{k}^{Ξ}(T ) := #{i : d_{i}^{Ξ}(T ) = k}, k = 0, 1, …,

the number of items with displacement k. Note that

∑_{k} n_{k}^{Ξ}(T ) = n.  (2.1)

The total displacement is

d^{∗}(T ) := ∑_{i=1}^{n} d_{i}^{Ξ}(T ) = ∑_{k=0}^{∞} kn_{k}^{Ξ}(T )

and the average displacement is, when n > 0,

d̄(T ) := \frac{1}{n}d^{∗}(T ) = \frac{1}{n} ∑_{i=1}^{n} d_{i}^{Ξ}(T ).

As remarked above, d^{∗}(T ) and d̄(T ) do not depend on the policy Ξ.

If n > 0, we let d^{Ξ}(T ) denote a randomly chosen displacement in a given hash table T using policy Ξ, i.e. the random variable d_{I}^{Ξ}(T ) where I ∈ {1, …, n} is a random index with a uniform distribution. Thus, given T , d^{Ξ}(T ) has the distribution

ℙ(d^{Ξ}(T ) = k) = \frac{1}{n}n_{k}^{Ξ}(T )  (2.2)

and the expectation

𝔼 d^{Ξ}(T ) = d̄(T ).

Similarly, we let d_{j}^{U}(T ) denote the number of occupied cells encountered in an unsuccessful search starting at hash address j, 1 ≤ j ≤ m, and let d^{U}(T ) denote the number of occupied cells encountered in a random unsuccessful search, i.e. d^{U}(T ) := d_{J}^{U}(T ), where J ∈ {1, …, m} is a uniformly distributed random index. (As for successful searches, the number of probes thus is one more, d_{j}^{U}(T ) + 1 and d^{U}(T ) + 1.) We further let

n_{k}^{U}(T ) := #{j : d_{j}^{U}(T ) = k}, k = 0, 1, …,

and note that now, in contrast to (2.1),

∑_{k} n_{k}^{U}(T ) = m.  (2.3)

Thus, given T , d^{U}(T ) has the distribution

ℙ(d^{U}(T ) = k) = \frac{1}{m}n_{k}^{U}(T ).

2.1. Blocks. A block in a hash table (with n < m) is a sequence of cells {i + 1, …, j} (modulo m) where i and j are two consecutive empty cells; thus the last cell in a block is empty but all others are occupied. Clearly, T contains m−n blocks which form a partition of {1, …, m}. We denote the block lengths in T by ℓ_{1}(T ), …, ℓ_{m−n}(T ). (In the confined case, we take the blocks in the natural order, but in the unconfined case we start at a randomly chosen block. Otherwise, if for example in the unconfined case we would let the first block be the block containing cell 1, we would introduce an unwanted bias.)

Note that by our convention, each block includes the final, empty cell. Hence each block length is ≥ 1, and a block of length 1 is just a single empty cell (preceded by another empty cell). Further,

∑_{i=1}^{m−n} ℓ_{i}(T ) = m.

Each block may be regarded as an almost full confined hash table, with ℓ cells and ℓ − 1 items, where ℓ is the length of the block.

The block lengths ℓ_{i} do not depend on the insertion policy.

If B is a block of length ℓ in T , then the ℓ values of d_{j}^{U}(T ) for j ∈ B are ℓ − 1, ℓ − 2, …, 0. Hence, for k = 0, 1, …,

n_{k}^{U}(T ) = #{i : ℓ_{i}(T ) > k}.  (2.4)

We further see that d_{j}^{U}(T ) and d^{U}(T ) do not depend on the insertion policy.

2.2. Profile. Let, for j = 1, …, m, X_{j} := {i : h_{i} = j} be the number of items with hash address j. Further, let H_{j} be the number of items that make an attempt to be inserted in cell j, whether they succeed or not. We extend these definitions to arbitrary integer indices by interpreting the index j modulo m. We call (H_{j})_{j=1}^{m} the profile of the hashing. If H_{j} ≥ 1, then exactly one of the H_{j} items that try cell j ends up there, while the remaining H_{j} − 1 items either are rejected immediately or are admitted first but later thrown out; thus these continue to cell j + 1, and

H_{j+1} = X_{j+1} + (H_{j} − 1)_{+}.

When n < m, this set of equations has a unique solution [15, Exercise 6.4-32], [10, Lemma 2.1]

H_{j} = max_{−∞<i≤j}(∑_{k=i}^{j} X_{k} − (j − i)).

In particular, the profile does not depend on the insertion policy.

The profile has a simple relation to Robin Hood hashing.

Lemma 2.1. For Robin Hood,

n_{k}^{RH}(T ) = #{i : d_{i}^{RH} = k} = #{j : H_{j} = k + 1}.

In other words, the displacements (d_{i}^{RH})_{i=1}^{n} are a permutation of the numbers (H_{j} − 1)_{j=1}^{m}, ignoring the m − n negative values when H_{i} = 0.

Proof. Consider a cell j and the X_{j} items that arrive at j. Under the RH rule, the final order of the items in a block is the same as the order of their places of arrivals. Hence, the (H_{j−1} − 1)_{+} items that try cell j − 1 but are rejected (immediately or later) and therefore continue and try cell j, will end up in cells j, …, j+(H_{j−1} − 1)_{+}−1, and the X_{j} items that arrive at place j will end up in j+(H_{j−1} − 1)_{+}, …, j+(H_{j−1} − 1)_{+}+X_{j} −1, Consequently, the displacements of these X_{j} items are (H_{j−1} − 1)_{+}, …, (H_{j−1} − 1)_{+} + X_{j} − 1 = H_{j} − 1. In particular, these displacements are all different, and, if k ≥ 0, one of them equals k if and only if H_{j−1} − 1 ≤ k ≤ H_{j} − 1. Hence,

\begin{aligned}n_{k}^{RH} & = #\{j : H_{j−1} − 1 ≤ k ≤ H_{j} − 1\} \\ & = #\{j : H_{j−1} ≤ k + 1 ≤ H_{j}\}. \end{aligned}  (2.5)

Consider the sequence {H_{j}}, where the index runs through {1, …, m} regarded as a cycle, with 1 following m. The number of times H_{j} increases across [k, k+1] has to equal the number of times it decreases across the same interval, and since H_{j} − H_{j−1} ≥ −1 always, such a decrease can only be from k + 1 to k.

Hence, (2.5) yields

n_{k}^{RH} = #{j : H_{j−1} ≤ k + 1 ≤ H_{j}}
= #{j : H_{j−1} = k + 1 ≤ H_{j}} + #{j : H_{j−1} ≤ k < k + 1 ≤ H_{j}}
= #{j : H_{j−1} = k + 1 ≤ H_{j}} + #{j : H_{j−1} = k + 1 > k = H_{j}}
= #{j : H_{j−1} = k + 1}.  □

3. Random blocks and infinite hashing

Let T (z) be the tree function

T (z) := ∑_{l=1}^{∞} \frac{l^{l−1}z^{l}}{l!} ,  |z| ≤ e^{−1}.  (3.1)

Recall the well-known formulas T (z)e^{−T (z)} = z (|z| ≤ e^{−1}), T (αe^{−α}) = α (0 ≤ α ≤ 1),

∑_{l=1}^{∞} \frac{l^{l−2}z^{l}}{l!} = T (z) − \frac{1}{2}T (z)^{2}  (3.2)

and

T′(z) = \frac{T (z)}{z(1 − T (z))}.  (3.3)

We say, for 0 ≤ α ≤ 1, that a random variable B_{α} has the Borel distribution Bo(α) if

ℙ(B_{α} = l) = \frac{l^{l−1}}{l!} α^{l−1}e^{−lα} = \frac{1}{T (αe^{−α})} \frac{l^{l−1}}{l!} (αe^{−α})^{l},  l = 1, 2, … (3.4)

(B_{α} always denotes such a variable.) The probability generating function of the Borel distribution is

𝔼 z^{B_{α}} = ∑_{l=1}^{∞} ℙ(B_{α} = l)z^{l} = \frac{T (αe^{−α}z)}{T (αe^{−α})} = \frac{T (αe^{−α}z)}{α}.  (3.5)

Moments are easily computed from this. In particular, see e.g. [10, §4],

𝔼 B_{α} = \frac{1}{1 − T (αe^{−α})} = \frac{1}{1 − α},  (3.6)
𝔼 B_{α}^{2} = \frac{1}{(1 − α)^{3}} .  (3.7)

As shown in [10, Lemma 4.1], for any α > 0, the sequence of block lengths {ℓ_{i}(T_{m,n})}_{i=1}^{m−n} of the random hash table T_{m,n} or T′_{m,n} has the same distribution as a sequence {X_{i}}_{i=1}^{m−n} of independent random variables X_{i} with the common distribution Bo(α), conditioned on ∑_{i=1}^{m−n} X_{i} = m. Moreover, conditioned on the block lengths ℓ_{i}, the internal structures of the blocks are independent, and the same as for a sequence of independent random almost full confined hash tables T′_{ℓ_{i},ℓ_{i}−1}, i = 1, …, m − n.

We let T_{α}, where 0 ≤ α ≤ 1, denote the random hash table of random size constructed by first selecting ℓ at random with the Borel distribution Bo(α), and then taking a random confined hash table T′_{ℓ,ℓ−1}. (Thus T_{α} is a confined hash table.) The result just quoted then implies the following.

Lemma 3.1. The random confined hash table T′_{m,n} can be obtained by juxtaposing m − n independent copies of T_{α}, conditioning on the total size being m. The random hash table T_{m,n} can be obtained by first constructing T′_{m,n} in this way, followed by a random cyclic shift. Here α is any number with 0 < α ≤ 1. □

Remark 3.2. There is a one-to-one correspondence between hash tables and rooted forests, see e.g. [15, Exercise 6.4-31] and [5], and the lemma is essentially equivalent to a result for random rooted forests by Pavlov [17, 19, 20]. Furthermore, Lemma 3.1 is closely related to results for generating functions for the total displacement in [7, 16].

Next, let us observe that the Borel distribution arises in connection with random walks. More precisely, let ξ_{1}, ξ_{2}, … be i.i.d. random variables with the Poisson distribution Po(α), and let S_{k} := ∑_{i=1}^{k}(ξ_{i} − 1) be a random walk starting at S_{0} = 0 with increments ξ_{i} − 1. Then τ := min{k : S_{k} = −1} has the Borel distribution Bo(α) [11, 12]; see also [6, 21].

Remark 3.3. It is easily seen that this result has equivalent reformulations in the theories of queues and branching processes: Bo(α) is the distribution of the number of customers in a busy period in a queue with arrivals according to a Poisson process and constant service time; Bo(α) is also the total progeny of a Galton–Watson process where each individual has Po(α) children. For these results and generalizations, see e.g. [2, 18, 13, 27, 25, 26, 6, 21].

Furthermore, let us use this random walk to construct a hash table T̃ on {1, …, τ} by taking ξ_{i} items with hash address i, 1 ≤ i ≤ τ, inserting them in the table in random order. Then, for 1 ≤ k ≤ τ, the number of probes at cell k, i.e. H_{k}, is S_{k} + 1; thus the number of unsuccessful probes at k is S_{k} for k < τ, and τ is the first empty cell. It is easily seen that, conditioned on τ = l, the resulting table has a uniform distribution over all almost full confined hash tables of length l, i.e. it is T′_{l,l−1} Consequently, the random hash table T̃ equals (in distribution) T_{α}. This yields the following description of the profile.

Lemma 3.4. Let 0 < α < 1. The profile (H_{j})_{j=1}^{m(T_{α})} of T_{α} has the same distribution as (S_{j} + 1)_{j=1}^{τ}, where ξ ∈ Po(α), S_{k} and τ are as above. □

This may also be expressed using the following random infinite hashing. Consider a hash table with infinitely many cells 1, 2, 3, … and suppose that

items arrive to the cells according to independent Poisson processes with rate 1. When an item arrives, it is placed in the cell if the cell is empty, otherwise either the new or the old item (according to the chosen policy) is moved to the next cell, and so on. All movements are instantaneous. Denote the resulting table at time t ≥ 0 by T_{∞}(t). We define blocks in T_{∞}(t) as for finite tables, starting at cell 1; we also consider an infinite string of occupied cells as a block. There are either an infinite number of finite blocks, or a finite (possibly zero) number of finite blocks followed by a single infinite block.

Lemma 3.5. If 0 ≤ α ≤ 1, then the first block in T_{∞}(α) equals T_{α} in distribution.

Proof. Let ξ_{i} be the number of items arriving to cell i up to time α. Then ξ_{1}, ξ_{2}, … are i.i.d. Po(α) as above, and we define S_{k} and τ as before. Thus, for k ≤ τ, the number of items probing cell k up to time α is S_{k} + 1, and τ is the first empty cell at time α, i.e. the length of the first block in T_{∞}(α). Conditioned on τ and ξ_{1}, …, ξ_{τ}, the τ − 1 items that have arrived to {1, …, τ} have come in random order, and we are in the situation of T̃ discussed above. □

Remark 3.6. As a digression, let us study T_{∞}(α) further.

For α ≤ 1, the random walk S_{k} defined above has negative or zero drift and thus a.s. hits −1, i.e. τ < ∞ (as is implicit in the discussion above). After cell τ, the same process starts again, and thus T_{∞}(α) consists of an infinite string of independent random blocks, each a copy of T_{α}. In particular, the description above of the blocks in T_{m,n} is equivalent to the fact that if we condition T_{∞}(α) on the (m−n):th empty cell being cell m, then the m first cells form a random confined hash table T′_{m,n}, which easily is seen directly.

For α > 1, the random walk {S_{k}} has positive drift and thus has positive probability of never hitting −1. This means that T_{∞}(α) may have one or several finite blocks in the beginning, but, a.s., eventually there is an infinite block covering the rest of the table. As a consequence, the infinite hashing works for time α ≤ 1, but for α > 1 it fails because items are moved away to infinity (in zero time) and lost. In other words, there is a phase transition at time 1.

For α > 1, the probability of the first block being finite is α′/α, where α′ := T (αe^{−α}) < 1, and conditioned on being finite, the block has the distribution of T_{α′}. In particular, its length then has the Borel distribution Bo(α′) with mean 1/(1 − α′).

Hence, the number of finite blocks has the geometric distribution Ge(1 − α′/α) with mean α′/(α − α′). As a consequence, the expected number of cells in the finite blocks equals \frac{α′}{α−α′} \frac{1}{1−α′}.

Finally, we note that T_{∞}(α) is a discrete version of the queueing process studied by Borel [2].

Remark 3.7. We can similarly define two-way infinite hashing with the cells indexed by ℤ, all integers. This can be regarded as infinite unconfined hashing, while the one-way infinite hashing on ℤ_{+} is infinite confined hashing.

In this case, we have a similar structure as for the one-way infinite case. If the time α ≤ 1, the table consists a.s. of an infinite number of finite blocks. On the other hand, for α > 1, the whole table is filled a.s.

4. A general limit theorem

We begin with a general limit theorem for the distribution of the individual displacements (in the case n/m → α, 0 < α < 1).

Recall that we first take a random hash table T_{m,n} and then consider the distribution of a random displacement for that hash table, i.e. we consider the conditional distribution of a random displacement given the hash table. We are thus really studying a random probability distribution; the reader who finds this too mind-boggling can instead think of the proportions n_{k}^{Ξ}(T_{m,n})/n of items with given displacements in the table, which is the same thing by (2.2).

Theorem 4.1. Suppose that m, n → ∞ with n/m → α, where 0 < α < 1, and let Ξ ∈ {FC, LC, RH}.

(i) For every k = 0, 1, …,

ℙ(d^{Ξ}(T_{m,n}) = k | T_{m,n}) = \frac{1}{n}n_{k}^{Ξ}(T_{m,n}) →^{p} p_{α}^{Ξ}(k) := \frac{1 − α}{α} 𝔼 n_{k}^{Ξ}(T_{α}), (4.1)

and p_{α}^{Ξ} = {p_{α}^{Ξ}(k)}_{k=0}^{∞} is a probability distribution on ℕ. (ii) More precisely, for every k = 0, 1, … and jointly for all k,

\sqrt{n}(ℙ(d^{Ξ}(T_{m,n}) = k | T_{m,n}) − p_{n/m}^{Ξ}(k)) = n^{−1/2}(n_{k}^{Ξ}(T_{m,n}) − np_{n/m}^{Ξ}(k)) →^{d} Z_{k}^{Ξ},

(4.2)

where Z_{k}^{Ξ} are some Gaussian random variables with means 𝔼 Z_{k}^{Ξ} = 0 and a nondegenerate covariance matrix given by

Cov(Z_{k}^{Ξ}, Z_{l}^{Ξ}) = \frac{1 − α}{α}(Cov(n_{k}^{Ξ}(T_{α}), n_{l}^{Ξ}(T_{α}))

− (1 − α)^{3} Cov(n_{k}^{Ξ}(T_{α}), m(T_{α})) Cov(n_{l}^{Ξ}(T_{α}), m(T_{α}))); (4.3)

furthermore, all moments converge too. In particular, with N_{k} := n_{k}^{Ξ}(T_{m,n}),

𝔼 N_{k} = np_{n/m}^{Ξ}(k) + o(n^{1/2}) = np_{α}^{Ξ}(k) + o(n),

(N_{k} − 𝔼 N_{k})/(Var N_{k})^{1/2} →^{d} N(0, 1).

Remark 4.2. A more fancy formulation of part (i) of the theorem is that the distribution of d^{Ξ}(T_{m,n}) converges to p_{α}^{Ξ} in probability, in the space of all probability measures on ℕ, equipped with the weak topology (which coincides with the ℓ^{1} topology on this space); see [1] for definitions.

We will find (more or less explicit) formulas for the limit probabilities p_{α}^{Ξ} in Sections 7–9. It seems possible that the variances and covariances can be found by the same methods, but we have not attempted to find them.

The theorem says that a typical instance of the random hash table T_{m,n} has its displacements distributed approximately according to p_{α}^{Ξ}, with some normal fluctuations. In particular, different realizations of T_{m,n} have (with large probability) almost the same distribution. Taking the expectation over the possible choices of T_{m,n}, this yields the following, conceptually simpler, corollary on the distribution of the displacement of a random item in a random hash table.

Corollary 4.3. If n/m → α < 1 and Ξ ∈ {FC, LC, RH}, then

d^{Ξ}(T_{m,n}) →^{d} D_{α}^{Ξ},

where D_{α}^{Ξ} is a random variable with distribution

ℙ(D_{α}^{Ξ} = k) = p_{α}^{Ξ}(k).  □

Proof of Theorem 4.1. Let α_{n} := n/m and let T_{1}, T_{2}, … be independent copies of T_{α_{n}}. By Lemma 3.1, n_{k}^{Ξ}(T_{m,n}) has the same distribution as ∑_{i=1}^{m−n} n_{k}^{Ξ}(T_{i}) conditioned on ∑_{i=1}^{m−n} m(T_{i}) = m.

We define X_{i} := m(T_{i}) and Y_{i} := n_{k}^{Ξ}(T_{i}) and are thus led to study ∑_{i=1}^{m−n} Y_{i} conditioned on ∑_{i=1}^{m−n} X_{i} = m. We use, as in [10], the following conditional limit theorem proved in [9].

Lemma 4.4. Suppose that, for each ν, (X, Y) = (X(ν), Y (ν)) is a pair of random variables such that X is integer valued, and that N = N(ν) and m = m(ν) are integers. Suppose further that for some γ and c (independent of ν), with 0 < γ ≤ 2 and c > 0, the following hold, where σ_{X}^{2} := Var X, σ_{Y}^{2} := Var Y and all limits are taken as ν → ∞:

(i) 𝔼 X = m/N. (ii) 0 < σ_{X}^{2} < ∞. (iii) For every integer r ≥ 3, 𝔼 |X − 𝔼 X|^{r} = o(N^{r/2−1}σ_{X}^{r}). (iv) σ_{X}^{2} = O(N^{2/γ−1}).

(v) φ_{X}(s) := 𝔼 e^{isX} satisfies 1 − |φ_{X}(s)| ≥ c min(|s|^{γ}, s^{2}σ_{X}^{2}) for |s| ≤ π. (vi) 0 < σ_{Y}^{2} < ∞. (vii) For every integer r ≥ 3, 𝔼 |Y − 𝔼 Y |^{r} = o(N^{r/2−1}σ_{Y}^{r}). (viii) The correlation ρ := Cov(X, Y)/σ_{X}σ_{Y} satisfies lim sup |ρ| < 1.

Let, for each ν, (X_{i}, Y_{i}) be i.i.d. copies of (X, Y), and let S_{N} := ∑_{1}^{N} X_{i}, T_{N} := ∑_{1}^{N} Y_{i} and τ^{2} := σ_{Y}^{2} (1 − ρ^{2}) = σ_{Y}^{2} − Cov(X, Y)^{2}/σ_{X}^{2}. Then, as ν → ∞, the conditional distribution of (T_{N} −N 𝔼 Y)/N^{1/2}τ given S_{N} = m converges to a standard normal distribution. In other words, if U = U_{ν} is a random variable whose distribution equals the conditional distribution of T_{N} given S_{N} = m, then

\frac{U − N 𝔼 Y}{N^{1/2}τ} →^{d} N(0, 1).  (4.4)

Moreover, 𝔼 U = N 𝔼 Y + o(N^{1/2}τ) and Var U ∼ Nτ^{2}, and thus also

\frac{U − 𝔼 U}{(Var U)^{1/2}} →^{d} N(0, 1).  (4.5)

The limits (4.4) and (4.5) hold with convergence of all moments. □

To apply Lemma 4.4, we consider a sequence (m, n) = (m(ν), n(ν)) tending to infinity and let N := m − n. First, fix k ≥ 1 and let X := m(T_{n/m}) and Y := n_{k}^{Ξ}(T_{n/m}). By the remarks before the lemma, n_{k}^{Ξ}(T_{m,n}) has the same distribution as T_{N} conditioned on S_{N} = m, i.e. the same distribution as U in the lemma.

We have to verify all conditions of the lemma. First, X ∈ Bo(n/m) and thus, by (3.6), 𝔼 X = 1/(1 − α_{n}) = m/N, which verifies (i). Next, n/m → α ∈ (0, 1), and thus T_{n/m} →^{d} T_{α} and (X, Y) →^{d} (X̄, Ȳ) := (m(T_{α}), n_{k}^{Ξ}(T_{α})), with convergence of all moments. Further, N → ∞, the distribution of X̄ has span 1 (because ℙ(X̄ = 1) > 0) and Ȳ is not a.s. equal to a linear function of X̄ because both ℙ(X̄ = k+2, Ȳ = 0) > 0 and ℙ(X̄ = k+2, Ȳ = 1) > 0. It follows easily, see [9, Corollary 2.1] for a general statement, that all other conditions of the lemma hold for γ = 2, with τ^{2} = Var(Ȳ) − Cov(Ȳ , X̄)^{2}/ Var(X̄).

We may thus apply Lemma 4.4. We have

N 𝔼 Y = n\frac{1 − n/m}{n/m} 𝔼 n_{k}^{Ξ}(T_{n/m}) = np_{n/m}^{Ξ}(k),

and (4.2) follows for a single k, with Var(Z_{k}^{Ξ}) = lim(N/n)τ^{2} = ((1 − α)/α)τ^{2}. (Note that we divide by n^{1/2} in (4.2) but N^{1/2} in (4.4).) Furthermore, the same argument applies with the Y above replaced by a linear combination Y := ∑_{0}^{K} a_{k}n_{k}^{Ξ}(T_{n/m}), which by the Cramér–Wold device yields joint convergence and, using (3.7), (4.3), see [9, Corollary 2.2] for details.

Again, no such Y is equal to a linear function of X, and thus every nontrivial finite linear combination ∑_{0}^{K} a_{k}Z_{k}^{Ξ} has nonzero variance.

Part (ii) of Theorem 4.1 thus follows from Lemma 4.4. Part (i) follows from part (ii) and (2.1) and (3.6), which yields

∑_{k=0}^{∞} p_{α}^{Ξ}(k) = \frac{1 − α}{α} 𝔼 ∑_{k=0}^{∞} n_{k}^{Ξ}(T_{α}) = \frac{1 − α}{α} 𝔼 n(T_{α}) = \frac{1 − α}{α} 𝔼(m(T_{α}) − 1) = 1.

□

We have similar results, with minor differences, for the unsuccessful searches.

Theorem 4.5. Suppose that m, n → ∞ with n/m → α, where 0 < α < 1.

(i) For every k = 0, 1, …,

ℙ(d^{U}(T_{m,n}) = k | T_{m,n}) = \frac{1}{m}n_{k}^{U}(T_{m,n}) →^{p} p_{α}^{U}(k) := (1 − α) ℙ(B_{α} > k),

where B_{α} ∈ Bo(α), and p_{α}^{U} = {p_{α}^{U}(k)}_{k=0}^{∞} is a probability distribution on ℕ. (ii) More precisely, for every k = 0, 1, … and jointly for all k,

\sqrt{n}(ℙ(d^{U}(T_{m,n}) = k | T_{m,n}) − p_{n/m}^{U}(k)) = \frac{n^{1/2}}{m} (n_{k}^{U}(T_{m,n}) − mp_{n/m}^{U}(k)) →^{d} Z_{k}^{U},

where Z_{k}^{U} are some Gaussian random variables with means 𝔼 Z_{k}^{U} = 0 and a covariance matrix given by

Cov(Z_{k}^{U}, Z_{l}^{U}) = α(1 − α)(Cov(1[B_{α} ≤ k], 1[B_{α} ≤ l])

− (1 − α)^{3} Cov(1[B_{α} ≤ k], B_{α}) Cov(1[B_{α} ≤ l], B_{α}));

furthermore, all moments converge too. In particular, with N_{k} := n_{k}^{U}(T_{m,n}),

𝔼 N_{k} = mp_{n/m}^{U}(k) + o(m^{1/2}) = mp_{α}^{U}(k) + o(m),

(N_{k} − 𝔼 N_{k})/(Var N_{k})^{1/2} →^{d} N(0, 1).

The case k = 0 is trivial, n_{0}^{U}(T_{m,n}) = m − n = mp_{n/m}^{U}(0) and thus Z_{0}^{U} = 0, but the variables Z_{k}^{U}, k ≥ 1, are linearly independent.

Proof. We argue as in the proof of Theorem 4.1, now taking Y := n_{k}^{U}(T_{n/m}), or a linear combination ∑_{0}^{K} a_{k}n_{k}^{U}(T_{n/m}) of such variables. By (2.4), recalling that T_{α} has a single block, n_{k}^{U}(T_{n/m}) = 1[m(T_{n/m}) > k] and thus

N 𝔼 n_{k}^{U}(T_{n/m}) = m(1 − n/m) ℙ(m(T_{n/m}) > k) = mp_{n/m}^{U}(k),

and the result follows from Lemma 4.4 as above, if we recall that m(T_{α}) ∈ Bo(α) so m(T_{α}) =^{d} B_{α}, and use 1[B_{α} > k] = 1 − 1[B_{α} ≤ k]. □

Corollary 4.6. If n/m → α < 1, then

d^{U}(T_{m,n}) →^{d} D_{α}^{U},

where D_{α}^{U} is a random variable with distribution

ℙ(D_{α}^{U} = k) = p_{α}^{U}(k).  □

In the proofs above we used finite linear combinations ∑_{0}^{K} a_{k}n_{k}^{Ξ}(T ), but we can just as well take infinite sums ∑_{0}^{∞} f(k)n_{k}^{Ξ}(T ), provided the function f grows subexponentially, i.e. f(k) = exp(o(k)), which implies that ∑_{0}^{∞} f(k)n_{k}^{Ξ}(T_{α}) has finite moments of all orders. In fact, this was done in [10] to study the total displacement d^{∗}(T_{m,n}), which is obtained by the choice f(k) = k.

We obtain the following result, leaving the formulas for the asymptotic variances to the reader.

Theorem 4.7. Let f be a function of subexponential growth on ℕ, for example a polynomial. Suppose that m, n → ∞ with n/m → α, where 0 < α < 1. For every Ξ ∈ {FC, LC, RH},

\begin{aligned}\frac{1}{n} & ∑_{i=1}^{n} f(d_{i}^{Ξ}(T_{m,n})) = \frac{1}{n} ∑_{k=0}^{∞} f(k)n_{k}^{Ξ}(T_{m,n}) \\ & →^{p} ∑_{k=0}^{∞} f(k)p_{α}^{Ξ}(k) = \frac{1 − α}{α} 𝔼 ∑_{k=0}^{∞} f(k)n_{k}^{Ξ}(T_{α}) = \frac{1 − α}{α} 𝔼 ∑_{i=1}^{n(T_{α})} f(d_{i}^{Ξ}(T_{α})). \end{aligned}

and, similarly, with B_{α} ∈ Bo(α),

\begin{aligned}\frac{1}{m} ∑_{j=1}^{m} f(d_{j}^{U}(T_{m,n})) & = \frac{1}{m} ∑_{k=0}^{∞} f(k)n_{k}^{U}(T_{m,n}) \\ & →^{p} ∑_{k=0}^{∞} f(k)p_{α}^{U}(k) = (1 − α) 𝔼 ∑_{k=0}^{B_{α}−1} f(k). \end{aligned}

The convergences hold in L^{p} too, for any p < ∞; in particular, the expectations of the left hand sides converge to the right hand sides. Moreover, the random variables on the left hand side are asymptotically normal, with variances O(n^{−1}). □

Corollary 4.8. Suppose that m, n → ∞ with n/m → α, where 0 < α < 1, and let Ξ ∈ {FC, LC, RH, U}. Then

𝔼(d^{Ξ}(T_{m,n}) | T_{m,n}) →^{p} 𝔼 D_{α}^{Ξ},  (4.6)
Var(d^{Ξ}(T_{m,n}) | T_{m,n}) →^{p} Var D_{α}^{Ξ}.  (4.7)

The expectations of the left hand sides converge to the same limits.

Proof. Apply Theorem 4.7 with f(k) = k and f(k) = k^{2}. □

Note that if Ξ ∈ {FC, LC, RH}, then 𝔼(d^{Ξ}(T_{m,n}) | T_{m,n}) = d̄(T_{m,n}), the average displacement. We thus have the orthogonal decomposition d^{Ξ}(T_{m,n}) = (d^{Ξ}(T_{m,n}) − d̄(T_{m,n})) + d̄(T_{m,n}) and the decomposition of the variance

Var(d^{Ξ}(T_{m,n})) = Var(d^{Ξ}(T_{m,n}) − d̄(T_{m,n})) + Var(d̄(T_{m,n}))
= 𝔼(Var(d^{Ξ}(T_{m,n}) | T_{m,n})) + Var(d̄(T_{m,n}))
→ Var(D_{α}^{Ξ}).

The second term, i.e. the part of the variance that comes from the variation between different hash tables is of order O(n^{−1}) only by Theorem 4.7, and thus much smaller than the first term which is the part of the variance coming from the variation between different items in the table. This, again, shows that the variation between tables is insignificant in the sparse range.

A similar result holds for d^{U}. Furthermore, we obtain similar results for higher moments by taking f(k) = k^{r}, r > 0. In particular, we can sharpen Corollaries 4.3 and 4.6.

Corollary 4.9. If n/m → α < 1 and Ξ ∈ {FC, LC, RH, U}, then d^{Ξ}(T_{m,n}) →^{d} D_{α}^{Ξ} with all moments, i.e.

𝔼(d^{Ξ}(T_{m,n}))^{r} → 𝔼(D_{α}^{Ξ})^{r},  r ≥ 0.  □

We have so far treated all three insertion policies together. In Sections 6– 9, we will study them one by one (beginning with unsucessful searches) and identify the limit distributions p_{α}^{Ξ}, i.e. the distributions of the limit random variables D_{α}^{Ξ}.

5. Exact distributions

Although we are mainly interested in asymptotic result, we make in this section a digression and consider exact formulas for the distributions of d^{Ξ}(T_{m,n}) and, in particular, their moments. For simplicity, we consider only Ξ ∈ {FC, LC, RH} in this section, and leave the case of unsuccessful searches to the next section. Using results by Poblete, Viola and Munro [23, 28], we will see that the moments of D_{α}^{Ξ} not only are the limits of the moments of d^{Ξ}(T_{m,n}) as m, n → ∞ with n/m → α, they can also be regarded as Poisson transforms of the moments of d^{Ξ}(T_{m,n}). The same is true for the probabilities ℙ(d^{Ξ}(T_{m,n}) = k) and for the probability generating function. This provides an interesting relation between the values of these moments (probabilities) and their limits. Moreover, it is possible to invert the Poisson transform and thus derive exact formulas from the limits. This yields interesting connections with earlier results by various authors.

We denote the probability generating function of D_{α}^{Ξ} by ψ_{α}^{Ξ} and have by (4.1), for 0 < α < 1, at least for |z| ≤ 1,

ψ_{α}^{Ξ}(z) := 𝔼 z^{D_{α}^{Ξ}} = ∑_{k=0}^{∞} z^{k}p_{α}^{Ξ}(k) = \frac{1 − α}{α} ∑_{k=0}^{∞} z^{k} 𝔼 n_{k}^{Ξ}(T_{α}).  (5.1)

Recall that the probabilities p_{α}^{Ξ}(k) can be obtained by differentiating ψ_{α}^{Ξ}(z) at z = 0, and that the (factorial) moments are obtained by differentiation at z = 1.

Remark 5.1. Since no displacement is larger than the size of the table, we have the bound 𝔼 n_{k}^{Ξ}(T_{α}) ≤ 𝔼(m(T_{α})1[m(T_{α}) ≥ k]), which together with (3.4) easily implies that the sums in (5.1) converge at least for |z| < (αe^{1−α})^{−1}. Hence, for each α < 1, ψ_{α}^{Ξ}(z) is analytic in a disc with radius greater than 1, and (5.1) is valid there. The same applies to various formulas for generating functions below; they are always valid for |z| ≤ 1, and actually in some larger open domain (possibly depending on parameters such as α and Ξ), but we will usually ignore mentioning this restriction on z.

Furthermore, for 1 ≤ n ≤ m, let

φ_{m,n}^{Ξ}(z) := 𝔼 z^{d^{Ξ}(T_{m,n})},  (5.2)

the probability generating function of d^{Ξ}(T_{m,n}). When n < m, d^{Ξ}(T′_{m,n}) has the same distribution as d^{Ξ}(T_{m,n}), see Section 2, and thus the same probability generating function φ_{m,n}^{Ξ}(z).

Let, for ℓ ≥ 1, Φ_{ℓ}^{Ξ}(z) be the sum of z^{d_{i}^{Ξ}(T )} over all ℓ^{ℓ−2} confined almost full hash tables of length ℓ, and all i ∈ {1, …, l − 1}. Thus Φ_{1}^{Ξ}(z) = 0, and for ℓ ≥ 2, Φ_{ℓ}^{Ξ}(z) = (ℓ − 1)ℓ^{ℓ−2}φ_{ℓ,ℓ−1}^{Ξ}(z). Further,

Φ_{ℓ}^{Ξ}(z) = ℓ^{ℓ−2} 𝔼 ∑_{i=1}^{ℓ−1} z^{d_{i}^{Ξ}(T′_{ℓ,ℓ−1})} = ℓ^{ℓ−2} 𝔼 ∑_{k=0}^{∞} n_{k}^{Ξ}(T′_{ℓ,ℓ−1})z^{k}.  (5.3)

Hence, by (5.1), the definition of T_{α} and (3.4),

ψ_{α}^{Ξ}(z) = \frac{1 − α}{α} ∑_{k=0}^{∞} z^{k} 𝔼 n_{k}^{Ξ}(T_{α}) = \frac{1 − α}{α} ∑_{ℓ=1}^{∞} ℙ(B_{α} = ℓ)ℓ^{−(ℓ−2)}Φ_{ℓ}^{Ξ}(z)

= (1 − α) ∑_{ℓ=2}^{∞} \frac{α^{ℓ−2}e^{−ℓα}}{(ℓ − 1)!} Φ_{ℓ}^{Ξ}(z)  (5.4a)

= (1 − α) ∑_{ℓ=2}^{∞} \frac{(ℓα)^{ℓ−2}e^{−ℓα}}{(ℓ − 2)!} φ_{ℓ,ℓ−1}^{Ξ}(z)

= (1 − α) ∑_{i=0}^{∞} \frac{((i + 2)α)^{i}e^{−(i+2)α}}{i!} φ_{i+2,i+1}^{Ξ}(z).  (5.4b)

In terms of the transforms defined in Poblete, Viola and Munro [23], (5.4b) shows that ψ_{α}^{Ξ}(z) is the diagonal Poisson transform D_{2}[φ_{n+2,n+1}^{Ξ}; α].

Before proceeding, we note that (5.4b) also shows that ψ_{α}^{Ξ}(z) is an analytic function of α too (in a suitable domain).

Fix z and let f_{m,n−1} := φ_{m,n}^{Ξ}(z), 0 ≤ n < m. (Thus f_{m,n} refers to a hash table of size m with n + 1 items; we follow here the notation in [23].) This is the expectation of a random variable that depends on a randomly chosen item and the block it belongs to. Poblete, Viola and Munro [23, §4.1] show that for such quantities f_{m,n}, it is easy to express f_{m,n} (n < m − 1) in terms of the values for almost full tables f_{i+2,i}, see [23, (28)].

Using this formula [23, (28)] as a definition of f_{m,n} for n ≥ m − 1 too, it is further shown in [23, (29)] that the diagonal Poisson transform D_{2}[f_{n+2,n}; x] equals the Poisson transform P_{m}[f_{m,n}; x], which is defined as 𝔼 f_{m,N} where N ∈ Po(mx). (In particular, the latter transform is independent of m.) This leads to the following result.

Theorem 5.2. For every m ≥ 1 and Ξ ∈ {FC, LC, RH}, φ_{m,n}^{Ξ} can be defined for n > m too such that for 0 ≤ α < 1

ψ_{α}^{Ξ}(z) = P_{m}[φ_{m,n+1}^{Ξ}(z); α] = e^{−mα} ∑_{n=0}^{∞} \frac{(mα)^{n}}{n!} φ_{m,n+1}^{Ξ}(z)  (5.5)

and

φ_{m,n}^{Ξ}(z) = \frac{(n − 1)!}{m^{n−1}}[α^{n−1}](e^{mα}ψ_{α}^{Ξ}(z)) = ∑_{k=0}^{n−1} \frac{(n − 1)\underline{k}}{m^{k}} [α^{k}]ψ_{α}^{Ξ}(z).  (5.6)

Note that the functions φ_{m,n}^{Ξ} that appear here only have a formal meaning when n > m. At least, we do not know any probabilistic interpretation of them in this case, and they are not always probability generating functions. (For example, it follows easily from Theorem 5.2 and Theorem 8.1 below that φ_{1,3}^{RH}(z) = \frac{1}{3}z^{2} + \frac{4}{3}z − \frac{2}{3}.) It would be interesting to find such an interpretation, and a probabilistic proof of Theorem 5.2.

Proof. We have already shown (5.5), with φ_{m,n}^{Ξ}(z) = f_{m,n−1} given by [23, (28)] for n ≥ m.

To invert the Poisson transform, we multiply (5.5) by e^{mα} and extract the coefficient of α^{n}, which yields

\begin{aligned}φ_{m,n+1}^{Ξ}(z) & = \frac{n!}{m^{n}} [α^{n}](e^{mα}ψ_{α}^{Ξ}(z)) = \frac{n!}{m^{n}} ∑_{k=0}^{n} \frac{m^{n−k}}{(n − k)!} [α^{k}]ψ_{α}^{Ξ}(z) \\ & = ∑_{k=0}^{n} \frac{n\underline{k}}{m^{k}} [α^{k}]ψ_{α}^{Ξ}(z). \end{aligned}

One subtle problem remains: The argument in [23] leading to [23, (28)] uses confined hash tables, and is thus restricted to f_{m,n} for n + 1 < m. Hence, the φ_{m,n}^{Ξ}(z) that appears in (5.5) and (5.6) is indeed given by (5.2) for n < m, but it remains to show that this is true for n = m too. In order to see this, fix z and n, and note that the right hand side of (5.6) is a polynomial in 1/m. We claim that the same is true for φ_{m,n}^{Ξ} for all m ≥ n; since the equality is verified for m > n, it then holds for m = n too, and the theorem is completely proved.

To verify the claim, define a graph on the set {1, …, n} where i and j are joined by an edge if items i and j conflict over the same cell sometime during the construction of the hash table (using the policy Ξ), and call the components of this graph strict blocks. It is easily seen that any partition of {1, …, n} into strict blocks together with some given internal structure in the strict blocks has a probability that is a polynomial in 1/m for m ≥ n, and the result follows. □

We can take derivatives at z = 1 in Theorem 5.2 to obtain the corresponding result for fractional moments, and then take suitable linear combinations to obtain the moments. Similarly, taking derivatives at z = 0 we obtain results for the point probabilities. Alternatively, we can argue as above using moments or probabilities for f_{m,n}. We thus obtain the following result.

Corollary 5.3. Let m ≥ 1 and Ξ ∈ {FC, LC, RH}. Then, for every r ≥ 0,

𝔼(D_{α}^{Ξ})^{r} = P_{m}[𝔼(d^{Ξ}(T_{m,n+1}))^{r}; α] = e^{−mα} ∑_{n=0}^{∞} \frac{(mα)^{n}}{n!} 𝔼(d^{Ξ}(T_{m,n+1}))^{r}

and, for k ≥ 0,

ℙ(D_{α}^{Ξ} = k) = P_{m}[ℙ(d^{Ξ}(T_{m,n+1}) = k); α] = e^{−mα} ∑_{n=0}^{∞} \frac{(mα)^{n}}{n!} ℙ(d^{Ξ}(T_{m,n+1}) = k)

where 𝔼(d^{Ξ}(T_{m,n+1}))^{r} and ℙ(d^{Ξ}(T_{m,n+1}) = k) only have a formal meaning for n + 1 > m. Conversely, for 1 ≤ n ≤ m,

𝔼(d^{Ξ}(T_{m,n}))^{r} = \frac{(n − 1)!}{m^{n−1}}[α^{n−1}](e^{mα} 𝔼(D_{α}^{Ξ})^{r}) = ∑_{i=0}^{n−1} \frac{(n − 1)\underline{i}}{m^{i}} [α^{i}] 𝔼(D_{α}^{Ξ})^{r},

ℙ(d^{Ξ}(T_{m,n}) = k) = \frac{(n − 1)!}{m^{n−1}}[α^{n−1}](e^{mα} ℙ(D_{α}^{Ξ} = k))
= ∑_{i=0}^{n−1} \frac{(n − 1)\underline{i}}{m^{i}} [α^{i}] ℙ(D_{α}^{Ξ} = k).  □

An important example is provided by the transform (1 − α)^{−r−1}, which has the inverse Poisson transform

\frac{n!}{m^{n}} [α^{n}](e^{mα}(1 − α)^{−r−1}) = \frac{n!}{m^{n}} ∑_{k=0}^{n} \frac{m^{n−k}}{(n − k)!}\binom{r + k}{k} = Q_{r}(m, n),

the Q function defined in [15, Theorem 6.4.K]. Here r may be any real number. Note, in particular, that Q_{−1}(m, n) = 1 and Q_{−2}(m, n) = 1 − n/m.

Consequently, we have an explicit formula, covering several cases below. (We use the simple, well-known, identity [16, (5.8)] for Q_{r}(m, n − 1).)

Corollary 5.4. Let r ≥ 1 and Ξ ∈ {FC, LC, RH}, and suppose that

𝔼(D_{α}^{Ξ})^{r} = ∑_{j∈J} c_{j}(1 − α)^{−j}, 0 < α < 1,

for some finite set J ⊂ ℤ and numbers c_{j}. Then, for 1 ≤ n ≤ m,

𝔼(d^{Ξ}(T_{m,n}))^{r} = ∑_{j∈J} c_{j}Q_{j−1}(m, n − 1)
= \frac{m}{n} ∑_{j∈J} c_{j}(Q_{j−1}(m, n) − Q_{j−2}(m, n)).  □

Of course, the converse of this corollary is immediate.

6. The limit distribution for unsuccessful searches

By Theorem 4.5 and (3.4),

p_{α}^{U}(k) = (1 − α) ℙ(B_{α} > k) = (1 − α)(1 − ∑_{l=1}^{k} \frac{l^{l−1}}{l!} α^{l−1}e^{−lα}).  (6.1)

In particular, p_{α}^{U}(0) = 1 − α, p_{α}^{U}(1) = (1 − α)(1 − e^{−α}) and p_{α}^{U}(2) = (1 − α)(1 − e^{−α} − αe^{−2α}).

We have the following further results.

Theorem 6.1. The probability generating function of D_{α}^{U} is

ψ_{α}^{U}(z) := 𝔼 z^{D_{α}^{U}} = ∑_{k=0}^{∞} z^{k}p_{α}^{U}(k) = \frac{1 − α}{α} · \frac{T (αe^{−α}) − T (αe^{−α}z)}{1 − z}.

The first moments are given by

𝔼 D_{α}^{U} = \frac{2α − α^{2}}{2(1 − α)^{2}} = \frac{1}{2}(1 − α)^{−2} − \frac{1}{2},
𝔼(D_{α}^{U})^{2} = \frac{6α + 3α^{2} − 4α^{3} + α^{4}}{6(1 − α)^{4}} = (1 − α)^{−4} − \frac{2}{3}(1 − α)^{−3} − \frac{1}{2}(1 − α)^{−2} + \frac{1}{6},
Var(D_{α}^{U}) = \frac{12α − 6α^{2} + 4α^{3} − α^{4}}{12(1 − α)^{4}} = \frac{3}{4}(1 − α)^{−4} − \frac{2}{3}(1 − α)^{−3} − \frac{1}{12}.

Proof. By Theorem 4.5 and (3.4), or Theorem 4.7 with f(k) = z^{k} (for |z| ≤ 1), together with (3.5),

\begin{aligned}ψ_{α}^{U}(z) & = ∑_{k=0}^{∞} z^{k}p_{α}^{U}(k) = ∑_{k=0}^{∞} z^{k}(1 − α) ℙ(B_{α} > k) = (1 − α) 𝔼 ∑_{k=0}^{B_{α}−1} z^{k} \\ & = (1 − α) 𝔼 \frac{1 − z^{B_{α}}}{1 − z} = (1 − α)\frac{1 − T (αe^{−α}z)/α}{1 − z}. \end{aligned}

The moments are computed by calculating the derivatives of ψ_{α}^{U}(z) at z = 1. (A computer algebra program is helpful.) □

To obtain exact formulas for moments of d^{U}(T_{m,n}), we cannot directly apply the results of Section 5, since d^{U} is defined by taking a random new hash address rather than a random item. We circumvent this by defining d^{u}(T ) to be d^{U}(T ) conditioned on being nonzero; this equals the remaining length of the current block at a random item, and the arguments above apply. The limit random variable is D_{α}^{u}, defined as D_{α}^{U} conditioned on being nonzero. We have, using Theorem 6.1 and ℙ(D_{α}^{U} > 0) = 1 − p_{α}^{U}(0) = α,

𝔼 D_{α}^{u} = α^{−1} 𝔼 D_{α}^{U} = \frac{2 − α}{2(1 − α)^{2}} = \frac{1}{2}(1 − α)^{−2} + \frac{1}{2}(1 − α)^{−1}  (6.2)

and Corollary 5.4 yields, since ℙ(d^{U}(T_{m,n}) > 0) = n/m,

𝔼 d^{U}(T_{m,n}) = \frac{n}{m} 𝔼 d^{u}(T_{m,n})
= \frac{1}{2}(Q_{1}(m, n) − Q_{0}(m, n)) + \frac{1}{2}(Q_{0}(m, n) − Q_{−1}(m, n))
= \frac{1}{2}Q_{1}(m, n) − \frac{1}{2},

in accordance with [14], [15, Theorem 6.4.K] (where d^{U} + 1 is studied). Similarly,

\begin{aligned}𝔼(D_{α}^{u})^{2} & = α^{−1} 𝔼(D_{α}^{U})^{2} = \frac{6 + 3α − 4α^{2} + α^{3}}{6(1 − α)^{4}} \\ & = (1 − α)^{−4} + \frac{1}{3}(1 − α)^{−3} − \frac{1}{6}(1 − α)^{−2} − \frac{1}{6}(1 − α)^{−1} \end{aligned}  (6.3)

and Corollary 5.4 yields

\begin{aligned}𝔼(d^{U}(T_{m,n}))^{2} & = \frac{n}{m} 𝔼(d^{u}(T_{m,n}))^{2} \\ & = Q_{3}(m, n) − \frac{2}{3}Q_{2}(m, n) − \frac{1}{2}Q_{1}(m, n) + \frac{1}{6}, \end{aligned}

in accordance with the formula for 𝔼(d^{U}(T_{m,n}) + 1)^{2} in [15, Answer 6.4-28].

We finally observe from Theorem 6.1 that the radius of convergence r^{U}(α) of ψ_{α}^{U}(z) equals (αe^{1−α})^{−1}, which is the radius of convergence for 𝔼 z^{B_{α}} too.

7. The limit distribution for FC

Theorem 7.1. The distribution of D_{α}^{FC}, 0 < α < 1, is given by

p_{α}^{FC}(k) = ℙ(D_{α}^{FC} = k) = \frac{1}{α} ∫_{0}^{α} p_{x}^{U}(k) dx = 1 − \frac{α}{2} − ∑_{l=1}^{k} \frac{l^{l−2}}{l!} α^{l−1}e^{−lα}. (7.1)

The probability generating function is

ψ_{α}^{FC}(z) := 𝔼 z^{D_{α}^{FC}} = ∑_{k=0}^{∞} z^{k}p_{α}^{FC}(k) = \frac{(1 − T (zαe^{−α}))^{2} − (1 − α)^{2}}{2α(1 − z)} . (7.2)

The first moments are

𝔼 D_{α}^{FC} = \frac{α}{2(1 − α)} = \frac{1}{2}(1 − α)^{−1} − \frac{1}{2},  (7.3)
𝔼(D_{α}^{FC})^{2} = \frac{3α − α^{3}}{6(1 − α)^{3}} = \frac{1}{3}(1 − α)^{−3} − \frac{1}{2}(1 − α)^{−1} + \frac{1}{6},  (7.4)
Var(D_{α}^{FC}) = \frac{6α − 3α^{2} + α^{3}}{12(1 − α)^{3}} = \frac{1}{3}(1 − α)^{−3} − \frac{1}{4}(1 − α)^{−2} − \frac{1}{12}.  (7.5)

Proof. In a random hash table T_{m,n} using the FC rule, the insertion of i:th item can be regarded as an unsuccessful search in the table T_{m,i−1} constructed so far; hence

d_{i}^{FC}(T_{m,n}) =^{d} d^{U}(T_{m,i−1}),  1 ≤ i ≤ n,  (7.6)

and

𝔼 n_{k}^{FC}(T_{m,n}) = ∑_{i=1}^{n} ℙ(d_{i}^{FC}(T_{m,n}) = k) = ∑_{i=1}^{n} ℙ(d^{U}(T_{m,i−1}) = k).

Consequently, using Corollary 4.6 and dominated convergence,

\begin{aligned}\frac{1}{n} 𝔼 n_{k}^{FC}(T_{m,n}) & = \frac{1}{n} ∑_{i=0}^{n−1} ℙ(d^{U}(T_{m,i}) = k) = \frac{m}{n} ∫_{0}^{n/m} ℙ(d^{U}(T_{m,⌊mx⌋}) = k) dx \\ & → \frac{1}{α} ∫_{0}^{α} ℙ(D_{x}^{U} = k) dx = \frac{1}{α} ∫_{0}^{α} p_{x}^{U}(k) dx, \end{aligned}

which by Theorem 4.1 yields p_{α}^{FC}(k) = \frac{1}{α} ∫_{0}^{α} p_{x}^{U}(k) dx, which is the first part of (7.1). The final equality in (7.1) is verified, using (6.1), by multiplying the last expression by α and differentiating.

As a consequence of (7.1) and (3.2),

ψ_{α}^{FC}(z) = ∑_{k=0}^{∞} z^{k}p_{α}^{FC}(k) = ∑_{k=0}^{∞} z^{k}(1 − \frac{α}{2}) − ∑_{1≤l≤k<∞} z^{k} \frac{l^{l−2}}{l!} α^{l−1}e^{−lα}

= \frac{1 − α/2}{1 − z} − \frac{1}{1 − z} ∑_{l=1}^{∞} z^{l} \frac{l^{l−2}}{l!} α^{l−1}e^{−lα}

= \frac{1 − α/2}{1 − z} − \frac{T (zαe^{−α}) − \frac{1}{2}T (zαe^{−α})^{2}}{(1 − z)α} ,

which can be rewritten as (7.2). The moments are obtained by differentiation. □

For example, p_{α}^{FC}(0) = 1 − \frac{1}{2}α, p_{α}^{FC}(1) = 1 − \frac{1}{2}α − e^{−α}, p_{α}^{FC}(2) = 1 − \frac{1}{2}α − e^{−α} − \frac{1}{2}αe^{−2α}.

From (7.3) and Corollary 5.4 we obtain the well-known formula [14], [15, Theorem 6.4.K]

𝔼 d^{FC}(T_{m,n}) = \frac{1}{2}Q_{0}(m, n − 1) − \frac{1}{2}.

Similarly, (7.4) and Corollary 5.4 yields

𝔼(d^{FC}(T_{m,n}))^{2} = \frac{m}{n} \frac{2Q_{2}(m, n) − 2Q_{1}(m, n) − 3Q_{0}(m, n) + 3}{6} + \frac{1}{6},

in accordance with [15, Answer 6.4-67].

It can be seen from the form of ψ_{α}^{FC} in (7.2) and (3.3) that every integer moment 𝔼(D_{α}^{FC})^{r} is a polynomial in 1/(1 − α), and thus Corollary 5.4 shows that every moment of d^{FC}(T_{m,n}) can be expressed in Q functions. We leave it to the reader as an exercise to find explicit formulas for, say, the third and fourth moments.

Similarly, we can obtain an exact formula for the distribution of d^{FC}(T_{m,n}).

Theorem 7.2.

ℙ(d^{FC}(T_{m,n}) = k) = 1 − \frac{n − 1}{2m} − ∑_{l=1}^{k} \frac{l^{l−2}(n − 1)\underline{l−1}(m − l)^{n−l}}{l! m^{n−1}} .

Proof. By Corollary 5.3 and (7.1), the probability equals

\frac{(n − 1)!}{m^{n−1}}[α^{n−1}](e^{mα} − \frac{α}{2}e^{mα} − ∑_{l=1}^{k} \frac{l^{l−2}}{l!} α^{l−1}e^{(m−l)α})

and the result follows. □

We finally observe from Theorem 7.1 that the radius of convergence r^{FC}(α) of ψ_{α}^{FC}(z) equals r^{U}(α) = (αe^{1−α})^{−1}. Hence, p_{α}^{FC}(k) decrease geometrically roughly as r^{FC}(α)^{−k} as k → ∞. More precisely, we have the following asymptotics.

Theorem 7.3. Let 0 < α < 1 be fixed. Then, as k → ∞,

p_{α}^{FC}(k) ∼ \frac{1}{\sqrt{2π}(e^{α−1} − α)}k^{−5/2}(αe^{1−α})^{k}.

Proof. A simple consequence of (7.1) and Stirling’s formula. We omit the details. □

8. The limit distribution for RH

For Robin Hood hashing, we have the following explicit formula for the generating function of the limit distribution in the sparse case.

Theorem 8.1. The probability generating function of D_{α}^{RH}, 0 < α < 1, is

ψ_{α}^{RH}(z) := 𝔼 z^{D_{α}^{RH}} = ∑_{k=0}^{∞} z^{k}p_{α}^{RH}(k) = \frac{1 − α}{α} · \frac{e^{α(1−z)} − 1}{1 − ze^{α(1−z)}} = \frac{1 − α}{α} · \frac{e^{αz} − e^{α}}{ze^{α} − e^{αz}} .

The first moments are

𝔼 D_{α}^{RH} = \frac{α}{2(1 − α)} = \frac{1}{2}(1 − α)^{−1} − \frac{1}{2},  (8.1)
𝔼(D_{α}^{RH})^{2} = \frac{3α − α^{2} + α^{3}}{6(1 − α)^{2}} = \frac{1}{2}(1 − α)^{−2} − \frac{2}{3}(1 − α)^{−1} + \frac{1}{6} + \frac{1}{6}α,  (8.2)
Var(D_{α}^{RH}) = \frac{6α − 5α^{2} + 2α^{3}}{12(1 − α)^{2}} = \frac{1}{4}(1 − α)^{−2} − \frac{1}{6}(1 − α)^{−1} − \frac{1}{12} + \frac{1}{6}α. (8.3)

Remark 8.2. The probabilities p_{α}^{RH} can be obtained from the generating function ψ_{α}^{RH}. For example,

p_{α}^{RH}(0) = (1 − α)\frac{e^{α} − 1}{α},  (8.4)
p_{α}^{RH}(1) = (1 − α)e^{α} \frac{e^{α} − 1 − α}{α}.  (8.5)

Moreover, as pointed out by the referee, there is a connection with Eulerian numbers [15, Section 5.1.3], [8, Section 6.2]. Indeed, from the formula above for ψ_{α}^{RH}(z) and [8, (7.60)] or [15, 5.1.3-(20)] follows easily

p_{α}^{RH}(k) = ∑_{l=1}^{∞}(1 − α)α^{l−1}\left⟨{l \atop k}\right⟩/l!.

This shows the curious fact that D_{α}^{RH} has the same distribution as the number of descents in a random permutation of random length L, where L has the geometric distribution ℙ(L = l) = (1 − α)α^{l−1}, l ≥ 1.

Proof. Let F (z) be the generating function ∑_{k=0}^{∞} 𝔼 n_{k}^{RH}(T_{α})z^{k}; thus ψ_{α}^{RH}(z) = ((1 − α)/α)F (z) by Theorem 4.1. By Lemmas 2.1 and 3.4,

F (z) = 𝔼 ∑_{i=1}^{τ−1} z^{d_{i}^{RH}} = 𝔼 ∑_{j=1}^{τ−1} z^{H_{j}−1} = 𝔼 ∑_{j=1}^{τ−1} z^{S_{j}},

where S_{j} and τ are as in Section 3.

Recall that the random walk S_{j} starts with S_{0} = 0 and ends with S_{τ} = −1. We also consider the shifted random walk S_{j} + r, starting with r ≥ 0, which we run until it hits 0, i.e. until τ_{r} := min{j ≥ 0 : S_{j} = −r}. We define

G_{r}(z) := 𝔼 ∑_{j=1}^{τ_{r}} z^{S_{j}+r},

and note that G_{0}(z) = 0 and G_{1}(z) = zF (z) + 1.

If r ≥ 1, then τ = τ_{1} is the time the shifted random walk first hits r − 1, and S_{τ} + r, S_{τ+1} + r, …, S_{τ_{r}} + r is a random walk starting at r − 1 and stopped when it hits 0, i.e. a copy of S_{0} + (r − 1), …, S_{τ_{r−1}} + (r − 1). Hence,

G_{r}(z) = 𝔼 ∑_{j=1}^{τ} z^{S_{j}+r} + 𝔼 ∑_{j=τ+1}^{τ_{r}} z^{S_{j}+r} = z^{r−1}G_{1}(z) + G_{r−1}(z),

and thus

G_{r}(z) = (z^{r−1} + ⋯ + 1)G_{1}(z) = \frac{1 − z^{r}}{1 − z} G_{1}(z), r ≥ 0.

Moreover, taking r = 1, we start at S_{0} + 1 = 1 and the next element is S_{1} + 1 = ξ_{1} ∈ Po(α), so the remainder of the random walk is a random walk started at ξ_{1}. Conditioning on ξ_{1}, we thus find

G_{1}(z) = ∑_{r=0}^{∞} ℙ(ξ_{1} = r)(z^{r} + G_{r}(z)) = ∑_{r=0}^{∞} ℙ(ξ_{1} = r)(z^{r} + \frac{1 − z^{r}}{1 − z} G_{1}(z))

= ∑_{r=0}^{∞} ℙ(ξ_{1} = r)z^{r}(1 − \frac{1}{1 − z} G_{1}(z)) + \frac{1}{1 − z} G_{1}(z)

= e^{αz−α}(1 − \frac{1}{1 − z} G_{1}(z)) + \frac{1}{1 − z} G_{1}(z)

with the solution

G_{1}(z) = \frac{1 − z}{1 − ze^{α(1−z)}} .

Hence,

F (z) = \frac{G_{1}(z) − 1}{z} = \frac{e^{α(1−z)} − 1}{1 − ze^{α(1−z)}} .

The formula for ψ_{α}^{RH} follows, and the moments are obtained by differentiations at z = 1. □

Note that 𝔼 D_{α}^{RH} = 𝔼 D_{α}^{FC}, as we already know since the average displacement is the same for any insertion policy. Similarly, 𝔼 d^{RH}(T_{m,n}) = 𝔼 d^{FC}(T_{m,n}) = \frac{1}{2}Q_{0}(m, n−1)− \frac{1}{2}. For the second moment, (8.2) can be written

𝔼(D_{α}^{RH})^{2} = \frac{1}{2}(1 − α)^{−2} − \frac{2}{3}(1 − α)^{−1} + \frac{1}{3} − \frac{1}{6}(1 − α),

and Corollary 5.4 yields, using Q_{−2}(m, n) = 1 − n/m,

\begin{aligned}𝔼(d^{RH}(T_{m,n}))^{2} & = \frac{1}{2}Q_{1}(m, n − 1) − \frac{2}{3}Q_{0}(m, n − 1) + \frac{1}{6} + \frac{n − 1}{6m} \\ & = \frac{m}{n} \frac{3Q_{1}(m, n) − 7Q_{0}(m, n) + 4}{6} + \frac{1}{6} + \frac{n − 1}{6m}, \end{aligned}

which easily is shown to be equivalent to the formula in [15, Answer 6.4-67].

It is easily seen that each integer moment of D_{α}^{RH} is a rational function in α, with denominator a power of 1−α. Hence each integer moment 𝔼(d^{RH}(T_{m,n}))^{r} can be expressed in Q functions (allowing negative indices; these terms form a polynomial in n/m and 1/m).

We can also find exact formulas for point probabilities. For example, by Corollary 5.3 and (8.4),

\begin{aligned}ℙ(d^{RH}(T_{m,n}) = 0) & = \frac{(n − 1)!}{m^{n−1}}[α^{n−1}](e^{mα} \frac{1 − α}{α}(e^{α} − 1)) \\ & = \frac{1}{n}((m + 1 − n)(1 + \frac{1}{m})^{n−1} − (m − n)). \end{aligned}

By the formula in Theorem 8.1, ψ_{α}^{RH}(z) is a meromorphic funcion of z in the entire complex plane. The poles are the roots of z = e^{α(z−1)}, except z = 1. Since the Taylor coefficients p_{α}^{RH} are non-negative, the pole closest to the origin lies on the positive real axis; moreover, it is easily seen that all other poles have strictly larger absolute values. The following theorem follows easily.

Theorem 8.3. Let 0 < α < 1. The radius of convergence r^{RH}(α) of ψ_{α}^{RH}(z) is the unique root r > 1 of r = e^{α(r−1)}. If α^{∗} > 1 satisfies α^{∗}e^{−α^{∗}} = αe^{−α}, then r^{RH}(α) = α^{∗}/α. Moreover, as k → ∞,

p_{α}^{RH}(k) ∼ \frac{(1 − α)(α^{∗} − α)}{αα^{∗}(α^{∗} − 1)}r^{RH}(α)^{−k}.

Note that r^{RH}(α) > 1/α > r^{FC}(α); another expression of the fact that large deviations are less likely for RH than for FC.

9. The limit distribution for LC

The Last Come policy seems to be the most difficult to analyse, and we are not able to give as explicit results as for the other policies. The simplest form of the probability generating function that we have been able to find is the following. It is quite possible that others may simplify the result, but the expression for the variance shows that this case is intrinsically more complicated than the two other policies considered here.

Theorem 9.1. Define

u(α, β, z) := \frac{1}{z + (1 − z)e^{α−β}} = \frac{e^{β}}{(1 − z)(e^{α} − e^{β}) + e^{β}} ,
v(α, β, z) := u(α, β, z)βe^{−β} = \frac{β}{ze^{β} + (1 − z)e^{α}} ,
w(α, β, z) := ∫_{β}^{α} \frac{u(α, γ, z)}{1 − T (v(α, γ, z))}dγ.

Then, for 0 < α < 1,

ψ_{α}^{LC}(z) = \frac{1 − α}{α} ∫_{0}^{α} e^{zw(α,β,z)} \frac{u(α, β, z)}{T (v(α, β, z))} \frac{β − T (v(α, β, z))}{1 − u(α, β, z)} dβ

= \frac{1 − α}{α} ∫_{0}^{α} e^{zw(α,β,z)} \frac{v(α, β, z)}{T (v(α, β, z))} ∫_{0}^{1} T′((1 − t + tu(α, β, z))βe^{−β}) dt dβ. (9.1)

The first moments are

𝔼 D_{α}^{LC} = \frac{α}{2(1 − α)} = \frac{1}{2(1 − α)} − \frac{1}{2},  (9.2)
𝔼(D_{α}^{LC})^{2} = \frac{1}{2(1 − α)^{2}} − \frac{1}{6(1 − α)} − \frac{e^{α} − 1}{3α} − \frac{e^{α−1}}{6α} (Ei(1) − Ei(1 − α)) + \frac{1}{6}, (9.3)

Var(D_{α}^{LC}) = \frac{1}{4(1 − α)^{2}} + \frac{1}{3(1 − α)} − \frac{e^{α} − 1}{3α} − \frac{e^{α−1}}{6α} (Ei(1) − Ei(1 − α)) − \frac{1}{12}. (9.4)

Here Ei is the exponential integral function, Ei(1) − Ei(1 − α) = ∫_{1−α}^{1} \frac{e^{x}}{x} dx.

Proof. We build heavily on the analysis of the first two moments by Poblete, Viola and Munro [23, 24, 28], who proved (9.3) and (9.4) (in a different form).

We use (5.3) and (5.4a). To keep track of the displacements and obtain formulas for Φ_{ℓ}^{LC}(z), we keep track also of the positions of the items in their blocks (in the final table). Thus, let l_{i}(T ) be the number of items with final position before item i in the same block in the hash table T with the LC rule, and consider the bivariate generating function Φ_{ℓ}(z, y) equal to the sum of z^{d_{i}^{LC}(T )}y^{l_{i}(T )} over all ℓ^{ℓ−2} confined almost full hash tables of length ℓ, and all i ∈ {1, …, ℓ−1}. Hence, in the notation of (5.3) and (5.4a), Φ_{ℓ}^{LC}(z) = Φ_{ℓ}(z, 1).

In the notation of [23],

Φ_{k}(z, y) = ∑_{l+r+2=k} z^{−1}F_{l,r}(z)y^{l}  (9.5)

(the factor z^{−1} is because [23] studies the number of probes, i.e. 1 + the displacement); moreover, their C_{i}(z) := ∑_{l+r=i} F_{l,r}(z) = zΦ_{i+2}(z, 1) = zΦ_{i+2}^{LC}(z).

Further, define the trivariate generating function (note that Φ_{1}(z, y) = 0)

\begin{aligned}Ψ(z, y, λ) & := ∑_{i=0}^{∞} \frac{λ^{i}}{i!} Φ_{i+1}(z, y) = ∑_{i=0}^{∞} \frac{λ^{i+1}}{(i + 1)!}Φ_{i+2}(z, y) \\ & = ∑_{l,r≥0} z^{−1}F_{l,r}(z)y^{l} \frac{λ^{l+r+1}}{(l + r + 1)!}. \end{aligned}  (9.6)

The sums converge at least for |z| ≤ 1, |y| ≤ 1, |λ| < e^{−1}, and Ψ is continuous in that domain and analytic in its interior. By (5.4a) and (9.6), we have

ψ_{α}^{LC}(z) = \frac{1 − α}{α}e^{−α} ∑_{ℓ=1}^{∞} \frac{(αe^{−α})^{ℓ−1}}{(ℓ − 1)!} Φ_{ℓ}(z, 1) = \frac{1 − α}{α}e^{−α}Ψ(z, 1, αe^{−α}). (9.7)

Poblete, Viola and Munro [23, (70)] give the recursion formula, for all l, r ≥ 0 with the convention that F_{l,r} = 0 if l < 0 or r < 0,

F_{l,r}(z) = z ∑_{0≤k≤r} \binom{l + r}{k}(k + 1)^{k−1}(l + r − k + 1)^{l+r−k−1}

+ ∑_{0≤k≤l+r} \binom{l + r}{k}(k + 1)^{k−1}(F_{l−k−1,r}(z)(k + 1) + lzF_{l−1,r−k}(z)

+ (r − k)F_{l,r−k−1}(z)).

Hence, using (9.6), with 1/i! = 0 if i < 0,

\begin{aligned}z \frac{∂Ψ(z, y, λ)}{∂λ} & = ∑_{l,r≥0} \frac{λ^{l+r}}{(l + r)!}y^{l}F_{l,r}(z) \\ & = z ∑_{\begin{matrix}r≥k≥0 \\ l≥0 \end{matrix}} \frac{λ^{l+r}y^{l}}{(l + r − k)! k!}(k + 1)^{k−1}(l + r − k + 1)^{l+r−k−1} \\ & + ∑_{k,l,r} \frac{λ^{l+r}y^{l}}{(l + r − k)! k!}(k + 1)^{k}F_{l−k−1,r}(z) \\ & + z ∑_{k,l,r} \frac{λ^{l+r}y^{l}}{(l + r − k)! k!}(k + 1)^{k−1}lF_{l−1,r−k}(z) \\ & + ∑_{k,l,r} \frac{λ^{l+r}y^{l}}{(l + r − k)! k!}(k + 1)^{k−1}(r − k)F_{l,r−k−1}(z) \\ & = zS_{I} + S_{II} + zS_{III} + S_{IV} . \end{aligned} (9.8)

To evaluate the sums S_{I}, S_{II}, S_{III}, S_{IV}, we first rewrite (3.1) as

T (z) = ∑_{j=0}^{∞} \frac{(j + 1)^{j}z^{j+1}}{(j + 1)!} = ∑_{j=0}^{∞} \frac{(j + 1)^{j−1}z^{j+1}}{j!}  (9.9)

and further differentiate to obtain, using (3.3),

∑_{j=0}^{∞} \frac{(j + 1)^{j}z^{j+1}}{j!} = zT′(z) = \frac{T (z)}{1 − T (z)}.  (9.10)

We now change summation indices, using j = l + r − k, and obtain by (9.9)

S_{I} = ∑_{\begin{matrix}j,k,l \\ j≥l≥0 \end{matrix}} \frac{λ^{j+k}y^{l}}{j! k!} (k + 1)^{k−1}(j + 1)^{j−1}

= ∑_{j,k≥0} \frac{λ^{k}}{k!} (k + 1)^{k−1} \frac{λ^{j}}{j!} (j + 1)^{j−1} \frac{1 − y^{j+1}}{1 − y}

= \frac{1}{1 − y} ∑_{k} \frac{λ^{k}}{k!} (k + 1)^{k−1} ∑_{j} \frac{λ^{j+1} − (yλ)^{j+1}}{λj!} (j + 1)^{j−1}

= \frac{1}{1 − y} \frac{T (λ)}{λ} \frac{T (λ) − T (yλ)}{λ}.

Similarly, using also m = l − k − 1 and (9.10), (9.6),

S_{II} = ∑_{j,k,m} \frac{λ^{j+k}y^{m+k+1}}{j! k!} (k + 1)^{k}F_{m,j−m−1}(z)

= λ^{−1} ∑_{k} \frac{(λy)^{k+1}}{k!} (k + 1)^{k} ∑_{j,m} \frac{λ^{j}}{j!} y^{m}F_{m,j−m−1}(z)

= λ^{−1} \frac{T (yλ)}{1 − T (yλ)}zΨ(z, y, λ),

S_{III} = ∑_{j,k,l} \frac{λ^{j+k}y^{l}}{j! k!} (k + 1)^{k−1}lF_{l−1,j−l}(z)

= \frac{T (λ)}{λ}y ∑_{j,l} \frac{λ^{j}}{j!} ly^{l−1}F_{l−1,j−l}(z)

= \frac{T (λ)}{λ}y \frac{∂}{∂y} (zyΨ(z, y, λ)),

S_{IV} = ∑_{j,k,l} \frac{λ^{j+k}y^{l}}{j! k!} (k + 1)^{k−1}(j − l)F_{l,j−l−1}(z)

= \frac{T (λ)}{λ}(λ\frac{∂}{∂λ} − y \frac{∂}{∂y} ) ∑_{j,l} \frac{λ^{j}}{j!} y^{l}F_{l,j−l−1}(z)

= \frac{T (λ)}{λ}(λ\frac{∂}{∂λ} − y \frac{∂}{∂y} )(zΨ(z, y, λ)).

Summing up, (9.8) yields

\frac{∂Ψ(z, y, λ)}{∂λ} = \frac{1}{λ^{2}(1 − y)}T (λ)(T (λ) − T (yλ)) + \frac{1}{λ} \frac{T (yλ)}{1 − T (yλ)}Ψ(z, y, λ)

+ \frac{1}{λ}T (λ)yzΨ(z, y, λ) + \frac{1}{λ}T (λ)zy^{2} \frac{∂Ψ(z, y, λ)}{∂y}

+ T (λ)\frac{∂Ψ(z, y, λ)}{∂λ} − \frac{y}{λ}T (λ)\frac{∂Ψ(z, y, λ)}{∂y},

which after multiplication by λ can be rearranged to

λ(1 − T (λ))\frac{∂Ψ(z, y, λ)}{∂λ} + T (λ)y(1 − yz)\frac{∂Ψ(z, y, λ)}{∂y}

= (T (λ)yz + \frac{T (yλ)}{1 − T (yλ)})Ψ(z, y, λ) + T (λ)\frac{T (λ) − T (yλ)}{λ(1 − y)} (9.11)

We simplify a little by the change of variable λ = αe^{−α}. We then have α = T (λ) and ∂/∂α = (1 − α)e^{−α}∂/∂λ. We write Ψ̃(z, y, α) = Ψ(z, y, αe^{−α}), noting for later use that this conveniently also appears in (9.7), which can be written

ψ_{α}^{LC}(z) = \frac{1 − α}{α}e^{−α}Ψ̃(z, 1, α).  (9.12)

Returning to (9.11), we obtain after substitution, and division by α,

\frac{∂Ψ̃(z, y, α)}{∂α} + y(1 − yz)\frac{∂Ψ̃(z, y, α)}{∂y}

= (yz + \frac{T (yαe^{−α})}{α(1 − T (yαe^{−α}))})Ψ̃(z, y, α) + \frac{α − T (yαe^{−α})}{αe^{−α}(1 − y)}, (9.13)

valid at least for |z| ≤ 1, |y| ≤ 1 and 0 ≤ α < 1. Note that this partial differential equation contains no ∂/∂z; hence we may regard z as a constant. We solve the differential equation in the standard way: The characteristics of (9.13) are given by

\frac{dy}{dα} = y(1 − yz)  (9.14)

or

\frac{dα}{dy} = \frac{1}{y(1 − yz)} = \frac{1}{y} + \frac{z}{1 − yz}

with the solutions

α − α_{1} = ln y − ln(1 − yz) + ln(1 − z),

where α_{1} is a constant (the value of α when y = 1), or, equivalently,

y = \frac{1}{z + (1 − z)e^{α_{1}−α}} = u(α_{1}, α, z).  (9.15)

Assume that 0 ≤ z ≤ 1 and 0 ≤ α_{1} < 1 and define y(α) by (9.15). Then (9.13) gives, renaming α to β,

\frac{dΨ̃(z, y(β), β)}{dβ} = g(β)Ψ̃(z, y(β), β) + h(β)  (9.16)

with, where y = y(β) = u(α_{1}, β, z),

g(β) = yz + \frac{T (yβe^{−β})}{β(1 − T (yβe^{−β}))} = yz + \frac{T (v(α_{1}, β, z))}{β(1 − T (v(α_{1}, β, z)))}

and

h(β) = \frac{β − T (yβe^{−β})}{βe^{−β}(1 − y)} = ∫_{0}^{1} T′((1 − t + ty)βe^{−β}) dt.

The solution to (9.16) is, because Ψ̃(z, y, 0) = Ψ(z, y, 0) = 0 by (9.6),

Ψ̃(z, y(α), α) = ∫_{0}^{α} e^{G(α)−G(β)}h(β) dβ  (9.17)

where G′ = g. Since, by (9.14),

\frac{d}{dβ} (y(β)βe^{−β}) = y(1 − yz)βe^{−β} + ye^{−β} − yβe^{−β} = y(1 − yzβ)e^{−β}

we have, using (3.3), with T = T (yβe^{−β}) = T (v(α_{1}, β, z)),

\begin{aligned}\frac{d}{dβ} T (y(β)βe^{−β}) & = \frac{T}{1 − T} \frac{y(1 − yzβ)e^{−β}}{yβe^{−β}} \\ & = \frac{T}{1 − T} (\frac{1}{β} − yz) = g(β) − yz(1 + \frac{T}{1 − T} ). \end{aligned}

Hence, we can choose

G(β) = T (v(α_{1}, β, z)) − zw(α_{1}, β, z)

and (9.17) yields, with α = α_{1} and dropping the subscript,

Ψ̃(z, 1, α) = ∫_{0}^{α} e^{T (v(α,α,z))−T (v(α,β,z))+zw(α,β,z)}h(β) dβ.

Finally, we use (9.12) and the facts that T (v(α, α, z)) = T (αe^{−α}) = α and e^{−T (v)} = v/T (v). The formula (9.1) follows.

In principle, the moments can be computed by repeated differentiation of (9.1) with respect to z (under the integral signs) and then letting z = 1, noting that u(α, β, 1) = 1, v(α, β, 1) = βe^{−β} and w(α, β, 1) = ln(1 − β) − ln(1 − α). However, the expressions become very complicated. Indeed, even to verify the trivial ψ_{α}^{LC}(1) = 1 from (9.1) takes a little effort. We have verified the first moment (9.2) this way, using computer algebra (Maple), but failed to obtain the formulas (9.3), (9.4) for the second moment. (No doubt, a more skillful person would succeed.)

A much shorter proof is to simply refer to the asymptotic formulas in Poblete, Viola and Munro [23], in particular [23, Theorem 28], together with Corollary 4.9.

We will, however, give a third proof, which is closely related to the proof in [23] but formulated using the functions and equations used above; we hope that this may illuminate the arguments used in [23] and their connection to the present paper.

As a warm-up, we begin with the mean (9.2), although we already know the result because 𝔼 D_{α}^{LC} = 𝔼 D_{α}^{FC} = 𝔼 D_{α}^{RH}. We let D_{α}, D_{z}, D_{y} denote the partial differential operators. Applying D_{z} to (9.13) and then setting z = y = 1 we find

D_{z} D_{α} Ψ̃(1, 1, α)−D_{y} Ψ̃(1, 1, α) = Ψ̃(1, 1, α)+(1+\frac{1}{1 − α}) D_{z} Ψ̃(1, 1, α). (9.18)

For convenience, we define

F (z, y, α) := (1 − α)e^{−α}Ψ̃(z, y, α)

and write f(α) := F (1, 1, α), f_{z}(α) := D_{z} F (1, 1, α), f_{y}(α) := D_{y} F (1, 1, α), f_{zz}(α) := D_{z}^{2} F (1, 1, α), and so on. Then (9.18) yields, after simple calculations, the ordinary differential equation in the three functions f(α), f_{z}(α), f_{y}(α)

D_{α} f_{z}(α) − f_{y}(α) = f(α).  (9.19)

(It may be more natural to consider α^{−1}F, cf. (9.12), which for fixed α is a bivariate probability generating function, but the extra factor α simplifies the differential equations.)

Note that, by (9.12), ψ_{α}^{LC}(z) = α^{−1}F (z, 1, α), and thus

f(α) = αψ_{α}^{LC}(1) = α,
f_{z}(α) = α D_{z} ψ_{α}^{LC}(1) = α 𝔼 D_{α}^{LC},  (9.20)
f_{zz}(α) = α D_{z}^{2} ψ_{α}^{LC}(1) = α 𝔼 D_{α}^{LC}(D_{α}^{LC} − 1),  (9.21)

and so on.

To solve (9.19), we first have to find f_{y}(α). One possibility is to use the definition of Φ_{ℓ} or (9.5) so see

Φ_{ℓ}(1, y) = ℓ^{ℓ−2} ∑_{i=1}^{ℓ−1} y^{i−1} = ℓ^{ℓ−2} \frac{1 − y^{ℓ−1}}{1 − y}

and thus, by (9.6) and (3.1)

Ψ(1, y, λ) = ∑_{i=1}^{∞} \frac{λ^{i−1}}{(i − 1)!}i^{i−2} \frac{1 − y^{i−1}}{1 − y} = \frac{1}{1 − y} (\frac{T (λ)}{λ} − \frac{T (λy)}{λy})

which leads to

F (1, y, α) = \frac{1 − α}{1 − y}(1 − \frac{T (αe^{−α}y)}{αy}).

A calculation using (3.3) yields

f_{y}(α) = D_{y} F (1, 1, α) = \frac{3α^{2} − 2α^{3}}{2(1 − α)^{2}} .

Alternatively, we may observe that if we as in Section 6 use the superscript u for unsuccessful searches conditioned on starting at an existing item, (5.3) yields

Φ_{k}^{u}(y) = yΦ_{k}(1, y).

Beneath our formalism, this simply reflects the fact that the number of items in a block to the right of a distinguished item has the same distribution as the number of items to the left; the factor y is because the distinguished element is included in the count defining d^{u} but not for Φ_{k}(z, y).

By (5.4a) and (9.6), we thus have

ψ_{α}^{u}(y) = \frac{1 − α}{α}e^{−α} ∑_{ℓ=1}^{∞} \frac{(αe^{−α})^{ℓ−1}}{(ℓ − 1)!} Φ_{ℓ}^{u}(y) = y \frac{1 − α}{α}e^{−α}Ψ̃(1, y, α)

and so

yF (1, y, α) = αψ_{α}^{u}(y).  (9.22)

Applying D_{y} we find at y = 1, using (6.2),

f(α) + f_{y}(α) = α D_{y} ψ_{α}^{u}(y) = α 𝔼 D_{α}^{u} = α\frac{2 − α}{2(1 − α)^{2}} .  (9.23)

We can now integrate (9.19), noting F (z, y, 0) = 0 and thus f_{z}(0) = 0:

f_{z}(α) = ∫_{0}^{α}(f(β) + f_{y}(β)) dβ = \frac{α^{2}}{2(1 − α)},  (9.24)

which by (9.20) yields (9.2).

For the second moment we argue similarly. We apply D_{z} D_{z} to (9.13) and obtain for z = y = 1

D_{z} D_{z} D_{α} Ψ̃ − 2 D_{z} D_{y} Ψ̃ = 2 D_{z} Ψ̃ + (1 + \frac{1}{1 − α}) D_{z} D_{z} Ψ̃

which implies

D_{α} f_{zz}(α) − 2f_{zy}(α) = 2f_{z}(α).  (9.25)

In order to solve this, we first need f_{zy}(α), which we find in the same way. We apply D_{y} D_{z} to (9.13) and obtain for z = y = 1

D_{y} D_{z} D_{α} Ψ̃ − D_{z} D_{y} Ψ̃ − D_{y}^{2} Ψ̃ − 2 D_{y} Ψ̃ =

(1 + \frac{1}{1 − α}) D_{y} D_{z} Ψ̃ + (1 + \frac{1}{(1 − α)^{3}} ) D_{z} Ψ̃ + D_{y} Ψ̃ + Ψ̃

and hence

D_{α} f_{zy}(α) = f_{zy}(α) + f_{yy}(α) + 3f_{y}(α) + (1 + \frac{1}{(1 − α)^{3}} )f_{z}(α) + f(α). (9.26)

To solve this, we first need f_{yy}(α). We find from (9.22) and (6.2), (6.3)

f_{yy}(α) = α 𝔼(D_{α}^{u}−1)(D_{α}^{u}−2) = α 𝔼(D_{α}^{u})^{2}−3α 𝔼 D_{α}^{u}+2α = \frac{16α^{3} − 19α^{4} + 6α^{5}}{3(1 − α)^{4}} .

(9.27)

(Alternatively, it is possible to continue in the same manner as above by applying D_{y}^{2} to (9.13) at z = y = 1; this yields a differential equation for f_{yy}(α) that can be solved. The same applies to f_{y}(α) above, which also can be found by applying D_{y} to (9.13).)

We can now put everything together. Noting that (9.27) and (9.23) imply f_{yy}(α) + 3f_{y}(α) + f(α) = α 𝔼(D_{α}^{u})^{2}, we find the solution to (9.26), using (6.3) and (9.24),

f_{zy}(α) = e^{α} ∫_{0}^{α} e^{−t}(t 𝔼(D_{t}^{u})^{2} + (1 + \frac{1}{(1 − t)^{3}} )f_{z}(t))dt

= \frac{1}{2(1 − α)^{3}} − \frac{7}{12(1 − α)^{2}} − \frac{7}{12(1 − α)} + \frac{5}{6} + \frac{α}{2} − \frac{e^{α}}{6}

− \frac{1}{12}e^{α−1}(Ei(1) − Ei(1 − α)).

Next, (9.25) is solved by, using (9.26),

\begin{aligned}f_{zz}(α) & = 2f_{zy}(α) + 2 ∫_{0}^{α}(f_{z}(t) − t 𝔼(D_{t}^{u})^{2} − (1 + \frac{1}{(1 − t)^{3}} )f_{z}(t))dt \\ & = \frac{1}{2(1 − α)^{2}} − \frac{7}{6(1 − α)} + 1 + \frac{2}{3}α − \frac{e^{α}}{3} − \frac{1}{6}e^{α−1}(Ei(1) − Ei(1 − α)). \end{aligned}

Finally, (9.3) and (9.4) follow from (9.21) and (9.2). □

Remark 9.2. The reader who wants to make a detailed comparison with [23] should note that, by (9.6) and the definitions in [23], their

c̀_{2}(x, z) = \frac{(1 − x)e^{−x}}{x} zΨ̃(z, 1, x) = \frac{1}{x}zF (z, 1, x),
g̀_{2}(x, z) = \frac{(1 − x)e^{−x}}{x} z(D_{y} +1)Ψ̃(z, 1, x) = \frac{1}{x}z(D_{y} +1)F (z, 1, x),
h̀_{2}(x) = D_{z} g̀_{2}(x, 1) = \frac{1}{x}(D_{z} +1)(D_{y} +1)F (1, 1, x)

= \frac{1}{x}(f_{zy}(x) + f_{z}(x) + f_{y}(x) + f(x)).

In principle, expressions for the probabilities ℙ(D_{α}^{LC} = k) can be obtained from (9.1) by differentiating at z = 0 (or making Taylor expansions). However, even for the simplest case k = 0, we obtain a rather complicated formula. We leave it to the reader to find a simpler formula, and to treat k ≥ 1.

Theorem 9.3. For 0 < α < 1,

p_{α}^{LC}(0) = ℙ(D_{α}^{LC} = 0) = ψ_{α}^{LC}(0) = \frac{1 − α}{α} ∫_{0}^{α} \frac{(e^{α−t} − 1)e^{α−t}(1 − t)}{e^{α−te^{α−t}} − 1}dt. (9.28)

Proof. Taking z = 0 in Theorem 9.1 we have u(α, β, 0) = e^{β−α} and v(α, β, 0) = βe^{−α}. Hence (9.1) yields

ψ_{α}^{LC}(0) = \frac{1 − α}{α} ∫_{0}^{α} \frac{e^{β−α}}{T (βe^{−α})} \frac{β − T (βe^{−α})}{1 − e^{β−α}}dβ.

The change of variables t = T (βe^{−α}) yields β = te^{α−t} and dβ/dt = (1 − t)e^{α−t}, and (9.28) follows by simple calculations. □

Various substitutions are possible, but none seems to give a simpler integral.

10. Some numerical values

Numerical values of p_{α}^{FC}(k) and p_{α}^{RH}(k) for given α and k are easily computed from the formulas in Theorems 7.1 and 8.1, see Remark 8.2. As examples we give some values (computed by Maple) in Table 1. The last line gives the sum for all k > 10.

Note that the fact that FC gives higher probabilities than RH for zero displacement hardly is an advantage, as might be believed. Since the average displacements are the same, this is compensated by higher probability for large displacements, which is worse.

k p_{0.5}^{FC}(k) p_{0.5}^{RH}(k) p_{0.9}^{FC}(k) p_{0.9}^{RH}(k)
0 0.750 0.649  0.550 0.162
1 0.143 0.245  0.143 0.153
2 0.051 0.076  0.069 0.128
3 0.024 0.022  0.042 0.104
4 0.012 0.0062 0.029 0.085
5 0.0070 0.0017 0.021 0.069
6 0.0042 0.00050 0.016 0.056
7 0.0026 0.00014 0.013 0.046
8 0.0017 0.000041 0.011 0.037
9 0.0011 0.000011 0.009 0.031
10 0.0007 0.000003 0.008 0.024
≥ 11 0.0018 0.000001 0.090 0.106

Table 1. Some numerical values

In principle, p_{α}^{LC}(k) can be calculated similarly from (9.1), but we have only done so for k = 0. We find, for example, by Theorem 9.3 and numerical integration, p_{0.5}^{LC}(0) ≐ 0.686 and p_{0.9}^{LC}(0) ≐ 0.212.

11. Monotonicity properties of the limit distributions

For FC, it follows immediately from (7.1) that the probabilities p_{α}^{FC}(k) decrease, p_{α}^{FC}(0) > p_{α}^{FC}(1) > . . .. Moreover, we have monotonicity for finite m and n too; it follows from (7.6) that for each m and n, the probabilities ℙ(d_{i}^{FC}(T_{m,n}) = k) are non-increasing in k.

This has the practical consequence that searching in a hash table constructed by the FC rule is best done in the standard way, probing at h, h + 1, h + 2, and so on, where h is the hash address of the searched item.

It has been suggested that for RH and LC hashing, where the variances of the individual displacements are smaller, the displacements might be concentrated about their mean 𝔼 d so that it would be more efficient to start probing at locations close to h + 𝔼 d. This seems to be the case for random probing and double hashing, see [3, 22]. However, we will see that this hardly is the case for linear probing. It would be the case (for a large table) for an insertion policy Ξ if p_{α}^{Ξ}(k) is larger when k is close to 𝔼 d than when k is close to 0, so we study these probabilities.

First, for Robin Hood hashing we have the following precise result; we postpone the proof.

Theorem 11.1. Let α_{1} ≐ 0.931 be the unique positive root of

e^{2α} − (2 + α)e^{α} + 1 = 0

If α ∈ [0, α_{1}], then p_{α}^{RH}(0) ≥ p_{α}^{RH}(1) > p_{α}^{RH}(2) > . . ..

Conversely, if α ∈ (α_{1}, 1), then p_{α}^{RH}(0) < p_{α}^{RH}(1).

Hence, it is only for α close to 1 that a different probing sequence might be better. However, even for α > α_{1}, small displacements seems to be more likely than displacements close to 𝔼 d. One reason is that it follows easily from Theorem 8.1 that as α → 1, (1 − α)D_{α}^{RH} →^{d} Exp(1/2). Hence, for α close to 1, the distribution of D_{α}^{RH} is approximatively exponential. Although this does not imply corresponding asymptotics of individual probabilities, it implies that the average of the values of p_{α}^{RH}(k) for k in a suitable interval close to 𝔼 d is about e^{−1} times the average of the values for k in an interval close to 0. This suggests that the standard probing sequence is close to optimal when α is close to 1, when the differences between different methods ought to be greatest.

Nevertheless, it is interesting to ask for the mode of the distribution of D_{α}^{RH}, i.e. the value of k that maximizes p_{α}^{RH}(k). Theorem 11.1 shows that the mode is 0 for α < α_{1}, but not for larger α.

Numerical calculations with Maple suggest the following; we have, however, no rigorous proof.

Conjecture 11.2. The mode of D_{α}^{RH} is

\begin{cases}0, & 0 < α < α_{1} ≐ 0.9308 \\ 1, & α_{1} < α < α_{2} ≐ 0.9888 \\ 2, & α_{2} < α < α_{3} ≐ 0.9989 \\ 3, & α_{3} < α < α_{4} ≐ 0.999995 \\ 4, & α_{4} < α < 1. \end{cases}

Of course, these results have merely theoretical interest; hashing with linear probing with n/m > .93 should probably be avoided. (In particular, this applies to the last case; if α > α_{4}, then the expectation of the displacement is over 100000.) Moreover, the differences are rather minor in this range; according to numerical calculations, no probability is ever more than 16.4% higher than p_{α}^{RH}(0), and the absolute differences p_{α}^{RH}(k) − p_{α}^{RH}(0) are less than 0.004. Hence, even when another probing sequence is better, the difference in performance seems to be small, and probably out-weighted by the additional steps required in the program.

It is somewhat surprising that the conjectured sequence of modes stops at 4. However, we have a another asymptotic result explaining this.

Theorem 11.3. As α → 1, (1 − α)^{−1}p_{α}^{RH}(k) → L_{k+1} for every k ≥ 0, where L_{k} have the generating function

∑_{k=1}^{∞} L_{k}z^{k} = z \frac{1 − e^{z−1}}{e^{z−1} − z} .

Proof. Theorem 8.1 implies that as α → 1, at least for |z| ≤ 1,

(1 − α)^{−1}ψ_{α}^{RH}(z) → \frac{e^{1−z} − 1}{1 − ze^{1−z}} = \frac{1 − e^{z−1}}{e^{z−1} − z} = ∑_{k=0}^{∞} L_{k+1}z^{k},

and the result follows. □

This generating function equals the one in Knuth [15, 5.1.3-(25)], and thus the limits L_{k} coincide with the numbers L_{k} defined there as the average lengths of the successive increasing runs in a random sequence. As shown in Knuth [15, Section 5.1.3], these numbers L_{k} converge rapidly to 2 as k → ∞, but the convergence is not monotone; the smallest is L_{1} = e − 1 ≐ 1.718 and the largest is L_{5} ≐ 2.00006. This and Theorem 11.3 strongly suggest (although do not strictly prove) that for α close to 1, the largest value of p_{α}^{RH}(k) is for k + 1 = 5, i.e. k = 4, as asserted in Conjecture 11.2.

Proof of Theorem 11.1. By (4.1), we can study 𝔼 n_{k}^{RH}(T_{α}) instead of p_{α}^{RH}(k).

Let k ≥ 0. By Lemmas 2.1 and 3.4, 𝔼 n_{k}^{RH}(T_{α}) and 𝔼 n_{k+1}^{RH}(T_{α}) are the expected number of visits of the random walk S_{i} to k and k + 1, respectively. We compare these numbers by studying the excursions of {S_{i}} above k − 1. Since the only negative step is −1, every such excursion ends at k. At each visit to k, the probability of exiting is e^{−α}, and if the random walk does not exit, it will sooner or later (perhaps immediately) return to k. Consequently, the number of visits to k in an excursion has a geometric distribution with expectation 1/e^{−α} = e^{α}.

Furthermore, at each visit to k, the probability of going to k + 1 or higher is ℙ(Po(α) ≥ 2) = 1 − e^{−α} − αe^{−α}; each such step leads, by the argument above, to an average of e^{α} visits to k + 1 before the first return to k. In an excursion beginning at k, there are thus on the average

e^{α}(1 − e^{−α} − αe^{−α})e^{α} = e^{α}(e^{α} − 1 − α)

visits to k + 1.

In an excursion beginning at l ≥ k+1, there are on the average an additional e^{α} visits to k + 1 before the first visit to k, and thus in total e^{α}(e^{α} − α) visits to k + 1.

The average number of excursions above k − 1 starting at l ≥ k is

ℙ(ξ_{0} = l + 1) + ∑_{j=0}^{k−1} 𝔼 n_{j}^{RH}(T_{α}) ℙ(ξ_{1} = l − j + 1).  (11.1)

For k = 0, we thus find, in agreement with (4.1) and (8.4), (8.5),

𝔼 n_{0}^{RH}(T_{α}) = ℙ(ξ_{0} ≥ 1)e^{α} = e^{α} − 1,  (11.2)
𝔼 n_{1}^{RH}(T_{α}) = ℙ(ξ_{0} = 1)e^{α}(e^{α} − 1 − α) + ℙ(ξ_{0} ≥ 2)e^{α}(e^{α} − α) = e^{α}(e^{α} − 1 − α), (11.3)

and hence

𝔼 n_{0}^{RH}(T_{α}) − 𝔼 n_{1}^{RH}(T_{α}) = ℙ(ξ_{0} = 1)A − ℙ(ξ_{0} ≥ 2)B,

with A := e^{α}(2 + α − e^{α}) > 0 and B := e^{α}(e^{α} − 1 − α) > 0. Consequently, 𝔼 n_{0}^{RH}(T_{α}) ≥ 𝔼 n_{1}^{RH}(T_{α}) if and only if ℙ(ξ_{0} ≥ 2)/ ℙ(ξ_{0} = 1) ≤ A/B.

Similarly, for k ≥ 1, using (11.1),

𝔼 n_{k}^{RH}(T_{α}) − 𝔼 n_{k+1}^{RH}(T_{α})

= ∑_{j=0}^{k−1}(𝔼 n_{j}^{RH}(T_{α}) + 1[j = 0])(ℙ(ξ_{0} = k − j + 1)A − ℙ(ξ_{0} ≥ k − j + 2)B). (11.4)

For a Poisson distributed variable ξ, ℙ(ξ = j + 1)/ ℙ(ξ = j) is a decreasing function of j, and thus so is ℙ(ξ ≥ j + 1)/ ℙ(ξ = j). Consequently, if 𝔼 n_{0}^{RH}(T_{α}) ≥ 𝔼 n_{1}^{RH}(T_{α}), then for each j ≥ 2

ℙ(ξ ≥ j + 1)/ ℙ(ξ = j) < ℙ(ξ ≥ 2)/ ℙ(ξ = 1) ≤ A/B,

and thus, by (11.4), 𝔼 n_{k}^{RH}(T_{α}) − 𝔼 n_{k+1}^{RH}(T_{α}) > 0 for every k ≥ 1.

Finally, by (11.2) and (11.3),

𝔼 n_{1}^{RH}(T_{α}) − 𝔼 n_{0}^{RH}(T_{α}) = e^{2α} − (2 + α)e^{α} + 1.

Denote this function by f(α). It is easily seen that f(0) = 0, f′(0) < 0, f(1) > 0 and f′′(α) > 0 for α > 0. Hence f is a convex function on [0, 1] with exactly one zero α_{1} > 0, and f(α) < 0 for 0 < α < α_{1} while f(α) > 0 for α_{1} < α < 1. The result follows. □

For LC hashing, we do not have any similar exact results, in view of the complicated expressions in Theorem 9.1. However, as will be shown in a sequel to this paper, as α → 1, the difference between RH and LC becomes negligible; in particular, just as for RH, (1 − α)D_{α}^{LC} →^{d} Exp(1/2). This suggests that the standard probing sequence is almost optimal for LC hashing too. Moreover, it follows from Theorem 9.3 that as α → 1,

(1 − α)^{−1}p_{α}^{LC}(0) → ∫_{0}^{1} \frac{(e^{1−t} − 1)e^{1−t}(1 − t)}{e^{1−te^{1−t}} − 1}dt ≐ 2.647.

This limit is larger than the corresponding limit L_{1} = e−1 for RH found above. Hence, for α close to 1 at least, p_{α}^{LC}(0) > p_{α}^{RH}(0), which suggests that 0 may be the mode of D_{α}^{LC} too for a wide range of α. It would be interesting to have any results on the mode of D_{α}^{LC}. We conjecture, in contrast to RH, that it is 0 for all α.

References

[1] P. Billingsley, Convergence of Probability Measures. John Wiley & Sons, New York, 1968.

[2] É. Borel, Sur l’emploi du théorème de Bernoulli pour faciliter le calcul d’une infinité de coefficients. Application au problème de l’attente à un guichet. C. R. Acad. Sci. Paris 214 (1942), 452–456.

[3] S. Carlsson, J.I. Munro & P.V. Poblete, On linear probing hashing. Unpublished manuscript, 1987.

[4] P. Celis, P.-Å. Larson, J.I. Munro, Robin Hood Hashing (Preliminary Report). FOCS 26 (1985), 281-288.

[5] P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. Rand. Struct. Alg. 21 (2002), no. 1, 76–119.

[6] M. Dwass, The total progeny in a branching process and a related random walk. J. Appl. Probab. 6 (1969), 682–686.

[7] P. Flajolet, P. Poblete & A. Viola, On the analysis of linear probing hashing. Algorithmica 22 (1998), no. 4, 490–515.

[8] R.L. Graham, D.E. Knuth & O. Patashnik, Concrete Mathematics. 2nd ed., Addison– Wesley, Reading, Mass., 1994.

[9] S. Janson, Moment convergence in conditional limit theorems. J. Appl. Probab. 38 (2001), no. 2, 421–437.

[10] S. Janson, Asymptotic distribution for the cost of linear probing hashing. Random Struct. Alg. 19 (2001), no. 3–4, 438–471.

[11] J.H.B. Kemperman, The General One-Dimensional Random Walk with Absorbing Barriers with Applications to Sequential Analysis. Thesis. Excelsiors Foto-Offset, The Hague, 1950.

[12] J.H.B. Kemperman, The Passage Problem for a Stationary Markov Chain. University of Chicago Press, Chicago, Ill., 1961.

[13] D.G. Kendall, Some problems in the theory of queues. J. Roy. Statist. Soc. Ser. B. 13 (1951), 151–185.

[14] D.E. Knuth, Notes on “open” addressing. Unpublished notes, 1963. Available at

http://www.wits.ac.za/helmut/first.ps

[15] D.E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed., Addison-Wesley, Reading, Mass., 1998.

[16] D.E. Knuth, Linear probing and graphs. Algorithmica 22 (1998), no. 4, 561–568.

[17] V.F. Kolchin, Random Mappings. Nauka, Moscow, 1984 (Russian). English transl.: Optimization Software, New York, 1986.

[18] R. Otter, The multiplicative process. Ann. Math. Statist. 20 (1949), 206–224.

[19] Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest. Teor. Verojatnost. i Primenen. 22 (1977), no. 3, 523–533 (Russian). English transl.: Th. Probab. Appl. 22 (1977), no. 3, 509–520.

[20] Yu. L. Pavlov, Random forests. Karelian Centre Russian Acad. Sci., Petrozavodsk, 1996 (Russian). English transl.: VSP, Zeist, The Netherlands, 2000.

[21] J. Pitman, Enumerations of trees and forests related to branching processes and random walks. Microsurveys in discrete probability (Princeton, NJ, 1997), 163–180, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998.

[22] P.V. Poblete & J.I. Munro, Last-come-first-served hashing. J. Algorithms 10 (1989), no. 2, 228–248.

[23] P.V. Poblete, A. Viola & J.I. Munro, The Diagonal Poisson Transform and its application to the analysis of a hashing scheme. Random Struct. Alg. 10 (1997), no. 1-2, 221–255.

[24] P.V. Poblete, A. Viola & J.I. Munro, Analyzing the LCFS linear probing hashing algorithm with the help of Maple. MapleTech 4 (1997), no. 1, 8–13.

[25] L. Takács, Combinatorial Methods in the Theory of Stochastic Processes. John Wiley & Sons, New York, 1967.

[26] L. Takács, Ballots, queues and random graphs. J. Appl. Probab. 26 (1989), no. 1, 103– 112.

[27] J.C. Tanner, A derivation of the Borel distribution. Biometrika 48 (1961), 222–224.

[28] A. Viola, Analysis of hashing algorithms and a new mathematical transform. Ph.D. thesis. Technical report CS-95-50, Computer Science Department, University of Waterloo, Waterloo, ON, Canada, November 1995.

[29] A. Viola, Exact distributions of individual displacements in linear probing hashing. ACM Trans. Algorithms, to appear.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

  E-mail address: svante.janson@math.uu.se
  URL: http://www.math.uu.se/~svante/