Для обчислення індексу використовувати хеш, в разі колізії взяти хеш від хеша; щоб не було зациклення, зберегти значення хеша від хеша в інший хеш-таблиці (або перевірити, чи немає вже цього хеша від хеша в тій хеш-таблиці), для цього спочатку обчислити хеш від хеша від хеша і в разі колізії вже обчислювати не просто 'еш від хеша від хеша, а хеш від хеша від хеша від хеша - yapycoder 18 Квітня '11 о 17:05
Я якщо чесно знатно поржал з останніх слів. Ну да ладно. Спробую зрозуміти і застосувати. - Ray 19 Квітня '11 о 13:23
А я, якщо чесно, не зрозумів, чи зрозумів OP жарт :) - yapycoder 19 Квітня '11 о 13:29
При правильному алгоритмі зациклення бути не може!
Для зменшення довжин ланцюжків колізій треба зробити так, щоб розмір таблиці і крок по ній були взаємно простими числами. Зазвичай роблять таблицю розмір якої просте число, а крок беруть як хеш від хеша.
відповідь дан 20 Квітня '11 о 20:43
Цикл може зациклитися з кількох причин:
1) Вся таблиця заповнена ключами. Вона виникає при коефіцієнті заповнення таблиці рівному 1. Ця проблема вирішується, якщо зробити перехешірованія. Для кожного ключа з таблиці застосувати знову хешування і відправити його в другу таблицю, розмір якої більше. Приклад коду:
2) Помилка в хеш-функції. Справа в тому, що повертається параметр другий хеш-функції повинен бути взаємно простий з розмірами таблиці. Наприклад, якщо розмір таблиці - ступінь 2, то підійде будь-який непарне число. А якщо розмір таблиці просте число - то підійде будь-яка хеш-функція.
3) Неправильне умова в циклі. Потрібно подивитися, які умови зупинки циклу. Головне - число ітерацій не повинно бути більше розміру таблиці.
відповідь дан 11 Листопада '15 о 22:35
Щоб відстежувати зациклення, доведеться городити ще одну структуру. Ідіть іншим шляхом. Є варіант, якщо можливі колізії, передбачати зберігання не окремих занчение по хешу, а список значень, з збігається хешем. Ну, наприклад, можна сортовані список зробити
відповідь даний 18 Квітня '11 о 17:26