Alfredo Viola

Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets

Keywords: Distributional Analysis, Hashing, Linear Probing, Buckets

This paper presents the first distributional analysis of both, a parking problem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a bα-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, called Tuba 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.

Motivation and previous results

Throughout this paper we consider hash tables that have m locations (m is called the "length" of the table) each of them containing at most b ≥ 1 keys, and we let n (with 0 ≤ n ≤ bm) denote the total number of keys (the "size") in the table. The ratio α = n/bm is called the "load factor" of the table. Clearly, the number of tables (the number of hash sequences) with length m and size n is m n , The simplest collision resolution scheme for open addressing hash tables with hash function h(x) is linear probing [START_REF] Gonnet | Handbook of Algorithms and Data Structures: in Pascal and C[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF][START_REF] Sedgewick | Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching[END_REF], which uses the cyclic probe sequence h(K), h(K)+1, . . . m-1, 0, 1, . . . , h(K)-1, assuming the table slots are numbered from 0 to m -1. Linear probing works reasonably well for tables that are not too full, but as the load factor increases, its performance deteriorates rapidly. Its main application is to retrieve information in secondary storage devices when the load factor is not too high, as first proposed by Peterson [START_REF] Peterson | Addressing for random-access storage[END_REF]. One reason for the use of linear probing is that it preserves locality of reference between successive probes, thus avoiding long seeks [START_REF] Larson | Analysis of uniform hashing[END_REF].

For each element x that gets placed at some location y, the circular distance between y and h(x) (that is, y -h(x) if h(x) ≤ y, and m + h(x) -y otherwise) is called its displacement. Displacement is both a measure of the cost of inserting x and of the cost of searching x in the table. Total displacement corresponding to a sequence of hashed values is the sum of the individual displacements of elements. and it determines the construction cost of the table.

Linear probing hashing has been the object of intense study; see the table on results and the bibliography in [19, pp. 51-54]. The first published analysis of linear probing was done by Konheim and Weiss [START_REF] Konheim | An occupancy discipline and applications[END_REF]. In addition, there is also special value for these problems since the first analysis of algorithms ever performed by D. Knuth [START_REF] Knuth | [END_REF] was that of linear probing hashing. As Knuth indicates in many of his writings, the problem has had a strong influence on his scientific carreer. Moreover, the construction cost to fill a linear probing hash table connects to a wealth of interesting combinatorial and analytic problems. More specifically, the Airy distribution that surfaces as a limit law in this construction cost is also present in random trees (inversions and path length), random graphs (the complexity or excess parameter), and in random walks (area) [START_REF] Knuth | Linear probing and graphs[END_REF][START_REF] Flajolet | On the analysis of linear probing hashing[END_REF].

Operating primarily in the context of double hashing, several authors [START_REF] Brent | Reducing the retrieval time of scatter storage techniques[END_REF][START_REF] Amble | Ordered hash tables[END_REF][START_REF] Gonnet | Efficient ordering of hash tables[END_REF] observed that a collision could be resolved in favor of any of the keys involved, and used this additional degree of freedom to decrease the expected search time in the table. We obtain the standard scheme by letting the incoming key probe its next location. So, we may see this standard policy as a first-come-first-served (FCFS) heuristic. Later Celis, Larson and Munro [START_REF] Celis | Robin Hood Hashing[END_REF][START_REF] Celis | Robin Hood hashing[END_REF] were the first to observe that collisions could be resolved having variance reduction as a goal. They defined the Robin Hood heuristic, in which each collision occurring on each insertion is resolved in favor of the key that is farthest away from its home location. Later, Poblete and Munro [START_REF] Poblete | Last-come-first-served hashing[END_REF] defined the last-come-first-served (LCFS) heuristic, where collisions are resolved in favor of the incoming key, and others are moved ahead one position in their probe sequences. These strategies do not look ahead in the probe sequence, since the decision is made before any of the keys probes its next location. As a consequence, they do not improve the average search cost.

It is shown in [START_REF] Carlsson | On linear probing hashing[END_REF] that the Robin Hood linear probing algorithm minimizes the variance of all linear probing algorithms that do not look ahead. This variance, for a full table, is Θ(m), instead of the Θ(m 3/2 ) of the standard algorithm. They derived the following expressions for the variance of C m,n , the successful search time

Var[C m,n ] = 1 2 Q 1 (m, n -1) - 1 4 Q 0 (m, n -1) 2 - 1 6 Q 0 (m, n -1) + 1 6 n -1 m - 1 12 , Var[C m,αm ] = 1 4(1 -α) 2 - 1 6(1 -α) - 1 12 + α 6 - 1 6m - 1 + 2α 3(1 -α 4 )m + O 1 m 2 , Var[C m,m ] = 4 -π 8 m + 1 9 - π 48 + 1 135 2π m + O 1 m 2 . (1)
Moreover, in [START_REF] Janson | Individual displacements for linear probing hashing with different insertion policies[END_REF] and [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF], a distributional analysis for the FCFS, LCFS and Robin Hood heuristic is presented. More specifically, for the Robin Hood heuristic, they obtain

P r{C m,n = r} = n+1 i=r n + 1 i (m -n -1 + i) (n + 1)m i i+1-r k=0 (-1) i+1-r-k i + 1 r + k k i , P r{C m,αm = r} = (1 -α) i≥r α i-1 i! i+1-r k=1 (-1) i+1-k-r i + 1 r + k k i - 1 2m   i≥r α i (i -1)(i -2 -iα) i! i+1-r k=1 (-1) i+1-k-r i + 1 r + k k i   + O 1 m 2 , C α (z) = lim m→∞ ∞ r=0 P r{C m,αm = r}z r = z 1 -α α e zα -e α ze α -e zα ,
where C α (z) is the probability generating function of the successful search time when m, n → ∞ and m/n = α, 0 ≤ α < 1.

These results consider a hash table with buckets of size 1. However, very little is known when we have tables with buckets of size b. In [START_REF] Blake | Big buckets are (are not) better![END_REF], Blake and Konheim studied the asymptotic behavior of the expected cost of successful searches as the number of elements and buckets tend to infinity with their ratio remaining constant. Mendelson [START_REF] Mendelson | Analysis of linear probing with buckets[END_REF] derived exact formulae for the same expected cost, but only solved them numerically. These papers consider the FCFS heuristic. In [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF] the first exact analysis of a linear probing hashing scheme with buckets of size b is presented. In that paper, they find the expected value and the asymptotic behavior of the average cost of successful searches when the Robin Hood heuristic is used. One of their main methodological contributions is the introduction of a new sequence of numbers T k,d,b for 0 ≤ d < b (that we call Tuba Numbers (i) ), and is one of the key components of the analysis presented in this paper. This is sequence EIS A124453 in Neil Sloane's Encyclopedia of Integer Sequences.

