функція називається функцією хешування або розстановки; таблиці, одержувані при такому способі побудови, називаються таблицями з обчислюваними адресами або перемішую таблицями. p align="justify"> Функції розстановки можуть бути побудовані різними способами. Наприклад, можна в якості номера рядка, в якій зберігається або буде зберігатися при вставці деякий ключ, взяти код першого символу імені, або суму всіх кодів символів ключа за модулем числа M, де M - довжина таблиці (розмір масиву, відведеного для її зберігання) . p align="justify"> При використанні таблиць з обчислюваними адресами може виникнути ряд додаткових проблем. Так, наприклад, при вставці нового запису функція розстановки може видати номер зайнятої рядка масиву (функція розстановки може визначати одні й ті ж значення для кількох різних ключів). Така ситуація при вставці запису називається відносним переповненням таблиці або колізією. При виникненні колізій можливі різні методи їх дозволу:
В· метод відкритого перемішування полягає в додаванні до обчисленому зайнятому номером деякого фіксованого зсуву (повторне перемішування)
'= (k + p) mod N, (3)
якщо новий адресу k'также є зайнятим, слід повторити процедуру повторного перемішування до тих пір, поки не виявиться вільна рядок, або таблиця не буде вичерпаний (якщо значення p і N є взаємно-простими, відкрите перемішування забезпечує знаходження вільного рядка масиву);
В· метод ланцюжків при виникненні колізій формує лінійні списки (ланцюжки), в кожному з яких розташовуються записи з однаковим значенням функції розстановки (у цьому випадку в рядках масиву для розміщення записів слід додати ще одне поле для посилання на наступну ланку списку).
Середня кількість переглядаються записів при пошуку запису в перемішувати таблицях при припущенні рівної ймовірності використання ключів і при використанні функції розстановки з рівномірним розсіюванням ключів по рядках масиву визначається наступним співвідношенням (дозвіл колізій за методом відкритого перемішування)
= (1 -?/2)/(1 -?) (4)
де
? - Коефіцієнт заповненості таблиці (? = N/M); кількість рядків у масиві для зберігання записів; кількість записів у таблиці. p align="justify"> Слід зазначити, що кількість порівнянь при пошуку в перемішувати таблицях згідно (4) залежить не від кількості записів у таблиці, а від заповнювання пам'яті, відведеної для розміщення записів. Для прикладу, при заповнювання масиву на 75% (? = 0.75) кількість порівнянь одно 2.5. Загальна схема системи підтримки таблиць
Хешування даних
Припустимо, що потрібно зберегти кілька записів, які мають унікальні ключі зі значеннями від 1 до 100. Можна створити масив...
