What is the best hash functions for millions of String keys?

Question

I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.

The problem that the retrieval process is too slow and I want to improve the retrieval. I wonder if there is a good hash function to help me with this task.

I am using Separate Channing for resolving the collision

the current hash function

hash = 0
for i = 0 : strlen
    hash = hash * 31 + getChar(strlen, i)

So My question: Is there a better hash function to minimize the collision between the keys?

Answer 1

It's impossible to say without knowing the properties of your keys. Programming language symbol tables tend to need to store a bunch of strings that look like i, j, x1, x2, y1, y2, etc. Simple hash functions often don't disambiguate these well.

There are plenty of hash functions out there. PJW hash/ElfHash is popular for programming languages because it was designed to handle the above cases well.

If you do have millions of keys, probably the best way to do it is to measure the hash chain lengths and see if they follow a Poisson distribution. If you are storing $m$ items in $n$ hash slots, then the number of hash slots with $k$ elements should follow a Poisson distribution with parameter $\lambda = \frac{m}{n}$.

You can test to see if a measured distribution follows an expected distribution using the Pearson $\chi^2$ test.

Answer 2

The best way to avoid collisions is to keep the number of slots large enough. You say "retrieval is too slow" - how slow? You need at the minimum one calculation of a hash key, one comparison, plus one comparison per collision. If you have more than one collision on average, either your hash table doesn't have enough slots, or something is very wrong with your hash function, or something is strange about your data.

BTW. Your hash function will be awful if you add 255 x 255 x 255 strings of three characters to your hash table. I hope you can figure out why, and why Bulat's is a lot better in that case.

But then there is the question: Have you profiled your code? If not, you are operating blindly. Measure how long your code takes, and how long what parts of the code take.

PS. Some standard libraries for various languages have started to use randomised hashes. So every time you start your application, you get a new set of hash functions. (As a consequence, you shouldn't ever store hash codes permanently, because they are invalid if your application starts again). This seems to have some significant advantages, mostly that worst case behaviour won't be permanent. Image 20 of your 25 employees have names whose hash functions collide - randomisation makes sure this will only happen once, and the next time your app is fine.

Answer 3

hash = (hash + getChar(strlen, i)) * 123456791

Answer 4

Hash calculation could be accelerated, if string was interpreted as int array (using word-sized type), striding with int until the end of string, doing rest with char.

Omiting possible need for strlen, I estimate effect comparable with simd, used for number crunching. Any string with less length than int size would not need any calculations at all. Though even with strlen - acceleration should be notable, especially with complex hash functions.

char s[] = "...";
unsigned long long hash = 0;

char     *c = s;
unsigned *i = (void *)s;
int stride = 0;

while (; *c; ++c) {
  stride++;
  if (stride == sizeof(*i))
  {
    hash = ((void*)i > (void*)) ? i[0] : hash * 31 + i[0];
    i++, stride=0;
  }
}

c = (void *)i;

while (; *c; ++c)
  hash = hash * 31 + c[0];

I did not try to even compile it, so don't mindless copy-paste.

Update: simpler approach with length, calculated separately

#include <stdlib.h>

char s[] = "...";
unsigned long long hash = 0;

int len = strlen(s);
unsigned long *u = (void *)s;

ldiv_t len_u = ldiv (len, sizeof(*u));

for (int i = 0; i < len_u.quot; i++)
    hash = hash * 31 + u[0];

for (int i = len - len_u.rem - 1; i < len; i++)
    hash = hash * 31 + s[i];

And using unsigned auto variable as some kind of buffer

char s[] = "...";
unsigned long long hash = 0;

unsigned buf; // processing unit
char *sp, c;  // string pointer & current string
int i;        // position in buf

sp = s;
i = 0;

while (( c = *sp ))
{
  ((char *)&buf)[i] = c;
  i = (i + 1) % sizeof(buf);
  if (!i) {
    hash = hash * 31 + buf;
    buf = 0;
  }
}
if (buf)
  hash = hash * 31 + buf;
```