перефразируя функция в 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); 

Как и в любой хеш-функции существуют столкновения, как можно реализовать функцию Rehashing, чтобы предотвратить эти столкновения, я прочитал Google, но примеры сложны для меня, любой может дать мне идею, пожалуйста.

Заранее спасибо

Answer 1

Хешинг - довольно интересная тема. Я бы посоветовал вам прочитать Кормена. Это ясно объясняет.

Я дам вам идею простого method--

Здесь просто взять счетчик и каждый раз, когда элемент вставлен затем увеличить его. Теперь, если заполняется 75% таблицы, вы просто увеличиваете размер массива . Выделите дважды массив. Теперь вы просто снова перефразируете все, используя новый размер таблицы. Вот как вы это делаете.

Чтобы избежать столкновения, вы можете использовать лучшую хеш-функцию.

Другое дело, если у вас есть столкновение, просто перейдите к следующему незаполненному . Поскольку < 75% заполнено в худшем случае, вы получите пустой слот. Попробуйте это. Это не так хорошо, но это работает.