In this paper we complete the work presented in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF], and find the distribution for the search cost of a random element when we construct a linear probing hash table using the Robin Hood heuristic, in tables with buckets of size b. As far as we know this is the first distributional analysis of a hashing scheme with buckets of size b. An open problem presented in the first edition of [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF] requested for the average search cost of a random element in a linear probing hash table with buckets of size b. This problem was solved in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF], and this paper generalize this result.

More specifically, we give the distribution for the search cost of a random element for bα-full tables (0 ≤ α < 1), as n, m → ∞ while n/m = bα. These results can also be derived for tables of fixed length m and size n, by the use of the Poisson transform presented in Section 3. However, the formulae lead to very lengthy and complicated expressions, and so we generally leave the results only in the Poisson model. It is mandatory to acknowledge that several of the main technical results needed to present this analysis have been presented in [START_REF] Blake | Big buckets are (are not) better![END_REF]. These contributions are a key component to find the generating functions for the Tuba Numbers, that lead to exact expressions for the distributions presented in this paper. More specifically in Lemma 3.1 (page 595) they characterize the sequence T k,0,b (d = 0), and in Theorem 4.1 (page 602) they give its generating function. Other important related results presented in that paper are used as a starting basis for our analysis. Nevertheless, they do not exploit the combinatorial structure of the problem as presented in [START_REF] Flajolet | On the analysis of linear probing hashing[END_REF]. This combinatorial structure allows us to find powerful results based on the methodology presented in [START_REF] Flajolet | Analytic Combinatorics[END_REF]. As a consequence, when we interpret the results in [START_REF] Blake | Big buckets are (are not) better![END_REF] under a combinatorial point of view, we may generalize those theorems and find the generating functions for the Tuba Numbers for all values of d.

Another main contribution of the paper (as a consequence of the methodology used to analyze the Robin Hood algorithm) is the full distribution of the number of cars that overflow in the parking problem with buckets. This problem was introduced in [START_REF] Konheim | An occupancy discipline and applications[END_REF] and in [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF] the problem is presented as "A certain one-way street has m parking spaces in a row numbered 1 to m. A man and his dozing wife drive by, and suddenly, she wakes up and orders him to park immediately. He dutifully parks at the first available space [. . . ]." This problem has been extensively studied, and some later references are [START_REF] Prellberg | Counting defective parking functions[END_REF][START_REF] Chassaing | Parking functions, empirical processes, and the width of rooted labeled trees[END_REF][START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF][START_REF] Panholzer | On a discrete parking problem[END_REF]. A general framework for this problem can be found in [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF]. We have to notice that some the results presented in [START_REF] Prellberg | Counting defective parking functions[END_REF] could be derived from the results in [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF][START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF] by depoissonization, since the analysis of Robin Hood needs as a subproblem the analysis of the parking problem. In this paper we give the distribution for the number of cars that overflow, when α < 1. This is the first result for the parking problem with buckets of size b > 1.

This paper is organized as follows. Section 2 and 3 are devoted to present some basic mathematical background used in the analysis, like the Tree Function and the Poisson Transform. It continues in Section 4 with the presentation of the Robin Hood Linear Probing Hashing Algorithm and in Section 5 with its relation with the Parking Problem. The main methodological contributions of the paper are presented in Section 6 where a combinatorial characterization of Linear Probing Hashing introduced already in [START_REF] Knuth | Linear probing and graphs[END_REF][START_REF] Flajolet | On the analysis of linear probing hashing[END_REF] is used to proper interpret and generalize the results presented in [START_REF] Blake | Big buckets are (are not) better![END_REF], and in Section 7 where a new sequence of numbers T k,d,b (called Tuba Numbers), which is a key tool to perform this analysis, is studied. Finally in Section 8 a distributional analysis of the Parking Problem is presented and in 4 the distributional analysis of the search cost of a random element in the Robin Hood Linear Probing Hashing is derived, including the exact expressions in the Poisson Model for all the factorial moments.

