 |
|
Найпростіші методи побудови хеш-таблиць
У найпростішому випадку хеш-таблиця являє собою лінійний неупорядкований список, або одновимірний масив, кожний елемент якого містить певну інформацію. Розміщення нових елементів у такій таблиці виконується шляхом запису інформації в наступний елемент масиву або списку.
Пошук потрібного елемента в хеш-таблиці буде в цьому випадку виконуватися шляхом послідовного перебору всіх елементів і порівняння їх імені з ім'ям шуканого елемента, поки не буде знайдений елемент із таким же ім'ям. Тоді, якщо за одиницю часу прийняти час, затрачуваний на порівняння двох елементів (у сучасних обчислювальних системах таке порівняння найчастіше виконується однією командою), то для хеш-таблиці, що містить N елементів, у середньому буде виконуватись N/2 порівнянь.
Час, необхідний на додавання нового елемента в хеш-таблицю (Tд), не залежить від числа елементів у хеш-таблиці (N). Але, якщо N велике, то пошук місця потребує значних затрат часу. Час пошуку (Тп) у такій хеш-таблиці можна оцінити як Тп = О(N). Оскільки саме пошук у хеш-таблиці є найбільш часто виконуваною операцією, то такий спосіб організації хеш-таблиць є неефективним.
Пошук може бути виконаний більш ефективно, якщо елементи хеш-таблиці відсортовані. Оскільки пошук здійснюється за іменем, найбільш природним рішенням буде розташувати елементи хеш-таблиці в прямому або зворотному алфавітному порядку. Ефективним методом пошуку в упорядкованому списку з N елементів є бінарний пошук.
При бінарному пошуку на кожному кроці число елементів, які можуть містити шуканий елемент, скорочується в два рази, тому максимальне число порівнянь дорівнює 1 + log 2 N. Тоді час пошуку елемента в хеш-таблиці можна оцінити, як Тп = О(log 2 N). Для порівняння: при N=128 бінарний пошук вимагає якнайбільше 8 порівнянь, а послідовний пошук у неупорядкованій хеш-таблиці — у середньому 64 порівняння.
Недоліком бінарного пошуку є вимога того, щоб хеш-таблиця була відсортованою. Тому що масив інформації, в якому виконується пошук, повинен бути впорядкованим, час його заповнення буде залежати від числа елементів в масиві. Якщо використовувати стандартні алгоритми для сортування масиву даних, то середній час, необхідний на розміщення всіх елементів у хеш-таблиці, можна оцінити як:
Тд = О(N·log 2 N) + k·О(N2),
де k- деякий коефіцієнт, що відображає співвідношення між часом, що витрачається комп'ютером на виконання операції порівняння і часом, необхідним для виконання операції перестановки даних.
При організації бінарного пошуку в хеш-таблиці забезпечується істотне скорочення часу пошуку потрібного елемента за рахунок збільшення часу на розміщення нового елемента в хеш-таблиці. Оскільки додавання нових елементів у хеш-таблицю відбувається істотно рідше, ніж звертання до них, цей метод варто визнати більше ефективним, ніж метод організації неупорядкованої хеш-таблиці. Однак реально цей метод не так часто використовується, оскільки існують більше ефективні методи.