І т.п.). Вибір тієї чи іншої хеш-функції визначається специфікою задачі, що розв'язується. Найпростішими прикладами хеш-функцій можуть бути контрольна сума або CRC .
У загальному випадку однозначної відповідності між вихідними даними та хеш-кодом немає. Тому існує безліч масивів даних, що дають однакові хеш-коди - так звані колізії. Імовірність виникнення колізій грає важливу роль оцінці «якості» хеш-функцій.
Контрольні суми
Нескладні, вкрай швидкі і легко реалізовані апаратні алгоритми, що використовуються для захисту від ненавмисних спотворень, у тому числі помилок апаратури.
За швидкістю обчислення в десятки та сотні разів швидше, ніж криптографічні хеш-функції, і значно простіше в апаратній реалізації.
Платою за таку високу швидкість є відсутність криптостійкості – легка можливість підігнати повідомлення під наперед відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біти) нижче, ніж криптографічних хешей (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій.
Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16-бітові слова та їх підсумовування, що застосовується, наприклад, TCP/IP.
Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька помилкових біт, що йдуть до заданої довжини. Сімейство алгоритмів т.з. «циклічний надлишковий код» задовольняє цим вимогам. До них відноситься, наприклад, CRC32 , що застосовується в апаратурі ZIP.
Криптографічні хеш-функції
Серед безлічі існуючих хеш-функцій прийнято виділяти криптографічно стійкі, які застосовуються в криптографії. Криптостійка хеш-функція перш за все повинна мати стійкістю до колізійдвох типів:
Застосування хешування
Хеш-функції також використовують у деяких структурах даних - хеш-таблицаx і декартових деревах . Вимоги до хеш-функції у разі інші:
- хороша перемішування даних
- швидкий алгоритм обчислення
Звірка даних
Загалом це застосування можна описати, як перевірка деякої інформації на ідентичність оригіналу, без використання оригіналу. Для звіряння використовується хеш-значення інформації, що перевіряється. Розрізняють два основні напрямки цього застосування:
Перевірка на наявність помилок
Наприклад, контрольна сума може бути передана каналом зв'язку разом з основним текстом. На приймальному кінці контрольна сума може бути розрахована заново і її можна порівняти з переданим значенням. Якщо буде виявлено розбіжність, це означає, що з передачі виникли спотворення і можна запросити повтор.
Побутовим аналогом хешування у разі може бути прийом, коли за переїздах у пам'яті тримають кількість місць багажу. Тоді для перевірки не потрібно згадувати про кожну валізу, а достатньо їх порахувати. Збіг означатиме, що жодна валіза не втрачена. Тобто кількість місць багажу є його хеш-кодом.
Перевірка парольної фрази
У більшості випадків парольні фрази не зберігаються на цільових об'єктах, зберігаються лише їх хеш-значення. Зберігати парольні фрази недоцільно, тому що у разі несанкціонованого доступу до файлу з фразами зловмисник дізнається всі парольні фрази і відразу зможе ними скористатися, а при зберіганні хеш-значень він дізнається лише хеш-значення, які не оборотні у вихідні дані, в даному випадку парольну фразу. У ході процедури аутентифікації обчислюється хеш-значення введеної парольної фрази і порівнюється зі збереженим.
Прикладом у разі можуть бути ОС GNU/Linux і Microsoft Windows XP . Вони зберігаються лише хеш-значення парольних фраз з облікових записів користувачів.
Прискорення пошуку даних
Наприклад, при записі текстових полів у базі даних може розраховуватися їхній хеш-код і дані можуть поміщатися в розділ, що відповідає цьому хеш-коду. Тоді при пошуку даних треба буде спочатку обчислити хеш-код тексту і відразу стане відомо, у якому розділі їх треба шукати, тобто шукати треба буде не по всій базі, а лише по одному її розділу (це прискорює пошук).
Побутовим аналогом хешування у разі може бути приміщення слів у словнику по алфавіту. Перша буква слова є його хеш-кодом, і при пошуку ми переглядаємо не весь словник, а лише потрібну букву.
Список алгоритмів
- SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
- RIPEMD-160
- RIPEMD-320
- Snefru
- Tiger (Whirlpool
- IP Internet Checksum (RFC 1071)
Посилання
Wikimedia Foundation. 2010 .
Дивитись що таке "Хеш-функція" в інших словниках:
хеш-функція- Функція, яка за різних розмірів вхідного значення має вихід фіксованого розміру. хеш функція — Тематики інформаційні технології в… Довідник технічного перекладачаВікіпедія
Хеш таблиця це структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) та виконувати три операції: операцію додавання нової пари, операцію пошуку та операцію видалення пари по… … Вікіпедія
Колізією хеш функції називається два різних вхідних блоки даних і таких, що Колізії існують для більшості хеш функцій, але для «хороших» хеш функцій частота їх виникнення близька до теоретичного мінімуму. В деяких окремих випадках … Вікіпедія
Хешування (іноді хешування, англ. hashing) перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш функціями або функціями згортки, а їх результати ... Вікіпедія
Tiger хеш функція, розроблена Рос Андерсон і Елі Біхам в 1995 році. Tiger був призначений для особливо швидкого виконання на 64-розрядних комп'ютерах. Tiger не має патентних обмежень, може використовуватися вільно як з … Вікіпедія
Як я вважаю, багатьом відомо про те, що з 2007 року Національний інститут стандартів і технологій США (NIST) проводить конкурс на розробку хеш-алгоритму для заміни SHA-1 та сімейства алгоритмів SHA-2. Однак ця тема чомусь обділена увагою на сайті. Власне, це і привело мене до вас. Пропоную вашій увазі цикл статей, присвячених хеш-алгоритмам. У цьому циклі ми разом вивчимо основи хеш-функцій, розглянемо найвідоміші хеш-алгоритми, поринемо в атмосферу конкурсу SHA-3 та розглянемо алгоритми, які претендують на перемогу в ньому, обов'язково їх потестуємо. Також по можливості будуть розглянуті російські стандарти хешування.
Про себе
Студент кафедри інформаційної безпеки.Про хешування
В даний час практично жодна програма криптографії не обходиться без використання хешування.Хеш-функції – це функції, призначені для «стиснення» довільного повідомлення або набору даних, записаних, як правило, у двійковому алфавіті, деяку бітову комбінацію фіксованої довжини, звану згорткою. Хеш-функції мають різноманітні застосування під час проведення статистичних експериментів, при тестуванні логічних пристроїв, при побудові алгоритмів швидкого пошуку та перевірки цілісності записів у базах даних. Основною вимогою до хеш-функцій є рівномірність розподілу їх значень за випадкового вибору значень аргументу.
Криптографічної хеш-функцією називається будь-яка хеш-функція, що є криптостійкою, тобто задовольняє ряду вимог, специфічних для криптографічних додатків. У криптографії хеш-функції застосовуються для вирішення наступних завдань:
- побудови систем контролю цілісності даних при їх передачі чи зберіганні,
- Аутентифікація джерела даних.
Хеш-функцією називається будь-яка функція h:X -> Yлегко обчислювана і така, що для будь-якого повідомлення Mзначення h(M) = H (згортка)має фіксовану бітову довжину. X- безліч усіх повідомлень, Y- множина двійкових векторів фіксованої довжини.
Як правило, хеш-функції будують на основі так званих однокрокових стискаючих функцій. y = f(x 1 , x 2)двох змінних, де x 1, x 2і y- Двійкові вектори довжини m, nі nвідповідно, причому n- Довжина згортки, а m- Довжина блоку повідомлення.
Для отримання значення h(M)повідомлення спочатку розбивається на блоки довжини m(при цьому, якщо довжина повідомлення не кратна mто останній блок якимось спеціальним чином доповнюється до повного), а потім до отриманих блоків M 1 , M 2 .., M Nзастосовують наступну послідовну процедуру обчислення згортки:
H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N
Тут v- деяка константа, часто її називають вектором, що ініціалізує. Вона вибирається
з різних міркувань і може бути секретною константою або набір випадкових даних (вибірку дати і часу, наприклад).
При такому підході властивості хеш-функції повністю визначаються властивостями однокрокової функції.
Виділяють два важливі види криптографічних хеш-функцій – ключові та безключові. Ключові функції хеш називають кодами автентифікації повідомлень. Вони дають можливість без додаткових коштів гарантувати як правильність джерела даних, і цілісність даних у системах з користувачами, що довіряють один одному.
Безключові хеш-функції називаються кодами виявлення помилок. Вони дозволяють за допомогою додаткових засобів (шифрування, наприклад) гарантувати цілісність даних. Ці хеш-функції можуть застосовуватися в системах як з користувачами, що довіряють, так і не довіряють один одному.
Про статистичні властивості та вимоги
Як я вже говорив основною вимогою до хеш-функцій, є рівномірність розподілу їх значень при випадковому виборі значень аргументу. Для криптографічних хеш-функцій також важливо, щоб за найменшої зміни аргументу значення функції сильно змінювалося. Це називається лавинним ефектом.
До ключових функцій хешування пред'являються такі вимоги:
- неможливість фабрикації,
- Неможливість модифікації.
Перша вимога означає високу складність підбору повідомлення із правильним значенням згортки. Друге - високу складність підбору для заданого повідомлення з відомим значенням згортки іншого повідомлення з правильним значенням згортки.
До безключових функцій висувають вимоги:
- Односпрямованість,
- стійкість до колізій,
- Стійкість до знаходження другого прообразу.
Під односпрямованістю розуміють високу складність знаходження повідомлення за заданим значенням згортки. Слід зауважити, що на даний момент немає хеш-функцій з доведеною односпрямованістю.
Під стійкістю до колізій розуміють складність знаходження пари повідомлень з однаковими значеннями згортки. Зазвичай саме знаходження способу побудови колізій криптоаналітиками є першим сигналом старіння алгоритму та необхідності його швидкої заміни.
Під стійкістю до знаходження другого прообразу розуміють складність знаходження другого повідомлення з тим самим значенням згортки для заданого повідомлення з відомим значенням згортки.
Це була теоретична частина, яка стане нам у нагоді…
Про популярні хеш-алгоритми
Алгоритми CRC16/32- Контрольна сума (не криптографічне перетворення).
Алгоритми MD2/4/5/6. Є витвором Рона Райвеста, одного з авторів алгоритму RSA.
Алгоритм MD5 мав колись більшу популярність, але перші причини злому з'явилися ще наприкінці дев'яностих, і зараз його популярність стрімко падає.
Алгоритм MD6 – дуже цікавий з конструктивної точки зору алгоритм. Він висувався на конкурс SHA-3, але, на жаль, автори не встигли довести його до кондиції, і у списку кандидатів, які пройшли у другий раунд, цей алгоритм відсутній.
Алгоритми лінійки SHAШироко поширені зараз алгоритми. Іде активний перехід від SHA-1 до стандартів SHA-2. SHA-2 - збірна назва алгоритмів SHA224, SHA256, SHA384 та SHA512. SHA224 та SHA384 є по суті аналогами SHA256 та SHA512 відповідно, тільки після розрахунку згортки частина інформації в ній відкидається. Використовувати їх лише для забезпечення сумісності з обладнанням старих моделей.
Російський стандарт - ГОСТ 34.11-94.
У наступній статті
Огляд алгоритмів MD (MD4, MD5, MD6).
Література
А. П. Алфьоров, Основи криптографії.
Брюс Шнайєр, прикладна криптографія.
Він же хеш «хеш-функція»
Знаходиться у списку.
І т.п.). Вибір тієї чи іншої хеш-функції визначається специфікою задачі, що розв'язується. Найпростішими прикладами хеш-функцій можуть бути контрольна сума або CRC .
У загальному випадку однозначної відповідності між вихідними даними та хеш-кодом немає. Тому існує безліч масивів даних, що дають однакові хеш-коди - так звані колізії. Імовірність виникнення колізій грає важливу роль оцінці «якості» хеш-функцій.
Контрольні суми
Нескладні, вкрай швидкі і легко реалізовані апаратні алгоритми, що використовуються для захисту від ненавмисних спотворень, у тому числі помилок апаратури.
За швидкістю обчислення в десятки та сотні разів швидше, ніж криптографічні хеш-функції, і значно простіше в апаратній реалізації.
Платою за таку високу швидкість є відсутність криптостійкості – легка можливість підігнати повідомлення під наперед відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біти) нижче, ніж криптографічних хешей (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій.
Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16-бітові слова та їх підсумовування, що застосовується, наприклад, TCP/IP.
Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька помилкових біт, що йдуть до заданої довжини. Сімейство алгоритмів т.з. «циклічний надлишковий код» задовольняє цим вимогам. До них відноситься, наприклад, CRC32 , що застосовується в апаратурі ZIP.
Криптографічні хеш-функції
Серед безлічі існуючих хеш-функцій прийнято виділяти криптографічно стійкі, які застосовуються в криптографії. Криптостійка хеш-функція перш за все повинна мати стійкістю до колізійдвох типів:
Застосування хешування
Хеш-функції також використовують у деяких структурах даних - хеш-таблицаx і декартових деревах . Вимоги до хеш-функції у разі інші:
- хороша перемішування даних
- швидкий алгоритм обчислення
Звірка даних
Загалом це застосування можна описати, як перевірка деякої інформації на ідентичність оригіналу, без використання оригіналу. Для звіряння використовується хеш-значення інформації, що перевіряється. Розрізняють два основні напрямки цього застосування:
Перевірка на наявність помилок
Наприклад, контрольна сума може бути передана каналом зв'язку разом з основним текстом. На приймальному кінці контрольна сума може бути розрахована заново і її можна порівняти з переданим значенням. Якщо буде виявлено розбіжність, це означає, що з передачі виникли спотворення і можна запросити повтор.
Побутовим аналогом хешування у разі може бути прийом, коли за переїздах у пам'яті тримають кількість місць багажу. Тоді для перевірки не потрібно згадувати про кожну валізу, а достатньо їх порахувати. Збіг означатиме, що жодна валіза не втрачена. Тобто кількість місць багажу є його хеш-кодом.
Перевірка парольної фрази
У більшості випадків парольні фрази не зберігаються на цільових об'єктах, зберігаються лише їх хеш-значення. Зберігати парольні фрази недоцільно, тому що у разі несанкціонованого доступу до файлу з фразами зловмисник дізнається всі парольні фрази і відразу зможе ними скористатися, а при зберіганні хеш-значень він дізнається лише хеш-значення, які не оборотні у вихідні дані, в даному випадку парольну фразу. У ході процедури аутентифікації обчислюється хеш-значення введеної парольної фрази і порівнюється зі збереженим.
Прикладом у разі можуть бути ОС GNU/Linux і Microsoft Windows XP . Вони зберігаються лише хеш-значення парольних фраз з облікових записів користувачів.
Прискорення пошуку даних
Наприклад, при записі текстових полів у базі даних може розраховуватися їхній хеш-код і дані можуть поміщатися в розділ, що відповідає цьому хеш-коду. Тоді при пошуку даних треба буде спочатку обчислити хеш-код тексту і відразу стане відомо, у якому розділі їх треба шукати, тобто шукати треба буде не по всій базі, а лише по одному її розділу (це прискорює пошук).
Побутовим аналогом хешування у разі може бути приміщення слів у словнику по алфавіту. Перша буква слова є його хеш-кодом, і при пошуку ми переглядаємо не весь словник, а лише потрібну букву.
Список алгоритмів
- SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
- RIPEMD-160
- RIPEMD-320
- Snefru
- Tiger (Whirlpool
- IP Internet Checksum (RFC 1071)
Посилання
Wikimedia Foundation. 2010 .
- Хешан Мохеянь
- Хеш код
Дивитись що таке "Хеш-функція" в інших словниках:
Хеш-функція- функція, що здійснює хешування масиву даних за допомогою відображення значень з (дуже) великої множини значень (істотно) менше безліч значень. Англійською мовою: Hash function Див. також: Криптографічні алгоритми Фінансовий… … Фінансовий словник
криптографічна хеш-функція- Функція, що перетворює текст довільної довжини текст фіксованої (у більшості випадків меншої) довжини. Основне застосування хеш функції знайшли у схемі цифрового підпису. Так як хеш функція обчислюється швидше за цифровий підпис, то замість… …
Одностороння хеш-функція- хеш функція, що є обчислювально незворотною функцією. Англійською мовою: One way hash function Див. також: Криптографічні алгоритми Фінансовий словник Фінам … Фінансовий словник
TIGER - хеш-функція- TIGER хеш функція, розроблена Росом Андерсоном та Елі Біхамом у 1996 році. Хеш функція TIGER є новою швидкою хеш функцією, яка покликана бути дуже швидкою на сучасних комп'ютерах, зокрема, на 64 розрядних комп'ютерах. TIGER… … Вікіпедія
одностороння хеш-функція- Для односторонньої функції обчислювально неможливо знайти два різні аргументи, для яких її значення збігаються. [] Тематика захисту інформації EN one way hash function … Довідник технічного перекладача
Tiger (хеш-функція)- Tiger хеш функція, розроблена Росом Андерсоном та Елі Біхамом у 1995 році. Tiger був призначений для особливо швидкого виконання на 64-розрядних комп'ютерах. Tiger не має патентних обмежень, може використовуватися вільно як з … Вікіпедія
функція хешування- хешфункція 1. Функція, яка керує процесом занесення даних у хеш таблицю, визначаючи (адреси вільних осередків. 2. Функція, що є відображенням фрагмента відкритого повідомлення в шифрований рядок фіксованої довжини. В… … Довідник технічного перекладача
Хеш-таблиця- У програмуванні хеш таблиця це структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) та виконувати три операції: операцію додавання нової пари, операцію пошуку та операцію видалення… Вікіпедія
Хеш код- Хешування (іноді хешування, англ. hashing) перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш функціями або функціями згортки, а їх результати ... Вікіпедія
Колізія хеш-функції- Колізією хеш функції H називається два різні вхідні блоки даних x і y таких, що H(x) = H(y). Колізії існують для більшості хеш функцій, але для «хороших» хеш функцій частота їх виникнення близька до теоретичного мінімуму. В… … Вікіпедія
Розглянуті нами алгоритми пошуку зазвичай ґрунтуються на абстрактній операції порівняння. З цього ряду суттєво виділяється метод розподільного пошуку, описаний у "Таблиці символів та дерева бінарного пошуку", при якому елемент з ключем i зберігається в i-ій позиції таблиці, що дозволяє звернутися до нього безпосередньо. При розподільному пошуку значення ключів використовуються як індекси масиву, а не операнди операції порівняння; сам метод заснований на тому, що ключі є різними цілими числами того ж діапазону, що і індекси таблиці. У цьому розділі ми розглянемо хешування (hashing) - розширений варіант розподільного пошуку, що застосовується в більш типових додатках пошуку, де ключі не мають настільки зручні властивості. Кінцевий результат застосування даного підходу зовсім не схожий на методи, засновані на порівнянні - замість переміщення структурами даних словника за допомогою порівняння ключів пошуку з ключами в елементах, ми намагаємося звернутися до елементів у таблиці безпосередньо, виконуючи арифметичне перетворення ключів на адреси таблиці.
Алгоритми пошуку, що використовують хешування, складаються із двох окремих частин. Перший крок - обчислення хеш-функції (hash function), яка перетворює ключ пошуку на адресу таблиці. В ідеалі різні ключі мали б відображатися на різні адреси, але часто два або більше різних ключів можуть дати одну й ту саму адресу в таблиці. Тому друга частина пошуку методом хешування - процес вирішення колізій (collision resolution), який обробляє такі ключі. В одному з методів вирішення конфліктів, який ми розглянемо в цьому розділі, використовуються зв'язкові списки, тому він знаходить безпосереднє застосування в динамічних ситуаціях, коли важко передбачити кількість ключів пошуку. В інших двох методах вирішення колізій досягається висока продуктивністьпошуку, оскільки елементи зберігаються у фіксованому масиві. Ми розглянемо спосіб удосконалення цих методів, що дозволяє використовувати їх у тих випадках, коли не можна заздалегідь передбачити розміри таблиці.
Хешування - гарний приклад балансу між часом та обсягом пам'яті. Якби не було обмеження на обсяг використовуваної пам'яті, будь-який пошук можна було б виконати за допомогою лише одного звернення до пам'яті, просто використовуючи ключ як адресу пам'яті, як при розподільчому пошуку. Однак зазвичай цей ідеальний випадок недосяжний, оскільки для довгих ключів може знадобитися величезний обсяг пам'яті. З іншого боку, якби не було обмежень на час виконання, можна було обійтися мінімальним обсягом пам'яті, користуючись методом послідовного пошуку. Хеширование є спосіб використання прийнятного обсягу як пам'яті, і часу, і досягнення балансу між цими двома крайніми вимогами. Зокрема, можна підтримувати будь-який баланс просто змінюючи розмір таблиці, а не переписуючи код і не вибираючи інші алгоритми.
Хешування - одне з класичних завдань комп'ютерних наук: його різні алгоритми докладно досліджені та знаходять широке застосування. Ми побачимо, що при зовсім не жорстких припущеннях можна сподіватися на підтримку операцій знайти та вставити у таблицях символів з постійним часом виконання, незалежно від розміру таблиці.
Це очікуване значення - теоретичний оптимум продуктивності для будь-якої реалізації таблиці символів, але хешування все ж таки не є панацеєю з двох основних причин. По перше, час виконаннязалежить від довжини ключа, яка у реальних додатках, що використовують довгі ключі, може бути значною. По-друге, хешування не забезпечує ефективні реалізації інших операцій з таблицями символів, таких як вибрати або сортувати. У цьому розділі ми докладно розглянемо ці та інші питання.
Хеш-функції
Насамперед необхідно вирішити завдання обчислення хеш-функції, що перетворює ключі адреси таблиці. Зазвичай реалізація цього арифметичного обчислення не становить складності, але все ж таки необхідно дотримуватися обережності, щоб не нарватися на різні малопомітні підводні камені. За наявності таблиці, яка може містити елементи M, потрібна функція, що перетворює ключі в цілі числа в діапазоні . Ідеальна хеш-функція повинна легко обчислюватися і бути схожою до випадкової функції: для будь-яких аргументів результати в певному сенсі повинні бути рівноймовірними.
Функція хеш залежить від типу ключа. Строго говорячи, для кожного можливого виду ключів потрібна окрема хеш-функція. Для підвищення ефективності зазвичай бажано уникати явного перетворення типів, звернувшись натомість ідеї розгляду двійкового представлення ключів у машинному слові у вигляді цілого числа, яке можна використовувати в арифметичних обчисленнях. Хешування з'явилося до мов високого рівня - на ранніх комп'ютерах було звичайною справою розглядати якесь значення як рядковий ключ, то як ціле число. У деяких мовах високого рівня важко створювати програми, які залежать від представлення ключів у конкретному комп'ютері, оскільки такі програми, по суті, є машинно-залежними, тому їх важко перенести на інший комп'ютер. Зазвичай хеш-функції залежить від процесу перетворення ключів у цілі числа, у реалізаціях хешування буває важко одночасно забезпечити і машинну незалежність, і ефективність. Як правило, прості цілі ключі або ключі типу з плаваючою точкою можна перетворити за допомогою всього однієї машинної операції, але рядкові ключі та інші типи складових ключів вимагають великих витрат і більшої уваги до ефективності.
Ймовірно, найпростіша ситуація, коли ключами є числа з плаваючою точкою з фіксованого діапазону. Наприклад, якщо ключі - числа, більші 0 та менші 1, їх можна просто помножити на M, округлити результат до меншого цілого числа та отримати адресу в діапазоні між 0 та M - 1; такий приклад показано на рис. 14.1. Якщо ключі більше s і менше t, їх можна масштабувати, віднімаючи s і розділивши на t-s , у результаті вони потраплять у діапазон значень між 0 і 1, та був помножити M і отримати адресу таблиці.
Мал. 14.1.
Для перетворення чисел з плаваючою точкою в діапазоні між 0 і 1 індекси таблиці, розмір якої дорівнює 97, виконується множення цих чисел на 97. У даному прикладі відбулося три колізії: для індексів, рівних 17, 53 і 76. Хеш-значення визначаються старшими розрядами ключа, молодші розряди не відіграють жодної ролі. Однією з цілей розробки хеш-функції є усунення такого дисбалансу, щоб під час обчислення враховувався кожен розряд.
Якщо ключі є w-розрядними цілими числами, їх можна перетворити на числа з плаваючою точкою і розділити на 2 w для отримання чисел з плаваючою точкою в діапазоні між 0 і 1, а потім помножити на M, як у попередньому абзаці. Якщо операції з плаваючою точкою займають багато часу, а числа не настільки великі, щоб призвести до переповнення, цей же результат може бути отриманий за допомогою цілих арифметичних операцій: потрібно помножити ключ на M, а потім виконати зсув вправо на w розрядів для поділу на 2 w (або, якщо множення призводить до переповнення, виконати зсув, а потім множення). Такі методи марні для хешування, якщо ключі не розподілені по діапазону рівномірно, оскільки хеш-значення визначається лише провідними цифрами ключа.
Більш простий і ефективний метод для w-розрядних цілих чисел - один з, мабуть, найбільш часто використовуваних методів хешування - вибір як розміру M таблиці простого числа і обчислення залишку від поділу на M, тобто. h(k) = k mod M для будь-якого цілого ключа k. Така функція називається модульною хеш-функцією. Її дуже просто обчислити (k % M у мові C++), і вона ефективна досягнення рівномірного розподілу значень ключів між значеннями, меншими M. Невеликий приклад показаний на рис. 14.2.
Мал. 14.2.
У трьох правих стовпцях показаний результат хешування 16-розрядних ключів, наведених зліва, за допомогою таких функцій:
v % 97 (ліворуч)
v % 100 (в центрі) та
(int) (a * v) % 100 (праворуч),
де a = .618033. Розміри таблиці цих функцій відповідно дорівнюють 97, 100 і 100. Значення виглядають випадковими (оскільки випадкові ключі). Друга функція (v % 100 ) використовує лише дві крайні праві цифри ключів і тому для невипадкових ключів може бути низька продуктивність.
Модульне хешування можна застосувати і до ключів з плаваючою точкою. Якщо ключі належать невеликому діапазону, можна масштабувати їх у числа діапазону між 0 і 1, 2 w для отримання w-розрядних цілочисельних значень, а потім використовувати модульну хеш-функцію. Інший варіант - просто використовувати як операнд модульної хеш-функції двійкове уявлення ключа (якщо воно доступне).
Модульне хешування застосовується у всіх випадках, коли є доступ до біт, з яких складаються ключі, незалежно від того, чи є вони цілими числами, представленими машинним словом, послідовністю символів, упакованих у машинне слово, або представлені будь-яким іншим можливим варіантом. Послідовність випадкових символів, упакована в машинне слово - не зовсім те саме, що випадкові цілі ключі, оскільки не всі розряди використовуються для кодування. Але обидва ці типи (і будь-який інший тип ключа, закодований так, щоб уміститися в машинному слові) можна змусити виглядати випадковими індексами у невеликій таблиці.
Основна причина вибору як розмір M хеш-таблиці простого числа для модульного хешування показана на рис. 14.3. У цьому прикладі символьних даних з 7-розрядним кодуванням ключ трактується як число з основою 128 - по одній цифрі для кожного символу ключа. Слово now відповідає числу 1816567, яке також може бути записано як
оскільки в ASCII-коді символам n, o і w відповідають числа 1568 = 110 1578 = 111 і 1678 = 119 . Вибір розміру таблиці M = 64 для цього типу ключа невдалий, оскільки додавання до х значень, кратних 64 (або 128), не змінює значення х mod 64 - для будь-якого ключа значенням хеш функції є значення останніх 6 розрядів цього ключа. Безперечно, хороша хеш-функція повинна враховувати всі розряди ключа, особливо для символьних ключів. Аналогічні ситуації можуть бути, коли M містить множник, що є ступенем 2. Найпростіший спосіб уникнути цього - вибрати як M просте число.
Мал. 14.3.
У кожному рядку цієї таблиці наведено: 3-літерне слово, подання цього слова в ASCII-коді як 21-бітове число у вісімковій та десятковій формах та стандартні модульні хеш-функції для розмірів таблиць 64 та 31 (два крайні справа стовпця). Розмір таблиці 64 призводить до небажаних результатів, оскільки для отримання хеш-значення використовуються тільки праві розряди ключа, а літери в словах звичайної мови розподілені нерівномірно. Наприклад, всім словам, що закінчуються на букву у, відповідає хеш-значення 57. І, навпаки, просте значення 31 викликає менше колізій у таблиці більш ніж удвічі меншого розміру.
Модульне хешування дуже просто реалізувати, за винятком того, що розмір таблиці має бути простим числом. Для деяких програм можна задовольнятися невеликим відомим простим числом або пошукати у списку відомих простих чисел таке, що близьке до необхідного розміру таблиці. Наприклад, числа рівні 2 t - 1, є простими при t = 2, 3, 5, 7, 13, 17, 19 та 31(і ні за яких інших значень t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.
Мал. 14.4.
Ця таблиця найбільших простих чисел, менших 2 n для 
може використовуватися для динамічного розподілу хеш-таблиці, коли потрібно, щоб розмір таблиці був простим числом. Для будь-якого даного позитивного значення в охопленому діапазоні цю таблицю можна використовувати для визначення простого числа, яке відрізняється від нього менш ніж у 2 рази.
Інший варіант обробки цілих ключів - об'єднання мультиплікативного і модульного методів: потрібно помножити ключ на константу в діапазоні між 0 і 1, а потім виконати поділ по модулю M. Іншими словами, необхідно використовувати функцію . Між значеннями , M та ефективною основою системи числення ключа існує взаємозв'язок, який теоретично міг би призвести до аномальної поведінки, але якщо використовувати довільне значення a, у реальному додатку навряд чи виникне будь-яка проблема. Часто як a вибирають значення ф = 0,618033... (золотий переріз).
Вивчено безліч інших варіацій на цю тему, зокрема, хеш-функції, які можуть бути реалізовані за допомогою таких ефективних машинних інструкцій, як зсув та виділення маски (див. розділ посилань).
У багатьох додатках, у яких використовуються таблиці символів, ключі є числами і обов'язково є короткими; Найчастіше це алфавітно-цифрові рядки, які можуть бути досить довгими. Ну і як обчислити хеш-функцію для такого слова, як averylongkey?
У 7-розрядному ASCII-коді цьому слову відповідає 84-розрядне число \begin(align*) 97 \cdot 128^(11) &+ 118 \cdot 128^(10) + 101 \cdot 128^(9) + 114 \ cdot 128^(8) + 121 \cdot 128^(7)\\&+ 108 \cdot 128^(6) + 111 \cdot 128^(5) + 110 \cdot 128^(4) + 103 \cdot 128 ^(3)\\ &+ 107 \cdot 128^(2) + 101 \cdot 128^(1) + 121 \cdot 128^(0), \end(align*),
яке занадто велике, щоб з ним можна було виконувати звичайні арифметичні функції у більшості комп'ютерів. А найчастіше потрібно обробляти і набагато довші ключі.
Щоб обчислити модульну хеш-функцію для довгих ключів, вони перетворюються на фрагмент за фрагментом. Можна скористатися арифметичними властивостями функції модуля та використовувати алгоритм Горнера (див. розділ 4.9 "Абстрактні типи даних"). Цей метод ґрунтується на ще одному способі запису чисел, що відповідають ключам. Для прикладу, що розглядається, запишемо наступне вираз: \begin(align*) ((((((((((((97 \cdot 128^(11) &+ 118) \cdot 128^(10) + 101) \cdot 128^( 9) + 114) \cdot 128^(8) + 121) \cdot 128^(7)\\ &+ 108) \cdot 128^(6) + 111) \cdot 128^(5) + 110) \cdot 128^(4) + 103) \cdot 128^(3)\\ &+ 107) \cdot 128^(2) + 101) \cdot 128^(1) + 121. \end(align*)
Тобто десяткове число, що відповідає символьному кодуванню рядка, можна обчислити при перегляді його зліва направо, помножуючи накопичене значення на 128, а потім додаючи кодове значення наступного символу. У разі довгого рядка цей спосіб обчислення врешті-решт призведе до числа, більшого за те, яке взагалі можна представити в комп'ютері. Однак це число і не потрібно, оскільки потрібно лише (невеликий) залишок від його поділу на M. Результат можна отримати, навіть не зберігаючи велике накопичене значення, т.к. у будь-який момент обчислення можна відкинути число, кратне M - при кожному виконанні множення і додавання потрібно зберігати тільки залишок від розподілу по модулю M. Результат буде таким же, як коли б у нас була можливість обчислити довге число, а потім виконувати поділ (див. вправа 14.10). Це спостереження веде до безпосереднього арифметичного способу обчислення модульних хеш-функцій для довгих рядків – див. програму 14.1. У цій програмі використовується ще одне, останнє хитрощі: замість основи 128 у ній використовується просте число 127. Причина цієї зміни розглядається в наступному абзаці.
Існує безліч способів обчислення хеш-функцій приблизно з тими самими витратами, що і для модульного хешування з використанням методу Горнера (одна-дві арифметичні операції для кожного символу в ключі). Для випадкових ключів ці методи практично не відрізняються один від одного, але реальні ключі рідко бувають випадковими. Можливість ціною невеликих витрат надати реальним ключам випадковий вигляд призводить до розгляду рандомізованих алгоритмів хешування, оскільки потрібні хеш-функції, які створюють випадкові індекси таблиці незалежно від розподілу ключів. Рандомізацію організувати неважко, оскільки не потрібно буквально дотримуватися визначення модульного хеширования - потрібно лише, щоб у обчисленні цілого числа, меншого M, використовувалися всі розряди ключа.
Програма 14.1. Хеш-функція для рядкових ключів
M = 96 та a = 128 (вгорі),
M = 97 та a = 128 (у центрі) та
M = 96 та a = 127 (внизу)
Нерівномірний розподіл у першому випадку є результатом нерівномірного вживання літер та збереження нерівномірності через те, що і розмір таблиці, і множник кратні 32. Два інші приклади виглядають випадковими, оскільки розмір таблиці та множник є взаємно простими числами.
У програмі 14.1 показаний один із способів зробити це: використання простої основи замість ступеня 2 і цілого числа, що відповідає ASCII-подання рядка. На рис. 14.5 рис. 14.5 показано, як ця зміна покращує розподіл для типових рядкових ключів. Теоретично хеш-значення, створені програмою 14.1, можуть давати погані результати для розмірів таблиці, які є кратними 127 (хоча на практиці це, швидше за все, буде майже непомітно); до створення рандомизированного алгоритму можна було вибрати значення множника навмання. Ще ефективніший підхід - використання випадкових значень коефіцієнтів у обчисленні та різних випадкових значень для кожної цифри ключа. Такий підхід дає рандомізований алгоритм, який називається універсальним хешуванням (universal hashing).
Теоретично ідеальна універсальна хеш-функція - це функція, для якої ймовірність колізії між двома різними ключами в таблиці розміром M точно дорівнює 1/M. Можна довести, що використання як коефіцієнт а програмі 14.1 не фіксованого довільного значення, а послідовності випадкових різних значень перетворює модульне хешування в універсальну хеш-функцію. Однак витрати на створення нового випадкового числа для кожного символу в ключі зазвичай неприйнятні. На практиці можна досягти компромісу, показаного у програмі 14.1, не зберігаючи масив різних випадкових чисел для кожного символу ключа, а варіюючи коефіцієнти за допомогою генерації простої псевдовипадкової послідовності.
Підіб'ємо підсумки: щоб для реалізації абстрактної таблиці символів використовувати хешування, спочатку необхідно розширити інтерфейс абстрактного типу, включивши в нього операцію hash, яка відображає ключі на цілі негативні числа, менші розміру таблиці M.
