функция перефразирования в C

Я делаю хеш-таблицу и реализовал следующую хеш-функцию

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, но примеры для меня сложны, кто-нибудь может дать мне представление, пожалуйста.

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


c hashtable hash-function
person Eduardo Robles    schedule 10.01.2016    source источник
comment
У вас может быть немного лучшая хеш-функция; см. это   -  person Basile Starynkevitch    schedule 10.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

person user2736738    schedule 10.01.2016
comment
@RestlessC0bra.: Да, этот упомянутый метод дает лучший результат. Это метод. В противном случае простое увеличение слотов ничего не даст. Может быть какой-то модифицированный метод обсуждался в какой-то исследовательской статье или что-то в этом роде, но да, основная идея анализа похожа, я бы сказал (если вы ее найдете). - person user2736738; 11.05.2017