6.1 Shift-add

To make the hash function sensitive to the order of letters, we can shift the sum before adding a character. This results in the hash function in listing 6.


Listing 6:hashfunctionwithshift
 
1int h(const char *name, int max) 
2{ 
3  int sum = 0; 
4  while (*name) 
5  { 
6    sum <<= 1; 
7    sum += *name++; 
8  } 
9#ifdef ILLUSTRATE 
10  printf("%d\n",sum); 
11#endif 
12  return sum % max; 
13}

This time, the sums of ASCII codes are different. Kat Auyeung has a raw sum of 171695, whereas Tak Auyeung has a raw sum of 180911. However, in modulo-256 representation, both values become 175.

In general, the shift-add method does work better than the add method.

However, even the shift-add method is considered a poor hash function for strings. This is because the shift operation is nothing more than multiply by 2. The scattering ability of multiply by 2 is limited, especially when MAX_ENTRIES is 256, a multiple of 2!