На головну

Ключа записи в її адресу

  1.  F15.0 Гостра інтоксикація, обумовлена ??вживанням інших стимуляторів, включаючи кофеїн.
  2.  HKEY_USERS - містить всі активно завантажені профілі користувачів, включаючи HKEY_CURRENT_USER, а також профіль за замовчуванням.
  3.  HTM моделює світ шляхом побудови уявлень причин, включаючи встановлене моторне поведінку
  4.  ORG - Встановити адресою програми
  5.  Абсолютні і відносні адреси осередків
  6.  Автоматична Ip адресація (APIPA)
  7.  Адреса призначення і початкова адреса

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

Спосіб розміщення по обчислюваному адресою використовується для розміщення даних як в основний пам'яті - таблиці з прямим доступом, так і при зберіганні даних на ВЗУ - файли з прямим доступом.

Для обчислення адрес використовуються різні процедури, які виконують лінійні або нелінійні перетворення ключа запису або її коду. В результаті перетворення може визначатися фізичну адресу записи, індекс елемента масиву, що містить запис, номер запису в файлі.

Функція, що виконує процедуру над ключем і генеруюча адреса записи, називається функцією перетворення. У літературі по обробці даних такі функції часто називають рандомізують функціями (Від англ. random access - довільний доступ). Основна вимога до функції перетворення, полягає в тому, що вона повинна генерувати унікальну адресу для кожного запису.

При виборі функції перетворення оцінюється характер даних.

У тих випадках, коли всі записи інформаційного масиву мають

-фіксірованную довжину,

Унікальні послідовні значення ключа,

-діапазон можливих значень ключа не перевищує діапазону адрес доступної пам'яті,

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

Нехай, наприклад, необхідно розмістити в ОП 50 записів фіксованої довжини, ключі яких приймають значення від 0201 до 0250. Діапазон значень ключа - 50. Для зберігання записів використовуємо структуру масиву. Оголосимо масив на 50 елементів. Таким чином виділимо для зберігання записів адреси з1 по 50.

В цьому випадку для обчислення адрес (індексів масиву) можна використовувати наступне перетворення:

ai = ki - p

тут ki - Значення ключа запису; ai - Адреса записи, тобто індекс елемента масиву, в якому розміщена запис з ключем ki; Р - деяке позитивне число.

Виберемо Р = 200. Тоді запис з ключами К = 0211 і К = 0241 будуть займати відповідно 11 і 41 позиції в масиві. Таким чином, для розміщення та подальшого звернення до будь-якого запису потрібно значення її ключа перерахувати в індекс масиву, після чого до будь-якого запису можливий прямий доступ з програми.

Реальні дані не завжди задовольняють перерахованим умовам, і лінійні функції перетворення виявляються непридатними. Так, наприклад, якщо значення ключа не послідовні і мають великий розкид значень, то при використанні лінійної функції багато осередки пам'яті залишаться незайнятими. Для обчислення адрес в цих випадках використовують більш складні функції перетворення. У більшості випадків для обчислення адрес виявляються придатними функції хешування або хеш-функції. Ця назва походить від англ. дієслова to hash (нарізати, кришити, робити місиво). Хеш-функція хешірует, тобто кришить на дрібні шматочки і певним чином їх перемішує послідовність цифр або бітів, що визначають значення ключа запису або її коду. В результаті виходить адреса комірки пам'яті, де буде розміщена ця запис.

Розглянемо, як працює функція хешування, що перетворює ключ по методу згортки. Ця функція розбиває ключ на кілька частин, які потім сумуються таким чином, щоб сформувалося число в необхідному діапазоні (в діапазоні допустимих значень адрес). Нехай, наприклад, записи мають восьмирозрядні ключі К1 = 97434658 і К2 = 31269857, які необхідно перетворити в Трехразрядное адреси. Це завдання можна вирішити, виконавши наступні операції:

h (97434658) = 974 + 346 + 58 = 378

h (31269857) = 312 + 698 + 57 = 067

Тут символ h означає, що обробку ключа виконує хеш-функція. Для того щоб обчислювані адреси були Трехразрядное, складання виробляється по модулю 1000. Результатом складання по mod 1000 є залишок від ділення суми на 1000.

Функція хешування повинна відповідати таким вимогам:

- Обчислювані адреси повинні бути унікальними;

- Функція повинна забезпечувати однозначне перетворення ключа записи в її адресу (даного ключу завжди повинен відповідати один і той же адресу);

- Необхідно, щоб отримані адреси можливо більш рівномірно розподілялися по пам'яті;

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

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

Відомі різні хеш-функції, кожна з яких дає хороші результати при конкретний розподіл значень ключа. Але навіть найкраща хеш-функція не виключає можливість отримання однакових адрес для різних значень ключа. Майже неминучі ситуації, коли різні записи отримують один і той же адресу. Така ситуація називається колізією.

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

Ця функція має такий вигляд:

h (K) = K mod m + 1.

Тут m - дільник. Для обчислення h (K) ключ записи До ділиться на m і залишок від ділення, рівний K mod m, збільшується на 1.

Виберемо m = 101 і виконаємо перетворення h (K) над ключами 2000, 2001, ..., 2017. Вийдуть адреси 82, 83,, 99. Тепер розрахуємо адреси записів для ключів 3313, .3314, ..., 3330. Отримаємо ті ж самі адреси, тобто виникає колізія.

Існують різні методи вирішення колізій.

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

Інший метод вирішення колізій полягає в використанні згенерованого адреси в якості початкової точки для подальшого послідовного перегляду осередків пам'яті. Починаючи з цієї адреси, проводиться пошук вільного місця в пам'яті, куди розміщується запис, що вступила в колізію

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




 Організація пам'яті ЕОМ |  Архітектура машинної пам'яті |  Адресація основної пам'яті |  Три рівня представлення даних |  При розробці структур зберігання встановлюються |  Внутрішня структура запису |  Операції над структурами і типи структур даних |  Послідовне уявлення даних в пам'яті ЕОМ |  масиви |  черга |

© um.co.ua - учбові матеріали та реферати