2 The tree function and the Q functions One of the main characters in this paper is the tree function that is defined implicitly by T (z) = ze T (z) (and so T (ze -z ) = z) and that appears originally in problems related with the counting of rooted labeled trees [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Goulden | Combinatorial Enumeration[END_REF][START_REF] Moon | Counting labelled trees[END_REF][START_REF] Wilf | generatingfunctionology[END_REF]. The Lagrange inversion theorem provides a number of series expansions like

T (z) = n≥1 n n-1 n! z n , T (z) m = m n≥m n n-m-1 n! n m z n , (2)
where

a k = a(a -1) • • • (a -k + 1)
. Most generating functions in this paper involve rational fractions in T (z) with denominators that are powers of (1 -T ) -1 . Lagrange inversion also provides

1 1 -T (z) = 1 + ∞ n=1 n n z n n! . (3)
The asymptotic form of coefficients of any rational function of T is also directly recovered by singularity analysis [START_REF] Flajolet | Singularity analysis of generating functions[END_REF][START_REF] Odlyzko | Asymptotic enumeration methods[END_REF]. An application of the method requires the singular expansion of T (z), itself obtained from the implicit function theorem.

Lemma 1. The function T (z) has a unique dominant singularity at z = 1/e, and its singular expansion in a slit neighbourhood of 1/e is

T (z) = 1 -δ(z) + 1 3 δ(z) 2 - 11 72 δ(z) 3 + 43 540 δ(z) 4 + O δ(z) 5 . ( 4
)
where

δ(z) = √ 2 √ 1 -ez.
In close association with the tree function is what Knuth has popularized under the name of the "Ramanujan Q-function". This function [START_REF] Bruce | Ramanujan's Notebooks, Part II[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 1 Fundamental Algorithms[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 2 Seminumerical Algorithms[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF] and its close relatives play a central rôle in the analysis of many algorithms and data structures -hashing with linear probing [START_REF] Knuth | [END_REF][START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF], union-find algorithms [START_REF] Knuth | The expected linearity of a simple equivalence algorithm[END_REF], interleaved memory [START_REF] Knuth | Activity in an interleaved memory[END_REF], optimal caching [START_REF] Knuth | Analysis of optimum caching[END_REF], and random mappings [START_REF] Broder | Two counting problems solved via string encodings[END_REF][START_REF] Flajolet | Random mapping statistics[END_REF][START_REF] Knuth | The Art of Computer Programming, volume 2 Seminumerical Algorithms[END_REF], most notably. The Q-function is defined by

Q(n) = 1 + n -1 n + (n -1)(n -2) n 2 + • • • ,
or, in a way that is equivalent thanks to (2),

log 1 1 -T (z) = n≥0 Q(n)n n-1 z n n! . ( 5
)
Singularity analysis of the generating function yields immediately

Q(n) ∼ πn 2 - 1 3 + 1 12 π 2n - 4 135n + • • • . (6)
An asymptotic series for Q(n) was first derived by Ramanujan [START_REF] Bruce | Ramanujan's Notebooks, Part II[END_REF], and tight estimates are obtained in [START_REF] Flajolet | On Ramanujan's Q-function[END_REF].

For the purpose of expressing the average-case analysis of sparse tables, Knuth [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF] has extended the Ramanujan Q-function as

Q r (m, n) = i≥0 i + r i n i m i , so that Q(n) = Q 0 (n, n -1).
From the definition, one has

∞ n=0 Q r (m, n)m n t n n! = e mt (1 -t) r+1 . (7)
Then, by differentation,

Q r (m, n) = V r (m, n)Q 0 (m, n),
for some polynomials V r (m, n) that can be mechanically obtained from [START_REF] Carlsson | On linear probing hashing[END_REF]. For α fixed with 0 ≤ α < 1, basic asymptotic approximations entail

Q 0 (m, αm -1) = 1 1 -α - 1 (1 -α) 3 m -1 + 2 + α (1 -α) 5 m -2 - α 2 + 8α + 6 (1 -α) 7 m -3 + α 3 + 22α 2 + 58α + 24 (1 -α) 9 m -4 + O(m -5 ), (8)
and

Q r (m, m -c) = √ π Γ r+2 2 2 r+1 2 m r+1 2 + √ π Γ r+1 2 2 r 2 r + 2 -3c 3 m r 2 + √ π Γ r+2 2 2 r+1 2 3(r + 2) 2 -6(r + 2) + 2 + 12c 2 24 - c(r + 1) 2 + 4r(r + 2) 2 -7r(r + 2) 72 - cr(r + 1) 3 + rc 2 2 m r-1 2 + O m r-2 2 , (9)
where c and r are fixed. See [START_REF] Poblete | Approximating functions by their Poisson transform[END_REF] for a general framework.

The Poisson Transform

There are two standard models that are extensively used in the analysis of hashing algorithms: the exact filling model and the Poisson filling model. Under the exact model, we have a fixed number of keys, n, that are distributed among m locations, and all m n possible arrangements are equally likely to occur. Under the Poisson model, we assume that each location receives a number of keys that is Poisson distributed with parameter λ, and is independent of the number of keys going elsewhere. This implies that the total number of keys, N , is itself a Poisson distributed random variable with parameter λm:

P r [N = n] = e -λm (λm) n n! n = 0, 1, . . .
This model was first considered in the analysis of hashing by Fagin et al [START_REF] Fagin | Extendible hashing -a fast access method for dynamic files[END_REF] in 1979. Consider a hash table of size m with n elements, in which conflicts are resolved by open addressing using some heuristic. Let P be a property (e.g. cost of a successful search) of a random element of the table, and f m,n be the result of applying a linear operator f (e.g. an expected value) to the probability generating function of P that was found using the exact filling model. Then fm (x), the result of computing the same linear operator f to the probability generating function of P computed using a model with m random independent Poisson distributed objects each with parameter x, is

fm (x) = n≥0 P r [N = n] f m,n = e -mx n≥0 (mx) n n! f m,n . (10)
We may use [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] to define P m [f m,n ; x], the Poisson transform (also called Poisson generating function [START_REF] Flajolet | Mellin transforms and asymptotics : Harmonic sums[END_REF][START_REF] Jacquet | Trie partitioning process: Limiting distributions[END_REF]) of f m,n , as

P m [f m,n ; x] = fm (x) = e -mx n≥0 (mx) n n! f m,n . (11)
If P m [f m,n ; λ] has a MacLaurin expansion in powers of λ, then we can retrieve the original sequence f m,n by the following inversion theorem [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF]:

Theorem 1 (Depoissonization Theorem). If P m [f m,n ; λ] = k≥0 a m,k λ k then f m,n = k≥0 a m,k n k m k .
In this paper we consider λ = bα.

The results obtained under the Poisson filling model can also be interpreted as an approximation of those one would obtain under the exact filling model when n, m → ∞ with n = bαm. This approximation can be formalized by means of an asymptotic expansion. Poblete, in [START_REF] Poblete | Approximating functions by their Poisson transform[END_REF], presents an approximation theorem and gives an explicit form for all the terms of the expansion.

Theorem 2 ([42]). For bα = n/m, f m,n = P m [f m,n ; bα] + j≥1 1 n j 2j i=j+1 (bα) i c i,j ∂ i α P m [f m,n ; bα],
where

c i,j = 1 i! k≥0 (-1) i-k+j i k k k -j ,
and k k-j denotes the Stirling numbers of the first kind. For most situations and applications, this approximation is satisfactory. However, it cannot be used when we have a full, or almost full table (α is very close to 1).

The Robin Hood Linear Probing Hashing Algorithm

We follow the ideas presented in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF] and [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF]. Figure 1 shows the result of inserting elements with the keys 36, 77, 24, 69, 18, 56, 97, 78, 49, 79, 38 and 10 in a table with ten buckets of size 2, with hash function h(x) = x mod 10, and resolving collisions by linear probing using the Robin Hood heuristic. When there is a collision in location i, then the element that has probed the least number of locations, probes location (i + 1) mod m. In the case of a tie, we (arbitrarily) move the element whose key has largest value.

Figure 2 shows the partially filled table after inserting 58. There is a collision with 18 and 38. Since there is a tie (all of them are in their first probe location), we arbitrarily decide to move 58, the largest key. Then 58 is in its second probe location, 78 also, but 49 is in its first one. So 49 has to move. Then 49, 69, 79 are all in their second probe location, so 79 has to move to its final position by the tie-break policy described above.

The following properties are easily verified:

• At least one element is in its home location. • The keys are stored in nondecreasing order by hash value, starting at some location k and wrapping around. In our example k=4 (corresponding to the home location of 24).

• If a fixed rule (that depends only on the value of the keys and not in the order they are inserted) is used to break ties among the candidates to probe their next probe location (eg: by sorting these keys in increasing order), then the resulting table is independent of the order in which the elements were inserted [START_REF] Celis | Robin Hood Hashing[END_REF].

Linear Probing Sort and the Parking Problem

To analyze Robin Hood linear probing, we first have to discuss some ideas presented in [START_REF] Carlsson | On linear probing hashing[END_REF][START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF][START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF] and [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF]. When the hash function is order preserving (that is, if x < y then h(x) < h(y)), a variation of the Robin Hood linear probing algorithm can be used to sort [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF], by successively inserting the n elements in an initially empty table. In this case, instead of letting the excess elements from the rightmost location of the table wrap around to location zero, we can use an overflow area consisting of locations m, m + 1, etc. The number of locations needed for this overflow area is an important performance measure for this sorting algorithm. This problem is related to the study of the cost of successful searches in the Robin Hood linear probing algorithm, as follows. Without loss of generality, we search for an element that hashes to location 0. Moreover, since the order of the insertion is not important, we assume that this element is the last one inserted. If we look at the table after the first n elements have been inserted, all the elements that hash to location 0 (if any) will be occupying contiguous locations, near the beginning of the table. The locations preceding them will be occupied by elements that wrapped around from the right end of the table, as can be seen in Figure 2. The key observation here is that those elements are exactly the ones that would have gone to the overflow area. Furthermore, it is easy to see that the number of elements in this overflow area does not change when the elements that hash to 0 are removed. As a consequence, the cost of retrieving an elements that hashes to 0 can be divided in two parts.

