Хешування та хеш-таблиці

Хеш-таблиця являє собою узагальнення звичайного масиву. Можливість прямої індексації елементів звичайного масиву забезпечує доступ до будь-якої позиції в масиві за час 0(1).

Проте, якщо кількість ключів, що реально зберігаються в масиві, мала в порівнянні з кількістю можливих значень ключів, то зберігання такого масиву є не ефективним, а в деяких випадках і неможливим.

Альтернативою в цьому випадку стає хеш-таблиця, яка для зберігання елементів використовує масив з розміром, пропорційним кількості ключів, що реально в ній зберігаються.

А замість безпосереднього використання ключа як індекс елементу в масиву, індекс обчислюється за значенням цього ключа.

У випадку прямої адресації, елемент з ключем k зберігається в комірці під номером k. При хешуванні ж, цей елемент зберігається в комірці з номером h(k), тобто ми використовуємо хеш-функцію h() для обчислення номеру комірки для даного ключа k.

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

 Хешування— перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини.При використанні даного методу ми об'єднуємо всі елементи, хешовані в одну і ту ж комірку в зв'язаний список, а  сама комірка містить покажчик на заголовок такого списку;

якщо ж елементів, ключ яких хешується в номер цієї комірки – немає, то комірка містить null.

Методика відкритого хешування

Хеш-функція. Приклади хеш-функцій

Хеш-функція — функція, що перетворює вхідні дані будь-якого (як правило, великого) розміру в дані фіксованого розміру. int h(nametype x){ int sum = 0; for (unsigned int i = 0; i<strlen(x); i++)

sum = sum+(int)x[i]; return sum%(dict_size) ;}

Закрите хешування

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

Якщо ж ми намагатимемося помістити елемент x в сегмент з номером h(x) який уже зайнятий іншим елементом, то відповідно із методикою повторного хешування вибираємо послідовність інших номерів сегментів h₁(x), h₂(x),… куди ми можемо помістити елемент. Якщо ж вільних сегментів немає, то відповідно хеш-таблиця заповнена і елемент x вставити ми не можемо.

Реалізації хеш-функцій при закритому хешуванні

Лінійне дослідження

При такому методі для визначення послідовності досліджень використовують хеш-функцію:

де i – приймає значення від 0 до m-1.h(k) – називається допоміжною хеш-функцією.

Квадратичне дослідження

Квадратичне дослідження використовує хеш-функцію вигляду:

 

де  – допоміжні константи відмінні від нуля,  i – приймає значення від 0 до m-1.

Подвійне хешування є одним з найкращих способів використання закритого хешування, оскільки отримувані при ньому перестановки є достатньо випадковими.

 Подвійне хешування використовує хеш-функцію вигляду:

  де  – допоміжні хеш-функці i – приймає значення від 0 до m1.

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

  де _m` - повинно бути трішки меншим за m

Тип даних “Дерево”. Основні означення. Обхід дерева в прямому порядку

Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).

Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).

Некінцева вершина також має назву вершини розгалуження (branch node).

Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).

Глибиною вершини x називається довжина шляху від кореня до цієї вершини.

Максимальна глибина вершин дерева називається висотою.

Лісом (forest) називають множину дерев, які не перетинаються.

при проходженні в прямому порядку вузлів дерева T, спочатку відвідується корінь n, далі всі вузли під дерева T₁, всі вузли під дерева T₂, і т.д. Останнім відвідуються вузли під дерева T_k