c - C中的重新散列函数

Question

我正在做一个哈希表并实现了以下哈希函数

int linesn=8;
int hash(char *str, int table_size)
{
int sum;

// Make sure a valid string passed in
if (str==NULL) return -1;

// Sum up all the characters in the string
for( ; *str; str++) sum += *str;

// Return the sum mod the table size
return sum % table_size;
}

char *str="Carlos";
int hashv=hash(str,linesn);
printf("\nThe hash value is: %d",hashv);

由于存在任何散列函数冲突，如何实现重新散列函数来防止这些冲突，我在 Google 上阅读过，但示例对我来说很复杂，请任何人给我一个想法。

提前致谢

Answer 1

散列是一个非常有趣的话题。我建议您阅读 Cormen。解释的很清楚。

我会给你一个简单方法的想法--

Here simply take a counter and whenever a element is inserted then increase it. Now if 75% of the table is filled then you just double the size of the array. Allocate twice an array. Now you just again rehash everything using new table size. That's how you do it.

为避免冲突，您可以使用更好的哈希函数。

Another thing incase you have collision just move to the next unfilled one. As <75% is filled in worst case you will get an empty slot. Try this. It is not that good but it works.