• The number of elements that wrap around the table. In other words, the size of the overflow area.

• The number of elements that hash to location 0.

In Section 8 we study the distribution of the number of the elements that overflow, and in Section 9 we study the distribution for the successful search cost of a random element. In this setting, linear probing sort is the parking problem introduced in [START_REF] Konheim | An occupancy discipline and applications[END_REF].

In this paper we give the distribution for the number of cars that overflow when α < 1, generalizing to b > 1 some of the results presented in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF][START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF][START_REF] Prellberg | Counting defective parking functions[END_REF] for the case b = 1. We thank very much to an anonymous referee for pointng us out that in [START_REF] Seitz | Parking functions and generalizations[END_REF] an exact formula for the generating function of the overflow (called defective bucket parking functions) in the exact filling model has been derived by a rather simple and direct approach. Thus in that thesis an equivalent of the main theorem of Section 8 (Theorem 9) is presented.

We work in the Poisson model, since the presentation is much simpler than in the exact model. Then, with the use of the Poisson transform, we may obtain the exact results for fixed m, n, and b. It is important to note that in [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF][START_REF] Prellberg | Counting defective parking functions[END_REF][START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF] the exact distribution of the elements that overflow when b = 1 and in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF] the average number of elements that overflow (for general b) are calculated in the exact model. This analysis brings a new point of view on the problem. The key element to solve this problem is the use of a new sequence of numbers that we call Tuba Numbers By circular symmetry [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF] and for nonfull tables (n < bm), we may freely assume that one of the empty locations belongs to the rightmost bucket. This assumption of a last empty location in nonfull tables is made from now onwards. When all the empty places belong to the last bucket of the table we say that such a table is almost full. For a given length m there are b almost full tables since the last bucket may contain from 0 to b -1 empty locations.

As a consequence, a general table decomposes as a labeled product of clusters (sometimes also figuratively called "islands") that are, up to relabeling, almost full tables. Furthermore, it will be enough to study almost full tables, and then generalize the results for general tables in a similar way as it is done in [START_REF] Flajolet | On the analysis of linear probing hashing[END_REF], by using the sequence construction for labelled structures as presented in [START_REF] Flajolet | Analytic Combinatorics[END_REF].

As an example, the hash table in Figure 3 has buckets of size b = 3 and six clusters (almost full tables) starting at locations 0, 2, 3, 5, 6, and 8. In a respectively order, their lengths are 2, 1, 2, 1, 2, and 2; their sizes are 5, 0, 4, 0, 3, and 5; and they have 1, 3, 2, 3, 3, 1 free locations in their last bucket.

We present now a combinatorial interpretation of several results presented in [START_REF] Blake | Big buckets are (are not) better![END_REF], that will bring light to some important generalizations. Let F bn+d be the number of ways to construct an almost full table of length n + 1 and size bn + d (that is, there are b -d empty slots in the last bucket). Define also

F d (u) = n≥0 F bn+d u bn+d (bn + d)! N d (z, w) = b-1-d s=0 w b-s F s (zw), 0 ≤ d ≤ b -1. (12)
In this setting N d (z, w) is the generating function for the number of almost full tables with more than d empty locations in the last bucket.

The elementary symmetric functions of variables γ j (z) are defined as the coefficients {σ k (z)} of the polynomial

b k=0 σ k (z)x n-k = b-1 j=0 (x + γ j (z)).
Let r be a primitive b-th root of unity and σ k (z) be the k-th elementary symmetric function of the variables {T (r j z), 0 ≤ j < b}, where T is the Tree function. Lemma 2.3 (page 594) in [START_REF] Blake | Big buckets are (are not) better![END_REF] states

(bz) b-d F d (bz) = (-1) b-d-1 b b-d σ b-d (z), (13)
and formula 3.8 (page 597) states

N 0 (z, w) = 1 - b-1 i=0 1 - b z T r i zw b . (14)
Moreover, since

T (αe -α ) = α, then N 0 (bα, e -α ) = 1, (15)
since the product is 0 because when i = 0, the factor is 0. Let also Q m,n,d be the number of ways of inserting n elements into a table with m buckets of size b, so that a given (say the last) bucket of the table contains more than d empty slots. The bucket size b remains fixed, so we do not include it as a subscript in the sequel. There cannot be more empty slots than the size of the bucket so Q m,n,b = 0. For each of the m n possible arrangements, the last bucket has 0 or more empty slots, and so Q m,n,-1 = m n . Observe that Q m,n,0 gives the number of ways of inserting n elements into a table with m buckets, so that the last bucket is not full. For notational convenience, we define Q 0,n,d = [n = 0] (following the notation presented in [START_REF] Graham | Concrete Mathematics[END_REF] we use [S] to represent 1 if S is true, and 0 otherwise). Let also define

Λ d (z, w) = m≥0 n≥0 Q m,n,d z n n! w bm .
Then, Λ(z, w) is the generating function for the number of ways to construct hash tables such that their last bucket is not full. After a somehow tedious calculation, Lemma 3.2 (page 597) in [START_REF] Blake | Big buckets are (are not) better![END_REF] states

Λ 0 (z, w) = N 0 (z, w) 1 -N 0 (z, w) . (16)
Identity ( 16) could be directly derived, by interpreting a general hash table with more than 0 empty locations in its last bucket as a non-empty sequence of almost full tables, all of them with more than 0 empty locations in their last bucket. The generating function for Λ 0 (z, w) then follows by standard combinatorial techniques as presented in [START_REF] Flajolet | Analytic Combinatorics[END_REF]. This combinatorial interpretation allows a natural generalization of these results, to find Λ d (z, w) for all 0 ≤ d ≤ b -1: a general hash table with more than d empty slots in its last bucket is a sequence of almost full table with more than 0 empty locations, followed by an almost full table with more than d empty slots. As a consequence, we directly deduce: Lemma 2.

Λ d (z, w) = N d (z, w) 1 -N 0 (z, w) .
We may find explicit expressions for these generating functions with the use of the Tuba Numbers.

It does not seem possible to find a closed formula for Q m,n,d . This sequence of numbers is important since

(Q m,n,b-d+1 -Q m,n,b-d
)/m n is the probability that a given bucket of the table contains exactly d elements. In [START_REF] Mendelson | Analysis of linear probing with buckets[END_REF], Mendelson proves

