Think Distributed

Database and Distributed Systems

文字列に対するハッシュ関数

UNIX プログラミングテクニックという本を10年ぶりぐらいに読み返していたら、文字列に対するハッシュ関数として以下の関数が紹介されていた。Wikipedia によるとどうもこれは ELF で使われているハッシュ関数でもあるらしい。

#include <stdio.h>

unsigned long hashpjw(char *s) {
  char *p;
  unsigned long h = 0;
  for (p = s; *p; p++) {
    h = (h << 4) + (*p);
    unsigned long g = 0;
    if ((g = h) & 0xF0000000) {
      h ^= g >> 24;
      h ^= g;
    }
  }
  return h;
}

int main() {
  printf("%zd\n", hashpjw("abcd"));
  printf("%zd\n", hashpjw("abcdef"));
  printf("%zd\n", hashpjw("abcdefg"));
  printf("%zd\n", hashpjw("abcdefgh"));
  return 0;
}