Page 80 - 4656

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

Якщо сегменти приблизно однакові за розміром, то в
цьому випадку списки всіх сегментів повинні бути найбільш
короткими при даному числі сегментів. Якщо початкова множина
складається з N елементів, тоді середня довжина списків буде N/B
елементів. Якщо можна оцінити величину N і вибрати В якомога
ближче до цієї величини, то в кожному списку буде один-два
елементи. Тоді час виконання операторів словників буде малою
постійною величиною, залежною від N (або, еквівалентною, від
В).
Не завжди ясно, як вибрати хеш-функцію h так, щоб вона
приблизно порівну розподіляла елементи початкової множини по
всіх сегментах.
Тут же ми введемо хеш-функцію (яка буде "хорошою", але
не "відмінною"), визначену на символьних рядках. Ідея побудови
цієї функції полягає в тому, щоб представити символи у вигляді
цілих чисел, використовуючи для цього машинні коди символів.
У мові Pascal є вбудована функція ord(c), яка повертає
цілочисельний код символу с. Таким чином, якщо х - це ключ,
тип даних ключів визначений як аrrау[1..10] of char (у прикладі 2
цей тип даних названий nametype), тоді можна використовувати
хеш-функцію, код якої представлений в прикладі 1.
Якщо в словнику допускається видалення елементів, то
досягши порожнього сегменту ми, не знайшовши елементу х, не
можемо бути упевненими в тому, що його взагалі немає в
словнику, оскільки сегмент може стати порожнім вже після
вставки елементу х. Тому, щоб збільшити ефективність даної
реалізації, необхідно в сегмент, який звільнився після операції
видалення елементу, помістити спеціальну константу, яку
назвемо deleted (видалений). Важливо розрізняти константи
deleted і empty - остання знаходиться в сегментах, які ніколи не
містили елементів. При такому підході (навіть при нагоді
видалення елементів) виконання оператора MEMBER не вимагає
проглядання всієї хеш-таблиці. Крім того, при вставці елементів
78