Cuckoo hashing, introduced by Pagh and Rodler [10], is a dynamic dictionary data structure for storing a set S of n keys from a universe U, with constant lookup time and amortized expected constant insertion time. For the analysis, space (2+∊)n and Ω(log n)-wise independence of the hash functions is sufficient. In experiments mentioned in [10], several weaker hash classes worked well; however, a certain simple multiplicative hash family worked badly. In this paper, we prove that the failure probability is high when cuckoo hashing is run with the multiplicative class or with the very common class of linear hash functions over a prime field, even if space 4n is provided. The key set S is fully random, but it must be relatively dense in the universe U of all keys (like |S| ≥ |U|11/12). The bad behavior and the fact that this effect depends on the density of S in U can also be observed in experiments. The result transfers to larger universes if the keys are chosen from a suitable smaller domain. Viewed from a different perspective, our result illustrates that care must be taken when applying a recent result of Mitzenmacher and Vadhan ([12], SODA 2008) proving good behavior of universal hash classes in combination with key sets that have some entropy. Their result is applicable to cuckoo hashing. A technical hypothesis in [12], namely the assumption that either the “collision probability” or the “maximum probability” is small, translates into the condition that |S| is relatively small in comparison to |U|. Our result shows that the result from [12] on 2-universal classes ceases to hold if |S|/|U| is not small enough, even for very common 2-universal hash classes and fully random key sets.

Evolutionary algorithms are often applied for solving optimization problems that are too complex or different from classical problems so that the application of classical methods is difficult. One example are dynamic problems that change with time. An important class of dynamic problems is the class of tracking problems where an algorithm has to find an approximately optimal solution and insure an almost constant quality in spite of the changing problem. For the application of evolutionary algorithms to static optimization problems, the distribution of the optimization time and most often its expected value are most important. Adopting this perspective a simple tracking problem in the lattice is considered and the performance of a mutation-based evolutionary algorithm is evaluated. For the static case, asymptotically tight upper and lower bounds are proven. These results are applied to derive results on the tracking performance for different rates of change.