  Cuckoo hashing with a stash is a robust multiple choice hashing scheme with
high memory utilization that can be used in many network device applications.
Unfortunately, for memory loads beyond 0.5, little is known on its performance.
  In this paper, we analyze its average performance over such loads. We tackle
this problem by recasting the problem as an analysis of the expected maximum
matching size of a given random bipartite graph. We provide exact results for
any finite system, and also deduce asymptotic results as the memory size
increases. We further consider other variants of this problem, and finally
evaluate the performance of our models on Internet backbone traces. More
generally, our results give a tight lower bound on the size of the stash needed
for any multiple-choice hashing scheme.
