Optimising hashing functions with genetic algorithms (1991)
Genetic algorithms (aka GA's) are a robust global search strategy that ignore local minima and irrelevant parameters, suitable for large search spaces. It is based on an analogy with natural evolution and survival of the fittest. A generation of potential solutions is formed by randomly mating pairs from the previous generation, giving preference to the better performers. By repeating the process many times a (near) optimal solution evolves. Hashing functions are an implementation for fast table lookup, searching, etc. Given a symbol to store or lookup in a table, a hashing function produces an index into the table, preferably such that all possible symbols will be evenly distributed throughout the table. Their effectiveness is controlled by various parameters such as table size, symbol distribution, and the form of the function itself. This project aims to couple these two areas together to optimise the parameters of a given hashing function, by searching for a good set of values for the parameters with a genetic algorithm.