Організація хеш-таблиці №1
Побудувати хеш-таблицю розмірністю m=37, метод організації якої вибрати згідно з варіантом. Вибір хеш-функції. а) Вибір варіанта індивідуального завдання: № варіанта = [ (день народження) * (ASCII–код першої літери прізвища – велика латинська літера)] % 20 + 1 б) Варіанти завдань: 1. h(key) = (АSCII-код першого символа ключа) % m; 2. h(key) = (АSCII-код останього символа ключа) % m; 3. h(key) = (сума АSCII-кодів першого і останьої символів ключа) % m; 4. h(key) = [сума АSCII-кодів перших двох символів ключа (якщо ключ містить тільки один символ, то обидва символи вважати рівними першому)] % m; 5. h(key) = [сума АSCII-кодів останніх двох символів ключа (якщо ключ містить тільки один символ, то обидва символи вважати рівними першому) ] % m; 6. h(key) = [сума АSCII-кодів перших трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m; 7. h(key) = [сума АSCII-кодів останніх трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m; 8. h(key) = (сума АSCII-кодів всіх символів ключа) % m; 9. h(key) = (кількість символів в ключі) % m; 10. h(key) = [3*(кількість символів в ключі)] % m;(30) 11. h(key) = [5*(АSCII-код першого символа ключа)] % m; 12. h(key) = [7*(кількість символів в ключі)] % m; 13. h(key) = [10*(АSCII-код останього символа ключа)] % m; 14. h(key) = [(АSCII-код першого символа ключа) *(кількість символів в ключі)] % m; 15. h(key) = [(АSCII-код останього символа ключа) *(кількість символів в ключі)] % m; 16. h(key) = (добуток АSCII-кодів першого і останьої символів ключа) % m; 17. h(key) = [добуток АSCII-кодів перших двох символів ключа (якщо ключ містить тільки один символ, то обидва символи вважати рівними першому)] % m; 18. h(key) = [добуток АSCII-кодів останніх двох символів ключа (якщо ключ містить тільки один символ, то обидва символи вважати рівними першому) ] % m; 19. h(key) = [добуток АSCII-кодів перших трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m; 20. h(key) = [добуток АSCII-кодів останніх трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m;
Розв'язання колізій при хешуванні а) Вибір варіанта індивідуального завдання: № варіанта = [ (місяць народження) * (ASCII–код першої літери прізвища – велика латинська літера)] % 25 + 1 б) Варіанти завдань: Розв'язання колізій при хешуванні здійснити: 1. методом роздільних ланцюжків (розмірність хеш-таблиці m=37 замінити на m=7); 2. методом відкритого хешування (розмірність хеш-таблиці m=37 замінити на m=9); 3. методом відкритої адресації з функцією повторного хешування hi(key) = ( h(key) + i ) % m; 4. методом закритого хешування з функцією повторного хешування hi(key) = ( h(key) + 2 · i ) % m; 5. методом лінійного зондування з функцією повторного хешування hi(key) = ( h(key) + 3 · i ) % m; 6. методом лінійної послідовності спроб з функцією повторного хешування hi(key) = ( h(key) + 4 · i ) % m; 7. методом рехешування з функцією повторного хешування hi(key) = ( h(key) + pi ) % m , де pi – послідовність випадкових цілих чисел: p1 = 3, р2 = 1, p3 = 7 , 4 = 4 , ... (за потребою, продовжити цей ряд); ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|