Theorem 3. For 0 ≤ d ≤ b -1, and m > 0, Q m,n,d =      n j=0 n j Q m-1,j,d 0 ≤ n < mb -d 0 n ≥ mb-d
However, a new approach to the study of the numbers Q m,n,d , is presented in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF], where a new sequence of numbers T k,d,b is introduced that satisfies a recurrence resembling that of the Bernoulli numbers. This new sequence may be helpful in solving problems involving recurrences with truncated generating functions.

Let

[A(z)] n = n i=0 a i u i ,
then Theorem 3 translates into the recurrence relation

Q 0,d (u) = 1, Q m,d (u) = [e u Q m-1,d (u)] bm-d-1 , m ≥ 1, (17)
for

Q m,d (u) = n≥0 Q m,n,d u n n! .
The main problem is that we are dealing with a recurrence that involves truncated generating functions.

The strategy presented in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF] consists in finding an exponential generating function T d (u) such that

Q m,d (u) = [T d (u)e mu ] bm-d-1 (18)
where

T d (u) = k≥0 T k,b,d u k
k! , for some coefficients T k,b,d to be determined, and independent of m. Here, b is an implicit parameter, and we use the expression T k,d .

The intuition behind this idea is as follows. From [START_REF] Flajolet | Random mapping statistics[END_REF], we obtain Q m,d (u) by multiplying the truncated generating function Q m-1,d (u) by the series e u and then taking only the first bm -d terms of it (monomials of degree 0, 1, up to , bm -d -1). Moreover, Q 0,d (u) is the first term of e u . It is clear that without any truncations Q m,d (u) would be e mu . However we have to consider a correcting factor originated by these truncations and this is the reason for defining this generating function T d (u). Then [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] gives a non recursive definition of Q m,d (u) that involves the truncated product of two series. The interesting aspect of this approach is that T d (u) does not depend on m. Furthermore, the only dependency on m is captured in the well known series that converges to e mu .

The Tuba Numbers T k,d satisfy some nice properties. For example, the next two theorems are proved in [START_REF] Viola | Analysis of Hashing Algorithms and a New Mathematical Transform[END_REF]. The following can indeed be used as definition.

k j k + d b k-j T j,d = [k = 0]. (19)
A very curious property of these numbers is

Theorem 5. b-1 d=0 T k,d =    b k = 0, -1 k = 1, 0 k > 1, (20)
that translates into b-1 d=0

T d (bα) = b-1 d=0   k≥0 T k,d (bα) k k!   = b(1 -α). (21)
Equation ( 21) is very useful to simplify several expressions in the analysis. In this paper we generalize equation [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF]. One of the key observations is that T d (bα) is the limit of the Poisson transform of Q m,n,d /m n (the probability that a given bucket contains more than d empty slots) when m, n → ∞, n = bαm and α < 1 since

lim m→∞ P m [Q m,n,d /m n ; bα] = lim m→∞ e -mbα n≥0 Q m,n,d m n (mbα) n n! = lim m→∞ e -mbα T d (bα)e mbα bm-d-1 = T d (bα).
As a consequence T d (bα) is the probability that a random bucket has more than d empty locations when m, n → ∞, n = bαm and α < 1. The rate of convergence to this limit value is exponentially small.

Theorem 6. Let Υ m,d (bα) = P m [Q m,n,d /m n ; bα]. That is, Υ m,d (bα)
is the probability, in the Poisson Model, that a given bucket contains more than d empty slots when bmα elements are inserted in a hash table with m buckets of size b, using linear probing as collision resolution scheme. Then, when α < 1,

Υ m,d (bα) = T d (bα) + O α -d e bm(1-α+log α) m -3/2 .
Proof: We first have to notice that when α < 1, then 1 -α + log α < 0. Since Υ m,d (bα) = e -mbα T d (bα)e mbα bm-d-1 and

T d (bα) ≤ b-1 d=0 T d (bα) = b(1 -α) then | T d (bα) -Υ m,d (bα) | ≤ | e -mbα b(1 -α) ∞ j=bm-d (mbα) n n! | = e -mbα (mbα) mb-d (mb -d)! ∞ j=0 j -d m (mbα) j (j + mb -d) j ≤ e -mbα (mbα) mb-d (mb -d)! ∞ j=0 j -d m mbα mb -d + 1 j .
Since the last sum converges when α < 1, then

| T d (bα) -Υ m,d (bα) |= O e -mbα (mbα) mb-d (mb -d)! = O α -d e bm(1-α+log α) m -3/2 .
Theorem 6 generalizes Theorem 3.1 in [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF] since the latter only considers the case b = 1 and d = 0. The identity Υ m,d (bα) = e -mbα T d (bα)e mbα bm-d-1 leads to the following lemma that will be used in the proof of Theorem 9.

Lemma 3. Υ m,d (bα) = T d (bα) + O (bα) bm-d .
The rest of this section is devoted to find an explicit expression for T d (bα). The generating function T 0 (bα) has already been studied in [START_REF] Blake | Big buckets are (are not) better![END_REF]:

