Hash Tables

Hashing Idea

Uniformly map the keys

TableSize is prefered to be a prime number. (10007 is a prime number).

Hashing text keys:

$37^2 x_2^2 + 37 x_1 + x_0$ can be written as $37(37 x_2 + x_1) + x_0$

unsigned int hash(const String & key, int tablesize) {
    unsigned int hashval = 0;

    for (ch : key) 
        hashval = hashval * 37 + ch;

    return hashval % tablesize;
}

Collision

Separate Chaining



In [ ]: