ти являють собою дві класичні стратегії вирішення колізій -
відкриту адресацію з лінійним перебором і
метод ланцюжків .
Метод ланцюжків
Технологія зчеплення елементів полягає в тому, що елементи множини , яким відповідає одне і те ж хеш-значення, зв'язуються в ланцюжок-список. У позиції номер i зберігається покажчик на голову списку тих елементів, у яких хеш-значення ключа одно i; якщо таких елементів у множині немає, в позиції i записаний NULL. На рис. <# «Justify">
Рис. 2 . Дозвіл колізій за допомогою ланцюжків
Кожна комірка масиву є покажчиком на зв'язний список (ланцюжок) пар ключ-значення, відповідають одному і тому ж хеш-значенням ключа. Колізії просто призводять до того, що з'являються ланцюжка довжиною більше одного елемента.
Операції пошуку або видалення даних вимагають перегляду всіх елементів відповідної йому ланцюжка, щоб знайти в ній елемент з заданим ключем. Для додавання даних потрібно додати елемент в кінець або початок відповідного списку, і, у випадку якщо коефіцієнт заповнення стане занадто великий, збільшити розмір масиву і перебудувати таблицю.
Метод відкритої адресації
На відміну від хеширования з ланцюжками, при відкритої адресації ніяких списків немає, а всі записи зберігаються в самій хеш-таблиці. Кожна комірка таблиці містить або елемент динамічного безлічі, або NULL.
хеширование колізія цифровий ідентифікатор
У цьому випадку, якщо осередок з обчисленим індексом зайнята, то можна просто переглядати такі записи таблиці по порядку до тих пір, поки не буде знайдений ключ K або порожня позиція в таблиці. Для обчислення кроку можна також застосувати формулу, яка і визначить спосіб зміни кроку. На рис .3 дозвіл колізій здійснюється методом відкритої адресації. Два значення претендують на ключ 002, для одного з них знаходиться перше вільне (ще незайняте) місце в таблиці.
Рис. 3. Дозвіл колізій за допомогою відкритої адресації
Безпечне зберігання паролів за допомогою хеш-функцій
Нехай є у нас соціальна мережа, база даних або інше, де може бути вхід за логіном і паролем. Щоб система перевірила, чи правильно введений пароль, потрібно десь зберігати паролі. Зберігати пароль у відкритому вигляді не рекомендується.
Причини:
Будь-який файл можна відкрити блокнотом і переглянути.
Якщо зберігати в реєстрі, то також можна простежити звернення програми до реєстру і виявити те місце де зберігаються паролі.
скомпілювати програму (exe файл) можна розкрити дізассемблегом (наприклад ida pro) і відстежити звернення до місцяпорівняння пароля (наприклад soft-ice)
Таким чином якщо пароль зберігається у відкритому вигляді його легко можна виявити.
Щоб зберігати пароль в зашифрованому вигляді можна вдатися до хешування - використовувати хеш-функції з довгими хеш-зн...
