Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it allowed for numerical computations that, remarkably, suggested that the variance of the search cost approached a value of 1.883 when the table was full. Furthermore, by using a non-standard mean-centred search algorithm, this would imply that searches could be performed in expected constant time even in a full table.

In spite of the time elapsed since these observations were made, no progress has been made in proving them. In this paper we introduce a technique to work around the intractability of the recurrence equation by solving instead an associated differential equation. While this does not provide an exact solution, it is sufficiently powerful to prove a bound of π2/3 for the variance, and thus obtain a proof that the variance of Robin Hood is bounded by a small constant for load factors arbitrarily close to 1. As a corollary, this proves that the mean-centred search algorithm runs in expected constant time.

We also use this technique to study the performance of Robin Hood hash tables under a long sequence of insertions and deletions, where deletions are implemented by marking elements as deleted. We prove that, in this case, the variance is bounded by 1/(1−α), where α is the load factor.

To model the behaviour of these hash tables, we use a unified approach that we apply also to study the First-Come-First-Served and Last-Come-First-Served collision resolution disciplines, both with and without deletions.

The depth of a trie has been deeply studied when the source which produces the words is a simple source (a memoryless source or a Markov chain). When a source is simple but not an unbiased memoryless source, the expectation and the variance are both of logarithmic order and their dominant terms involve characteristic objects of the source, for instance the entropy. Moreover, there is an asymptotic Gaussian law, even though the speed of convergence towards the Gaussian law has not yet been precisely estimated. The present paper describes a ‘natural’ class of general sources, which does not contain any simple source, where the depth of a random trie, built on a set of words independently drawn from the source, has the same type of probabilistic behaviour as for simple sources: the expectation and the variance are both of logarithmic order and there is an asymptotic Gaussian law. There are precise asymptotic expansions for the expectation and the variance, and the speed of convergence toward the Gaussian law is optimal. The paper first provides analytical conditions on the Dirichlet series of probabilities of a general source under which this Gaussian law can be derived: a pole-free region where the series is of polynomial growth. In a second step, the paper focuses on sources associated with dynamical systems, called dynamical sources, where the Dirichlet series of probabilities is expressed with the transfer operator of the dynamical system. Then, the paper extends results due to Dolgopyat, already generalized by Baladi and Vallée, and shows that the previous analytical conditions are fulfilled for ‘most’ dynamical sources, provided that they ‘strongly differ’ from simple sources. Finally, the present paper describes a class of sources not containing any simple source, where the trie depth has the same type of probabilistic behaviour as for simple sources, even with more precise estimates.