записів з 100 елементами і встановити ключі кожного запису в 0. Щоб додати новий запис, просто копіюються її дані у відповідну позицію. Для вставки запису з ключовим значенням 37 слід скопіювати запис в 37-у позицію масиву. Щоб знайти запис з конкретним значенням ключа, програма досліджує відповідний запис масиву. Для видалення запису потрібно просто встановити її ключове значення в 0. Використовуючи таку схему, ви можете додавати, знаходити і видаляти елементи масиву всього за один крок. p align="justify"> На жаль, в реальних додатках ключові значення не завжди розташовуються в діапазонах від 1 до 100. Можливі ключові значення зазвичай охоплюють дуже широкий діапазон. В якості ключа база даних, що містить записи про співробітників, може використовувати номер соціального страхування. Існує 1 млрд можливих комбінацій дев'ятизначних чисел подібно до номера соціального страхування. Теоретично можна створити масив з одним записом для кожного можливого дев'ятизначного номери, але на практиці для цього не вистачить пам'яті і дискового простору. При тому, що кожен запис займає 1 Кбайт пам'яті, для масиву знадобилося б 1 Тбайт (1 млн мегабайт) пам'яті. Навіть якби комп'ютер і виділив такий обсяг пам'яті, ця схема виявилася б дуже неекономною. p align="justify"> Якщо в штаті компанії менше 10 млн службовців, масив на 99% завжди буде порожній.
Для вирішення подібних завдань схеми хешування відображають потенційно велику кількість можливих ключів у відносно компактній хеш-таблиці. Якщо у вашій компанії працює 700 робітників, ви можете оголосити хеш-таблицю з 1000 записами. p align="justify"> Схема хешування встановлює відповідність між 700 записами про службовців і 1000 позиціями таблиці. Хеш-функція може заносити записи в комірки таблиці rfo першим трьом цифрам номера соціального страхування. Запис про співробітника з номером соціального страхування 123-45-6789 буде перебувати у позиції 123. p align="justify"> Звичайно, якщо можливих ключових значень більше, ніж елементів таблиці, деякі ключові значення мають відобразитися в одну і ту ж позицію в хеш-таблиці. Наприклад, значення 123-45-6789 і 123-99-9999 відображаються в таблиці в позицію 123. Якщо є 1 млрд можливих номерів соціального страхування, а в таблиці всього 1000 позицій, в середньому кожну позицію займатиме 1 млн записів. p align="justify"> Щоб уникнути подібної проблеми схема хешування повинна включати алгоритм вирішення конфліктів (collision resolution policy), що визначає порядок дій, якщо ключ відображається на зайняту іншим записом позицію.
Дані методи використовують подібні способи вирішення конфліктних ситуацій. Спочатку ключ запису відображається на позицію хеш-таблиці. Якщо позиція вже зайнята, то ключ заноситься в нову позицію. Ця операція повторюється багато разів до тих пір, поки алгоритм, нарешті, не знайде порожню позицію в табли...
