0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 1) Which collision resolution method is used in your table? 2) Did you profile your program - are you sure that the slowdown is due to inappropriately chosen hash function? 3) Do you have any a priory knowledge about distribution of your strings? $\endgroup$ – Vladislav Bezhentsev May 12 '20 at 13:05
  • $\begingroup$ 1. I am using Separate Channing for resolving the collision $\endgroup$ – sc0der May 12 '20 at 13:21
  • $\begingroup$ I am asking to check if there is a better hash function to minimize the collision between keys $\endgroup$ – sc0der May 12 '20 at 13:22
  • $\begingroup$ Yes, I understand your question. But my point is that, we can't talk about "better" hash function without making some assumptions about the distribution of your strings. I mean, for any hash function we can find a set of strings of any given size, such that all strings from this set have the same hash. But as far as I understand, in your case we can assume that strings are uniformly distributed (please, correct me if I am wrong). $\endgroup$ – Vladislav Bezhentsev May 12 '20 at 13:33
  • $\begingroup$ yes you are right $\endgroup$ – sc0der May 12 '20 at 13:46
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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;
```
New contributor
Nikita Zlobin is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.