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$
  • $\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 at 13:05
  • $\begingroup$ 1. I am using Separate Channing for resolving the collision $\endgroup$ – sc0der May 12 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 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 at 13:33
  • $\begingroup$ yes you are right $\endgroup$ – sc0der May 12 at 13:46
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\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.