Главная | Обратная связь

Розв'язання колізій при хешуванні

а) Вибір варіанта індивідуального завдання:

№ варіанта = ( DN + RN + А2 ) % 25+ 1

б) Варіанти завдань:

Розв'язання колізій при хешуванні здійснити:

1. методом роздільних ланцюжків (розмірність хеш-таблиці m=37 замінити на m=7);

2. методом відкритого хешування (розмірність хеш-таблиці m=37 замінити на m=9);

3. методом відкритої адресації з функцією повторного хешування

h_i(key) = ( h(key) + i ) % m;

4. методом закритого хешування з функцією повторного хешування

h_i(key) = ( h(key) + 2 · i ) % m;

5. методом лінійного зондування з функцією повторного хешування

h_i(key) = ( h(key) + 3 · i ) % m;

6. методом лінійної послідовності спроб з функцією повторного хешування

h_i(key) = ( h(key) + 4 · i ) % m;

7. методом рехешування з функцією повторного хешування

h_i(key) = ( h(key) + p_i ) % m ,

де p_i – послідовність випадкових цілих чисел: p₁ = 3, р₂ = 1, p₃ = 7 , ₄ = 4 , ... (за потребою, продовжити цей ряд);

8. методом рехешування додаванням з функцією повторного хешування

h_i(key) = ( h(key) + i · h(key) ) % m;

9. методом відкритої адресації з функцією повторного хешування, що задається таким способом: спочатку перевіряється комірка h(key)+1, після цього перевіряється комірка h(key)–1, далі комірка h(key)+2, далі h(key)–2, далі h(key)+3 і так далі. Якщо досягається один з країв таблиці, то пошук продовжувати тільки з одного боку ключа (тобто тільки +і або тільки –і).

10. методом відкритої адресації з функцією повторного хешування

h_i(key) = ( h(key) + i ² ) % m;

11. методом закритого хешування з функцією повторного хешування

h_i(key) = ( h(key) + 2 · i ² ) % m;

12. методом квадратичного зондування з функцією повторного хешування

h_i(key) = ( h(key) + 3 · i ² ) % m;

13. методом квадратичної послідовності спроб з функцією повторного хешування

h_i(key) = ( h(key) + 4 · i ² ) % m;

14. методом рехешування з функцією повторного хешування

h_i(key) = ( h(key) + p_i · i ² ) % m ,

де p_i – послідовність випадкових цілих чисел: p₁ = 2, р₂ = 5, p₃ = 1, р₄ = 3, ... (за потребою, продовжити цей ряд);

15. методом відкритої адресації з функцією повторного хешування

h_i(key) = ( h(key) + 4 · і + i ² ) % m;

16. методом закритого хешування з функцією повторного хешування

h_i(key) = ( h(key) + 3 · і + 2 · i ² ) % m;

17. методом квадратичного зондування з функцією повторного хешування

h_i(key) = ( h(key) + 2 · і + 3 · i ² ) % m;

18. методом квадратичної послідовності спроб з функцією повторного хешування

h_i(key) = ( h(key) + і + 4 · i ² ) % m;

19. методом рехешування з функцією повторного хешування

h_i(key) = ( h(key) + с_i · і + p_i · i ² ) % m ,

де с_i , p_i – послідовності випадкових цілих чисел: с₁ = 4, с₂ = 1, с₃ = 5, ... ; p₁ = 3, р₂ = 2, p₃ = 4 , ... (за потребою, продовжити ці ряди);

20. методом відкритої адресації з функцією подвійного хешування

h_i(key) = ( h(key) + i · g(key) ) % m ,

де g(key) = 7 – (АSCII-код першого символа ключа – 5) % 7 ;

21. методом закритого хешування з функцією подвійного хешування

h_i(key) = ( h(key) + i · g(key) ) % m ,

де g(key) = 5 – (АSCII-код останього символа ключа + 2) % 5 ;

22. методом лінійного зондування з функцією подвійного хешування

h_i(key) = ( h(key) + 2 · i · g(key) ) % m ,

де g(key) = 1 + (АSCII-код першого символа ключа + 2) % 3 ;

23. методом рехешування з функцією подвійного хешування

h_i(key) = ( h(key) + 3 · i · g(key) ) % m ,

де g(key) = 4 – (АSCII-код останього символа ключа – 9) % 3 ;

24. методом відкритої адресації з функцією повторного хешування

h_i(key) = ( h(key) + i ) % m

та шляхом побудови динамічної хеш-таблиці (при заповненні хеш-таблиці більше ніж наполовину, збільшити її розмір в 2 раза);

25. методом відкритої адресації з функцією повторного хешування

h_i(key) = ( h(key) + i ) % m

та шляхом зміни структури хеш-таблиці (кожну комірку хеш-таблиці замінити блоком з трьох комірок);