Не лише програмісти, а й прості користувачі сучасних технологій так чи інак стикаються з хешуванням практично щодня. Адже воно використовується під час роботи з масивами даних, а також для захисту інформації та важливого контенту.
Хешування — це функція створення вихідних даних фіксованого розміру, з початкових даних змінного розміру, яка використовує при цьому різні математичні формули та алгоритми, також звані хеш-функціями.
При хешуванні відбувається процес зіставлення ключів (вихідні дані) та значень у хеш-таблиці (вихідні дані — індекс або хеш). Це дозволяє отримувати швидший доступ до елементів порівняно, наприклад, з використанням простого масиву даних.
Основна мета хешування — вирішити завдання швидкого пошуку елемента в наборі (масиві) даних. Наприклад, якщо ми маємо словник з мільйону українських слів, і ми хочемо знайти певний термін, ми можемо використовувати хешування, щоб цей процес був більш ефективним. Навпаки, неефективно перевіряти кожен елемент із мільйона, доки знайдемо збіг. Гешування дозволяє скоротити час такого пошуку.
Щодня обсяг даних в Інтернеті збільшується у багато разів і постійно ускладнюється процес зберігання цих даних. Якщо ви робите невеликий сайт, підсумковий обсяг даних може бути не таким вже й великим, але навіть його необхідно зберігати, мати до нього доступ і ефективно обробляти. Однією з найпоширеніших структур даних, що використовується для цієї мети, є структура даних Масив (Array).
Тепер, увага питання: якщо є Масив, навіщо нам потрібна нова структура даних? Відповідь на це питання криється у слові «ефективність». Хоча збереження даних у масиві займає невеликий час, пошук у ньому потребує більше часу. Цей час здається невеликим, але якщо ми маємо справу з великим набором даних, він значно зростає і робить використання типу даних Array (масив) неефективним.
Тут у гру і вступає хешування, як тип зберігання та обробки даних. Воно дозволяє легко зберігати дані за фіксований час, а також витягувати дані за фіксований час.
Іншим важливим застосуванням хешування є криптографія та шифрування, — для забезпечення цілісності, захищеності та конфіденційності даних. Останнім часом гешування також активно використовується при майнінгу та блокчейні криптовалют (наприклад, біткоїнів).
Є 3 базові компоненти, які визначають хешування:
ключ-значення
) у масиві. Тут кожному значенню даних присвоюється власний, і в ідеалі, унікальний індекс. Цей індекс також називають іншими різними іменами: хеш-індекс, хеш-сума, геш-значення, або просто хеш чи геш.
Припустимо, у нас є масив даних із рядків, в даному прикладі, з пар літер української абетки:
{"АБ", "ВГ", "ҐД"}
і нам потрібно зберегти його у таблиці, використовуючи хешування.
Наша основна мета — мати можливість швидко знаходити або оновлювати значення, що зберігаються в таблиці, і не турбуватися про порядок їх розміщення. Давайте уявимо, що цей набір рядків виступає в якості ключів. Як ми можемо зберегти ці дані з використанням хешування?
Крок №1: Ми знаємо, що хеш-функція (якась математична формула) використовується для розрахунку індексу (геш-значення) у таблиці даних.
Крок №2: Назначимо найпростіший індекс кожній літері абетки, наприклад, так:
"А" = 1, "Б" = 2, "В" = 3 ... і т.д.
Крок №3: Тепер ми можемо отримати числове значення (індекс) кожного рядка шляхом підсумовування всіх значень (найпростіша хеш-функція):
"АБ" = 1 + 2 = 3, "ВГ" = 3 + 4 = 7, "ҐД" = 5 + 6 = 11 … і так далі
Крок №4: Тепер припустимо, що ми маємо таблицю з 6 колонок для зберігання цих рядків (за кількістю літер). Найпростіша хеш-функція, що використовується в прикладі, являє собою суму символів у таблиці ключів. Ми можемо обчислити розташування рядка в масиві, використовуючи ділення за модулем на 6 (за кількістю колонок). Ділення за модулем — це залишок від ділення вихідних даних на максимальну кількість підсумкових даних. Наприклад, у PHP це можна отримати так:
<?php /* $a % $b */echo (3 % 6); // 3 echo (7 % 6); // 1 echo (11 % 6); // 5 … ?>
Крок №5: Отже, в хеш-таблиці ми збережемо наступні індекси:
"АБ" — 3 за модулем 6 = 3, "ВГ" — 7 за модулем 6 = 1, і "ҐД" — 11 за модулем 6 = 5.
В наведеному вище прикладі ми використовували найпростішу хеш-функцію (на простому математичному алгоритмі), щоб обчислити місце розташування заданого рядка в таблиці і швидко знайти значення, що зберігається в цьому індексі.
Як ви можете бачити, ідея хешування виявляється чудовим способом зберігання інформації (розбиваючи дані на пари ключ-значення
) у таблиці.
Існує безліч хеш-функцій, що використовують цифрові, літерні або літерно-цифрові ключі. Вище в прикладі ми використовували примітивну хеш-функцію, яка базується на присвоєнні простого індексу, та алгоритму ділення за модулем (ділення націло). На практиці використовують геш-функції, які повинні швидко обчислюватися, а також мати потенційно незначну кількість “колізій” (конфлікт однакових хешів). Колізії неминучі, якщо хешування генерує невеликі числа для великої кількості ключів, оскільки існує велика ймовірність того, що два ключі можуть дати те саме значення. Також хеш-функція, що використовується, повинна мати низький коефіцієнт завантаження (ефективний розподіл елементів у таблиці, що відповідає за розміром кількості цих елементів).
До інших видів хеш-функцій можна віднести (від простих до складніших):
На ранніх етапах становлення Інтернету для хешування використовувався алгоритм MD5 (Підпис Повідомлення 5 — Message Digest 5) — досить простий 128-бітовий алгоритм хешування. MD5-хеш складається із 32 цифр.
Приклад використання в PHP:
<?php
echo md5("пароль");
// Результат: e242f36f4f95f12966da8fa2efd59992
Потім з’явився SHA-1 (Алгоритм безпечного хешування 1 — Secure Hash Algorithm 1). Тут використовується згенерований 160-бітовий хеш, що складається із 40 цифр.
Приклад використання в PHP:
<?php
echo sha1("пароль");
// Результат: 5670b4358ae287fe8e74c2ff6f6293f905409077
З 2011 року алгоритми MD5 і SHA-1 вважаються небезпечними, через слабкість перед атаками з використанням «колізій».
На сьогоднішній день найбільш безпечними вважаються алгоритми хешування 2-ї версії сімейства SHA-2, а саме SHA-256 та SHA-512.
Приклади використання в PHP:
<?php echo hash("sha256", "пароль"); // Результат: 2dbc574daca52689a24fb60e835f8c19a36400830df7350859dd32d1abaaec5d echo hash("sha512", "пароль"); // Результат: f1d4b1ee047ec217264547763efb27c17c069eabc9f23124a223a1a859ca5cefe112a3e3cefe1cdc4331ecb70f9982f16dc67e250142476adae6ce9bc44f3a08 ?>
Наочний приклад:
<?php echo hash("sha256", "пароль"); // Результат: 2dbc574daca52689a24fb60e835f8c19a36400830df7350859dd32d1abaaec5d echo hash("sha256", "Пароль"); // Результат: cb1a2074b3a027ffa7d7d9c54682c3835fffc7f6d620d8a38532f075cc2f17a0 // У другому прикладі ми замінили одну літеру і отримали зовсім інший результат! ?>
null
) значень
В сьогоднішньому теоретичному, і трохи практичному, уроці ми розглянули основні принципи хешу та хешування. Ця тема не лише дуже важлива, але й дуже складна для розуміння. Особливо для програмістів-початківців. Тому метою даного уроку було не тільки наочно, але й зрозуміло розповісти про хешування та супутні моменти.
Відчували раніше себе трохи «загубленим» у сфері хешування? Сподіваємося, що сьогоднішній урок додав вам впевненості та розуміння цієї теми. Дякуємо за увагу!
Сьогоднішній огляд присвячений людям, для яких важливе питання конфіденційності в Інтернеті, та хто цінує свої…
Вперше про бренд Pro Plan почули у 1986 році, коли він став частиною американської компанії…
Страх покарання гірше самого покарання (Покарання — завжди щось конкретне, і воно все ж краще,…
Якщо ви плануєте розмістити веб-сайт в мережі Інтернет, дуже важливо знайти для нього швидкий і…
Навчання за кордоном вже давно асоціюється з якісною освітою, новими можливостями та безліччю перспектив. Але…
Вибір майстра для ремонту та перетяжки меблів – завдання, яке потребує вдумливого підходу. Адже від…