Hash Algorithms

2011 Nov 06

Hash algorithms are a methodology which try to effeciently calculate the index of the key value in a table using a numerical function to transform the search key into an unsigned integer. A perfect hash function is 1 to 1, but a probabalistic one can have collisions, meaning multiple key values will has to the same hash index - which means in worst case a linear search after that, and in best case will use one of the efficient search algorithms.

Hash effeciency is a measure of how much bigger the hash table needs to be then the total number of hash key values to get acceptable speed. This is related to the statistics and density of the searhc algorithms.

Many hash functions use a sequence of: add, multiply, shift and exclusive-or to calculate the hash index value for the search key value. It is time effecient for calculations for hash table size to be a power of two.

External links:

2007-2008