Кукушка хэширования Коллизии приводят к переполнению

Question

Я пытаюсь реализовать кукушку хеширования с хэш-функций: hash1: key.hashcode()% емкости hash2: key.hashcode()/емкость емкость%

С бесконечным контроль цикла и повторный метод удвоения. Программа отлично работает с небольшим количеством данных, но когда данные становятся большими (около 20 тыс. Элементов), программа продолжает переписываться до тех пор, пока пропускная способность не будет переполнена.

Я понял, что в основном бесконечные причины перехвата данными с точно таким же хэш-кодом. После повторного поединка будут случаи, когда другие данные получат один и тот же хэш-код и снова будут перезаписываться.

Я уже использую встроенный хэш-код Java, но вероятность того же хэш-кода по-прежнему высока, когда данные большие. Даже я немного изменил метод hashcode, в конце концов есть еще данные с одним и тем же хэш-кодом.

Итак, какой хэш-метод следует использовать для предотвращения этого?

Answer 1

Обычный метод создания хеш-функции обычно используется для использования простых чисел. Я пишу функцию (ниже), с которой я не гарантирую никаких столкновений, но ее следует уменьшить.

hashFunction1(String s){ 
    int k = 7;   //take a prime number, can be anything (I just chose 7) 
    for(int i = 0; i < s.length(); i++){ 
     k *= (23 * (int)(s.charAt(i))); 
     k %= capacity; 
    } 
} 
//23 is another randomly chosen number. 

Вы можете написать аналогичную хэш-функцию как hashFunction2, выбрав два разных простых числа. Но здесь главная проблема заключается в том, что для строк «stop» и «pots» это дает тот же хэш-код.

это так, импровизация по этой функции может быть:

hashFunction1(String s){ 
    int k = 7;   //take a prime number, can be anything (I just chose 7) 
    for(int i = 0; i < s.length(); i++){ 
     k *= (23 * (int)(s.charAt(i))); 
     k += (int)(s.charAt(i)); 
     k %= capacity; 
    } 
} 

, который позволит решить это (в большинстве случаев, если не все).

Если вы все еще находите эту функцию плохой, вместо s.charAt (i) вы можете использовать уникальное простое число, сопоставленное каждому символу, т.е. a = 3, b = 5, c = 7, d = 11 и т. д. Это должно еще больше разрешить столкновение.

EDIT:

1. Вы используете +n, который является постоянным.
2. 2 не является основным для использования в таких случаях. Используйте нечетное простое число, 3 работы.