Theorem 7 (Theorem 4.1 in [4]). T 0 (bα) = b(1 -α) b-1 j=1 1 -T (r j αe -α α ,
where T is the Tree function and r is a b-th root of unity.

This result can be generalized for T d (bα) for all 0 ≤ d ≤ b -1. We need first to prove an important Lemma.

Lemma 4.

T d (bα) = N d (bα, e -α )T 0 (bα), 0 ≤ d ≤ b -1.
Proof: The decomposition of a general full table as a sequence of almost full tables leads to

Q m,n,d = j≥0 b-d-1 s=0 n bj + s F bj+s Q m-1-j,n-j-bs,0 . (22)
The n elements inserted can be divided in the bj + s elements that go into the last cluster of length j + 1 and n -bj -s elements that go in the rest of the table of length m -1 -j. Since the last cluster should have more than d empty slots, then s should be less than b -d. We then have to multiply for the number of ways to construct these partial tables (F bj+s and Q m-1-j,n-bj-s,0 ), and sum over all possible values of j and s. If we then divide by m n and apply the Poisson Transform to both sides of ( 22) we have

T d (bα) = lim m→∞ P m [Q m,n,d /m n ; bα] = lim m→∞ e -mbα b-1-d s=0 j≥0 F bj+s (bα) bj+s (bj + s)! n≥bj+s Q m-1-j,n-j-b-s,0 (bα) n-bjn-s (n -bj -s)! = lim m→∞ e -mbα b-1-d s=0 j≥0 F bj+s (bα) bj+s (bj + s)! n≥0 Q m-1-j,n,0 (bα) n n! = lim m→∞ e -mbα b-1-d s=0 j≥0 F bj+s (bα) bj+s (bj + s)! T 0 (bα)e (m-1-j)bα bm-d-1 = T 0 (bα) b-1-d s=0 e -α b-s j≥0 F bj+s (bα) bj+s (bj + s)! e -α bj+s = T 0 (bα)N d (bα, e -α ).
Lemma 4 relates T 0 (bα) with T d (bα). Notice that since by equation ( 15) N 0 (bα, e -α ) = 1 then Lemma 4 is also valid for d = 0. A generalization of equation [START_REF] Flajolet | On the analysis of linear probing hashing[END_REF] to N d (bα, e -bα ) will then lead to explicit expressions for T d (bα). We use again elementary symmetric functions.

Lemma 5. N d (bα, e -α ) = [u d ] b-1 i=1 1 -u T (r i αe -α ) α , 0 ≤ d ≤ b -1.
Proof: By equation ( 13)

(bz) b-s F s (bz) = [t s ] t b - b-1 i=0 t -bT (r i z) , 0 ≤ s ≤ b -1.
As a consequence

(e -α ) b-s F s (bαe -α ) = (bα) s-b [t s ] u b - b-1 i=0 t -bT (r i αe -α ) = -(bα) s [t s ] b-1 i=0 t bα - T (r i αe -α ) α = -[u s ] b-1 i=0 u - T (r i αe -α ) α .
We then have

N d (bα, e -α ) = b-1-d s=0 (e -α ) b-s F s (bαe -α ) = - b-1-d s=0 [u s ] b-1 i=0 u - T (r i αe -α ) α = -[u b-1-d ] b-1 i=0 u -T (r i αe -α ) α 1 -u = -[u b-1-d ] (u -1) b-1 i=1 u -T (r i αe -α ) α 1 -u = [u b-1-d ] b-1 i=1 u - T (r i αe -α ) α = [u d ] b-1 i=1 1 -u T (r i αe -α ) α .
Lemmas 4 and 5 lead to the main theorem of this section: Theorem 8.

T d (bα) = b(1 -α) [u d ] b-1 i=1 1 -u T (r i αe -α ) α b-1 j=1 1 -T (r j αe -α ) α , 0 ≤ d ≤ b -1,
where T is the Tree function and r is a b-th root of unity.

The following Corollary will be very useful in the analysis of the parking problem with buckets.

Corollary 1. b-1 d=0 T b-1-d (bα)z d = b(1 -α) b-1 j=1 z -T (r j αe -α ) α b-1 j=1 1 -T (r j αe -α ) α .
8 The parking problem with buckets Notation. Given a bivariate function G(z, α) we define

ZG(z, α) = G(0, α) U z G(z, α) = G(1, α) ∂ z G(z, α) = ∂G(z, α) ∂z .
We first state the main Theorem of this section.

Theorem 9. Let w m,bα,k be the probability of having k cars going to overflow in a bα-full table with m buckets of size b and α < 1, and

Ω m (bα, z) = k≥0 w m,bα,k z k .
Then

Ω m (bα, z) = b(1 -α)(z -1) z b -e bα(z-1) b-1 j=1 z -T (r j αe -α ) α b-1 j=1 1 -T (r j αe -α ) α + O α bm . ( 23
)
Remark 1. When b = 1 then, in the terminology of [START_REF] Prellberg | Counting defective parking functions[END_REF], w mbα,k is the probability of having a defective parking function of defect k.

Proof of Theorem 9:

The proof follows closely the ideas presented in [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF]. We first derive a recurrence for Ω m (bα, z), and then solve it. Let define

Ω(bα, z) = b(1 -α)(z -1) z b -e bα(z-1) b-1 j=1 z -T (r j αe -α ) α b-1 j=1 1 -T (r j αe -α ) α .
Since we have a Poisson process, with probability e -bα α k k! the last bucket receives, in addition to the elements that overflow from the previous bucket, k elements that hash to it. From these elements, all but b of them go to overflow, and their contribution to the recurrence is

e bα(z-1) Ω m-1 (bα, z) z b . (24)
However, when the last bucket receives less than b elements in total, there is no overflow, and so we need a correction term. This correction term is

b s=1 1 -z -s P m,s (bα),
where P m,s (bα) is the probability (in the Poisson Model) of having b -s elements in the last bucket. As we have seen in Section 7 this value is equal to Υ m,s-1 (bα) -Υ m,s (bα), and so the contribution of this correction term is

b s=1 1 -z -s (Υ m,s-1 (bα) -Υ m,s (bα)) = 1 -z -1 b-1 s=0 Υ m,s (bα)z -s . (25)
Notice that Υ m,b (bα) = 0 since Q m,n,b = 0 because there cannot be more than b empty locations in a bucket. As a consequence, from equations ( 24) and ( 25) we obtain the following recurrence

Ω m (bα, z) = e bα(z-1) Ω m-1 (bα, z) z b + 1 -z -1 b-1 s=0 Υ m,s (bα)z -s . (26)
If we can establish that the sequence Ω m (bα, z) converges to Ω(bα, z) when m → ∞, then we finally get

Ω(bα, z) = (z -1) z b -e bα(z-1) b-1 s=0 T b-1-s (bα)z s . (27)
The result would then follow by equation ( 27) and Corollary 1.

The rest of the proof is devoted to prove the existence of such a limit. Let M (bα, z) = e bα(z-1)

z b , N (z) = 1 -z -1 , and R m (bα, z) = b-1 s=0 Υ m,s (bα)z -s .
Then, by equation ( 26) we have

Ω m (bα, z) = M (bα, z) m + N m i=1 M (bα, z) m-i R i (bα, z). (28)
As a consequence, when α < 1, the convergence from Ω m (bα, z) to Ω(bα, z) is established by equation ( 28) and Theorem 6. It remains to prove that for n = 0 . . . bm -

1 (α < 1), then [α n ]Ω m (bα, z) = [α n ]Ω(bα, z).
By equation [START_REF] Knuth | Analysis of optimum caching[END_REF] and Lemma 3 we have

Ω m (bα, z) = M (bα, z) m + N b-1 s=0 T s (bα) + O α bi-s z -s m i=1 M (bα, z) m-i .
Moreover,

M (bα, z) m-i = n≥0 ((m -i)bα) n n! k≥0 n k (-1) n-k z k-b(m-i) ,
and so

[α n ]M (bα, z) m-i contributes with powers of z from -b(m -i) to n -b(m -i) to [α n ]Ω m (bα, z). Since [α j ] Υ m,s (bα) = [α j ] T s (bα) for j = 0 . . . bm -s -1, then [z p ][α n ] (Υ m,s (bα)M (bα, z) m-i z -s ) = [z p ][α n ] (T s (bα)M (bα, z) m-i z -s ), p = n -bm + 1 . . . n -bm + bi -s.
As a consequence, by considering all the contributions in the intersection of all these ranges of p when i = 1..m, we have

[z p ][α n ] N b-1 s=0 T s (bα)z -s m i=1 M (bα, z) m-i = [z p ][α n ] N b-1 s=0 Υ m,s (bα)z -s m i=1 M (bα, z) m-i , p = n -bm + 1 . . . n -b + 1.
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets 323

On the other hand, it is not difficult to see that

[z p ][α n ] (Ω(bα, z) -Ω m (bα, z)) = 0, p = n -bm + 1 . . . n -b + 1,
and so

[z p ][α n ] Ω(bα, z) = [z p ][α n ] Ω m (bα, z), p = n -bm + 1 . . . n -b + 1,
We have then proved that when n ≤ bm -1 (α < 1), then [α n ] Ω(bα, z) = [α n ] Ω m (bα, z). We remark than when n ≥ bm, then this derivation only guarantees equality from powers of z that are greater to zero (n -bm + 1 > 0), and so [α n ] Ω(bα, z) and [α n ] Ω m (bα, z) may differ.

It is very important to notice that Theorem 9 allows the use of Theorem 1 with Ω(bα, z) to obtain w m,n,k in the exact filling model when n ≤ bm -1, since it only needs coefficients of powers of bα less than n. In any case, when n ≥ bm the range of potential non-zero coefficients of powers of z is included in n -bm + 1 . . . n -b + 1, so, at least formally, the use of Theorem 1 would return the exact probabilities in the exact filling model also for n ≥ bm.

When b = 1 we rederive the result presented in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF]]

