Page 78 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Лабораторна робота № 10.
Хеш-таблиці

Мета: ознайомитись із алгоритмом роботи хеш-таблиць.
Навчитися використовувати хеш-таблиці на прикладі мови
Джава.
Теоретичні відомості

При роботі з алгоритмами обробки даних першочерговим
станів завдання організації структури даних з мінімальним часом
доступу до окремого елементу. На жаль, в більшості відомих нам
структур даних час виконання завдання пошуку лінійно залежить
від кількості елементів. На великих масивах даних,
використовувати таку структуру стає неможливо. Для вирішення
цієї проблеми використовують механізм хешування, що дозволяє
прискорити доступ до даних за рахунок первинного часткового
упорядкування.
Під динамічною безліччю будемо розуміти набір
елементів, кількість і склад якого може постійно змінюватися в
процесі роботи програми. Кожен елемент динамічної безлічі
містить спеціальне поле, зване ключем, за яким здійснюється
пошук. Одним із способів організації таких структур даних є
хешування, а відповідні структури даних називають хеш-
таблицями
Існує ще один корисний і широко використовуваний
метод реалізації словників, який називається хешуванням. Цей
метод вимагає фіксованого часу (в середньому) на виконання
операторів і знімає обмеження, що множини повинні бути
підмножинами деякої кінцевої універсальної множини. У
найгіршому випадку цей метод для виконання операторів
вимагає часу, пропорційного розміру множини, так само, як і у
випадках реалізацій за допомогою масивів і списків. Але при
ретельній розробці алгоритмів ми можемо зробити так, що
76