hashing algorithms for strings

Question

I am reading hashing by Algorithms in C++ by Robert Sedwick

This implementation of a hash function for string keys involves one multiplication and one addition per character in the key. If we were to replace the constant 127 by 128, the program would simply compute the remainder when the number corresponding to the 7-bit ASCII representation of the key was divided by the table size, using Horner's method. The prime base 127 helps us to avoid anomalies if the table size is a power of 2 or a multiple of 2.

int hash(char *v, int M)
    { int h = 0, a = 127;
      for (; *v != 0; v++)
        h = (a*h + *v) % M;
      return h;
    }

A theoretically ideal universal hash function is one for which the chance of a collision between two distinct keys in a table of size M is precisely 1/M. It is possible to prove that using a sequence of different random values, instead of a fixed arbitrary value, for the coefficient a in Program 14.1 turns modular hashing into a universal hash function. However, the cost of generating a new random number for each character in the key is likely to be prohibitive. Program 14.2 demonstrates a practical compromise: We vary the coefficients by generating a simple pseudorandom sequence.

In summary, to use hashing for an abstract symbol-table implementation, the first step is to extend the abstract type interface to include a hash operation that maps keys into nonnegative integers less than M, the table size. The direct implementation

inline int hash(Key v, int M) { return (int) M*(v-s)/; }

does the job for floating-point keys between the values s and t; for integer keys, we can simply return v % M. If M is not prime, the hash function might return

(int) (.616161 * (float) v) % M

or the result of a similar integer computation such as

(16161 * (unsigned) v) % M.

My question how author mean prime base 127 helpus us to avoid anomalies if the table size is power of 2 or a multiple of 2?

What does authorm mean by "for integer keys, we can simply return v % M."?
What does author mean by "If M is not prime, the hash function might return

(int) (.616161 * (float) v) % M

or the result of a similar integer computation such as

(16161 * (unsigned) v) % M.

How author came up with .616161 and 16161?

Request help to understand with simple example

Aki Suihkonen Aki Suihkonen · Accepted Answer · 2014-02-24T10:41:44

First, the base has to be co-prime with the word size, otherwise the first characters of the string do not contribute to the hash value;

e.g. a=256; strings "AABA", "AAABA", "XYZAABA" will all produce the same hash, since the intermediate variable h is calculated modulo 2^32.

It's slightly more complex when only 7 bits are used per character, but the principle holds.

For integer keys, 0<= v <2^32, M = table_size (M is prime), v % M maps the complete range of v approximately uniformly taking account all bits in v.
Multiplying the integer v by a float 0.616161 before taking the modulo M, guarantees somekind of scrambling of the bits in v. Otherwise, just as in the first example, having M=100, would map all the values 1001, 101, 201, 3412341234101 to the same slot, ignoring up to 90% of the bits of the variable.

hashing algorithms for strings

1 Answers