Ω(α, z) = (z -1)(1 -α) z -e α(z-1) . (29)
Moreover, some of the results presented in [START_REF] Prellberg | Counting defective parking functions[END_REF] could be derived from the results in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF][START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF] by depoissonization. The probabilities can be extracted from equation [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF], by expanding powers of z, and then the results in the exact filling model follow from depoissonization, after expanding those probabilities in a power series in α. An alternative approach would be to depoissonize the distribution [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF] and then extract the coefficients.

For general b however, the depoissonization is rather complicated by the expressions related with the Tuba Numbers. As a consequence we present the results in the Poisson Model, and translate them in the exact model when the final expressions are relatively simple.

The first b probabilities are given in the following theorem:

Theorem 10.

w m,bα,k = e bα k! k i=0 k i (-1) k-i α k-i-1 (k -i + bα)i!T b-1-i (bα) + O α bm 0 ≤ k ≤ b -1.
More specifically, the probability that no car overflows is w bα,0 = e bα T b-1 (bα).

Proof: The result follows from the known identity

∂ k z (A(z, bα)B(z, bα)) = k i=0 k i ∂ k-i z A(z, bα) ∂ i z B(z, bα), with A(z, bα) = (z -1) z b -e bα(z-1) , B(z, bα) = b-1 s=0 T b-1-s (bα)z s ,
and noticing that for 0 ≤ j ≤ b -1, Z∂ j z A(z, bα) = (-1) j α j-1 (j + bα)e bα and Z∂ j z B(z, bα) = j!T b-1-j (bα).

When b = 1 then T 0 (α) = (1 -α), and then we rederive the known result w α,0 = e α (1 -α) presented in [START_REF] Konheim | An occupancy discipline and applications[END_REF]. More generally we may expand A(z, bα) to obtain

(z -1) z b -e bα(z-1) = (1 -z) j≥0 z bj e bα(j+1)(1-z) = n≥0   n b j=0 e bα(j+1) (-1) n-bj (bα(j + 1)) n-1-bj (n -bj)! (b(α -j(1 -α)) + n)   z n . (30)
Notice, that in Theorem 10 we use expansion (30) only for n < b and so j = 0. We may now find all the set of probabilities by using expansion [START_REF] Knuth | The Art of Computer Programming, volume 2 Seminumerical Algorithms[END_REF], to obtain Theorem 11. For all k ≥ 0 we have

w m,bα,k = k b j=0 e bα(j+1) min(b-1,k) i=0 (-1) k-i-bj (k -i -bj)! (bα(j + 1)) k-i-1-bj (k -i + bα(j + 1) -bj)T b-1-i (bα) + O α bm .
It does not seem possible to find a simple way to do depoissonization to the coefficients w m,n,k . From equation [START_REF] Graham | Concrete Mathematics[END_REF] we may also find the expected number of cars that overflow from a random bucket.

Theorem 12. Let Ω m,bα be the r.v for the number of cars that overflow from a bα-full table with m buckets of size b and α < 1. Then

E[Ω m,bα ] = 1 2 1 1 -α -b(1 + α) + b-1 d=1 1 1 -T (r j αe -α ) α + O α bm .
Proof: The result follows by taking derivatives with respect to z in equation ( 23), and noticing that

U z ∂ z   b-1 j=1 z -T (r j αe -α ) α b-1 j=1 1 -T (r j αe -α ) α   = b-1 d=1 1 1 -T (r j αe -α ) α . (31)
We may expand the generating functions of the quasi-inverses of the Tree functions, and then use the depoissonization theorem. As a consequence we obtain: Corollary 2. Let Ω b,m,n be the r.v for the number of cars that overflow from a hash table of length m and size n with buckets of size b. Then

E[Ω b,m,n ] = n/b i=2 n i (-1) i m i m k=1 k i-1 bk -i bk -1 , E[Ω b,m,bm-1 ] = √ 2πbm 4 - 7 6 + b-1 d=1 1 1 -T e 2πid b -1 + 1 48 2π bm + O 1 bm .
It is important to notice that these results have already been presented in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF]. For b = 1 and after using the identity

r k=0 r k k r = (-1) r r!,
we rederive the known result presented in [START_REF] Gonnet | The analysis of linear probing sort by the use of a new mathematical transform[END_REF] E

[Ω 1,m,n ] = 1 2 Q 0 (m, n) -1 - n m , where Q 0 (m, n) = i≥0 n i m i is the Ramanujan Q function.

Analysis of Robin Hood Linear Probing

In this section we find the distribution of the cost of a successful search for a random element in a hash table of size m → ∞ that contains n = bαm elements with 0 ≤ α < 1.

Let Ψ m (bα, z) be the probability generating function for the cost of a successful search for a random element in a bα-full table with m buckets of size b and α < 1.

As mentioned in Section 5 the cost of retrieving a random element is composed by all the elements that hash to the same location (collisions), plus the number of elements that overflow from the previous location. We first derive the generating function C m (bα, z) for the total displacement, that is, the generating function for the total number of comparisons, without considering the fact that we have to count only the number of buckets probed. Then, if

C m (bα, z) = i≥0 c m,i (bα)z i ,
the probability generating function for the cost of a successful search is

Ψ m (bα, z) = z i≥0 c m,i (bα)z i b = z k≥0 b-1 d=0 c m,bk+d (bα) z k = z b b-1 d=0 C m bα, r d z 1/b b-1 p=0 r d z 1/b -p , (32)
where r = e 2πi b is a b-th root of unity. Since the calculations are very involved we extract exact coefficients when possible, and then use the Poisson Transform to find the results in the exact model. A similar approach is used to find higher moments.

If k elements collide with the searched one, the expected total displacement originated by these collisions for (separately) retrieving all these elements. is

1 k + 1 k r=0 z r = 1 k + 1 1 -z k+1 1 -z .
Since the probability of having k elements. colliding with the searched one is e -bα (bα) k k! , we immediately see that the probability generating function of the displacement originated by these collisions is

