Презентация на тему Лекція 1/10. Організація хеш-пошуку як узагальнення вибірки за прямою адресою, вибір хеш-функцій та розв’язання колізій

пошуку за прямою адресою;
необхідність надмірно великого адресного простору для

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

адресою на мові С/C++
struct recrd* selNmb(struct recrd* tb, int

nElm)
{return &tb[nElm];
}
На мові Асемблера основна частина кодів вибірки за прямою адресою, розміщеною в [ebx], може мати вигляд:
XLAT ; вибірка байта за прямою адресою
або
MOV eax,tb[ebx*4]; вибірка подвійного слова за адресою
На базі цієї функції будуються функції зміни таблиць
При пошуку за прямою адресою ключова частина полів стає неістотною і може бути усунута з записів.

детерміновані результати для кожного значення аргументу;
обмеження значень у відповідності

з розміром таблиці або її сегментів: Ап + h(Аi)< Аmax;
формувати якомога віддалені значення для близьких значень аргументів пошуку в таблиці;
Забезпечити якомога рівномірний розподіл значень хеш-функції в області визначення.

Кожний елемент таблиці знаходиться за адресою А = Ап + h(Аi ), де Ап – початкова адреса сегменту таблиці, h(Аi ) – хеш-функція i–го ключа.
Вимоги до хеш-функції:

Аi mod N, де N – велике просте число,

що відповідає розміру сегмента таблиці, наприклад, 1009.
лінійно-мультиплікативний метод, за яким h(Аi) = (Σi wi EAi) mod N,
де wi – вагові коефіцієнти, а EAi – елементи аргументу пошуку A.
метод виділення бітів, за яким h(Аi) формується зціпленням потрібної кількості бітів, взятих з визначених позицій ланцюжка бітів заданої функції;
метод фрагментації аргументу, за яким бітовий рядок, що відповідає аргументу А, ділиться на фрагменти, що дорівнюють за довжиною хеш-адресі.

за формулою

як вставка на Асемблері
unsigned hFunc(struct keyStr*pK, unsigned sgLen)
{char*s=pK->str;
_asm{
cld ; визначення позитивного напрямку обробки рядка
mov esi, s ; завантаження адреси початку ключа
mov ecx, 0ffffh ; завантаження максимальної довжини
sub edx, edx ; очистка регістру накопичення суми
l0: lodsd ; завантаження чергових чотирьох байтів
add edx,eax ; додавання складових hash-функції
test al,al ; контроль закінчення рядка
loopnz l0 ; продовження циклу при продовженні рядка
mov eax, edx ; формування результату в акумуляторі
sub edx, edx ; очистка регістру старших розрядів
div sgLen ; одержання залишку
mov eax, edx ; формування результату в акумуляторі
}
}

біля обчисленої хеш-адреси, найбільш відоме і найменш ефективне через

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

Умова виникнення колізій:
h(Аj) = h(Аi), де Аj ≠ Аi.
Базові способи розв'язання колізій:

Формування
виходу
Кінець
Повідомлення
про
переповнення
Так
Співпав
Ні
Так
Ні
Ні

лінійним пошуком
// розв'язання колізій
unsigned hColRes
(struct recrd*pElm, // адреса елемента пошуку

struct recrd*tb, // адреса початку сегмента таблиці
unsigned h, // значення первинної hash-функції
unsigned sgLen) // довжина сегмента таблиці
{int l=2; // кількість кроків розв'язання
while(cmpKys(&(pElm->key), &(tb+h)->key)&&l--)
h=h if(l<0)return l; // контроль досягнення граничного кроку
return h;}

на визначенні критеріїв для:
- Статистики рівномірності розподілу значень в

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

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

обслуговувати вхідні дані системних програм різних обсягів. Якщо розглядати повні таблиці або індекси як автономні об’єкти, для них треба створювати управляючі структури даних, що поєднуватимуть такі автономні структури. В цьому випадку таблиці та структури даних, розглянуті в попередніх розділах можна вважати сегментами даних більш загальних багатосегментних таблиць. Структура, що визначає заголовок багатосегментної таблиці може бути записана наступним чином:
struct sgTbStr // структура сегмента
{int nRsEl; // кількість зарезервованих елементів
int nFlEl; // кількість використаних елементів
struct sgTbStr*pNxtSg;//адреса наступного сегмента
struct recrd* pRcPtr; //покажчик на сегмент записів
};

системних прог-рамах працюють за вимоги унікальності ключів таблиць :
-

Спосіб доступу повинен в більшості випадків давати можливість гарантії унікальності ключів, щоб запобігти можливим неоднознач-ностям при роботі з унікальними об’єктами;