e -bα 1 -z k≥0 (bα) k (k + 1)! 1 -z k+1 = 1 -e bα(z-1) bα(1 -z) . (33)
To conclude the derivation we have to consider the cost originated by the elements that overflow, and so, by Theorem 9 and equation ( 33) we find

C m (bα, z) = b(1 -α)(1 -e bα(z-1)) bα z b -e bα(z-1) b-1 j=1 z -T (r j αe -α ) α b-1 j=1 1 -T (r j αe -α ) α + O α bm . (34)
When b = 1, T 0 (α) = (1 -α), and so we obtain

lim m→∞ C m (α, z) = 1 -α α 1 -e α(z-1)
z -e α(z-1) , as derived in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF] and [START_REF] Janson | Individual displacements for linear probing hashing with different insertion policies[END_REF].

To extract the coefficients ψ k (bα) we first find c n (bα). Towards this goal we expand equation ( 34)

C m (bα, z) = 1 -z -b b-1 s=0 T b-1-s (bα) bα z s k≥1 e -kbα e kbαz z bk + O α bm = 1 -z -b b-1 s=0 T b-1-s (bα) bα z s n≥0   k≥1 e -kbα (kbα) n+bk (n + bk)!   z n + O α bm = n≥0 b-1 s=0 T b-1-s (bα) bα k≥1 e -kbα (kbα) n-s+bk (n -s + bk)! - (kbα) n-s+b(k+1) (n -s + b(k + 1))! z n + O α bm . (35)
As a consequence, from equations ( 32) and [START_REF] Larson | Analysis of uniform hashing[END_REF] we have proved the following theorem Theorem 13. Let Ψ m,bα be the random variable for the cost of searching a random element in a bα-full table with m buckets of size b and α < 1, using the Robin Hood linear probing hashing algorithm, and let Ψ m (bα, z) be its probability generating function. Then Moreover, the probability ψ i (bα) that i + 1 buckets have to be probed to retrieve a random element is

Even though the calculations are very involved and the expressions very complicated, we are able to present amazingly simple expressions for the first moment, in both models. First, the expected value is obtained in the Poisson model, and then by depoissonization the respective result is obtained in the exact model Theorem 14. Let Ψ b,m,n be the random variable for the cost of searching a random element when we insert n + 1 elements in a hash table of m buckets of size b using the Robin Hood linear probing hashing algorithm. Then for 0 ≤ α < 1 we have

E[Ψ b,m,n+1 ] = 1 + n/b k=1 n i=kb (-1) i-kb i -1 kb -1 (kb) i (i + 1)! n i (bm) i , (37)
where T (u) is the Tree Function (T (u) = ue T (u) ). The result follows after substituting all these identities in equation [START_REF] Peterson | Addressing for random-access storage[END_REF].

From Theorem 13 we may derive exact expressions for the factorial moments. We present here the main results in the Poisson model, that generalize the results presented in [START_REF] Viola | Exact distribution of individual displacements in linear probing hashing[END_REF] leaving the details of the derivations since they are mechanical manipulation of the generating functions and their derivatives. The corresponding expressions in the exact model can be obtained with the use of the Poisson transform, although they are extremely complicated.

We first obtain the exact expression for all the factorial moments of Ψ m,bα . Given the probability generating function Ψ m (bα, z), then E[Ψ r m,bα ] can be can be obtained by differentiating this generating function r times and setting z = 1.

Theorem 15. Let Ψ m,bα be the random variable for the cost of searching a random element in a bα-full table with m buckets of size b and α < 1, using the Robin Hood linear probing hashing algorithm, and let Ψ m (bα, z) be its probability generating function. Then

It is important to notice that the main asymptotic contribution when α → 1 is given by the first sum of equation [START_REF] Poblete | Approximating functions by their Poisson transform[END_REF], while the last two sums vanish for moments greater than 2.

Fig. 1 :

 1 Fig. 1: A Robin Hood Linear Probing hash table.

Fig. 3 :

 3 Fig. 3: A sequence of six almost full tables starting at locations 0, 2, 3, 5, 6, and 8.

  j

b z 1 - 1 j=1 1 -

 111 /b -p , with C m (bα, z) = 1 -e bα(z-1) bα z b -e bα(z-1) b-1 s=0 T b-1-s (bα)z s + O α bm = b(1 -α)(1 -e bα(z-1)) bα z b -e bα(z-1) b-1 j=1 z -T (r j αe -α ) α bT (r j αe -α ) α + O α bm .

  ψ i (bα) = P r{Ψ bα = i + 1} = b(i+k)+d-s (b(i + k) + d -s)! -(kbα) b(i+k+1)+d-s (b(i + k + 1) + d -s)! + O α bm .

1 -

 1 T (r d αe -α ) α .

  b(k+n)+d-s (b(k + n) + d -s)! b(k+n)+d (b(k + n) + d)! -r(r -1) b(k+n)+d (b(k + n) + d)! bk+d-s (bk + d -s)! + O α bm .

6

  Combinatorial characterization of Linear Probing HashingUnder a combinatorial point of view Linear Probing can be seen as a sequence of almost full tables[START_REF] Flajolet | On the analysis of linear probing hashing[END_REF].

	10 70	33 24	36	18 78
	30 81	63	56	38 49
	40	73	96	58
	0 1 2 3 4 5 6 7 8 9

(i) This name was suggested by J. Ian Munro, while the author was working on his PhD. thesis

Acknowledgements

The author wants to thank Patricio Poblete and an anonymous referee for their very useful comments in earlier versions of the paper, that lead to important improvements in its presentation.

† This work of was supported in part by proyecto CSIC fondos 2002-2004 and 2004-2006, from the Universidad de la República. Part of the work was done while the author was at LIPN -CNRS UMR 7030

Proof: While equation [START_REF] Moon | Counting labelled trees[END_REF] is a new result, the special case for a full table (n = bm-1) is derived in [START_REF] Viola | The analysis of linear probing hashing with buckets[END_REF]. Moreover equation [START_REF] Odlyzko | Asymptotic enumeration methods[END_REF] appears in [START_REF] Knuth | The Art of Computer Programming, volume 3 Sorting and Searching[END_REF].

It is important to notice that there are two equivalent expressions for E[Ψ m,bα ]. Equation ( 38) can be directly derived from the explicit formula for ψ i (bα) from Theorem 13, equation ( 39) is derived directly from the generating function, and uses the properties of the Tuba Numbers. It is important to notice that if we expand the generating functions in the sum of equation ( 39) we obtain directly equation [START_REF] Odlyzko | Asymptotic enumeration methods[END_REF]. Let

When we differentiate Ψ m (bα, z), since b-1 d=0 r d = 0 when d = 0, then most of the terms are null after using the operator U z , and so we obtain

with

Moreover we have the following chain of identities: