колізій необхідно мінімізувати. p align="justify"> Хороша хеш-функція повинна задовольняти двом вимогам:
В· її обчислення повинно виконуватися дуже швидко;
В· вона повинна мінімізувати кількість колізій.
Отже, перша властивість хорошої хеш-функції залежить від комп'ютера, а друге - від даних. Якби всі дані були випадковими, то хеш-функції були б дуже прості (кілька бітів ключа, наприклад). Однак на практиці випадкові дані зустрічаються вкрай рідко, і доводиться створювати функцію, яка залежала б від усього ключа. p align="justify"> Теоретично неможливо визначити хеш-функцію так, щоб вона створювала випадкові дані з реальних невипадкових файлів. Однак на практиці реально створити досить хорошу імітацію за допомогою простих арифметичних дій. Більш того, часто можна використовувати особливості даних для створення хеш-функцій з мінімальним числом колізій (меншим, ніж при істинно випадкових даних). p align="justify"> Можливо, одним з найбільш очевидних і простих способів хешування є метод середини квадрата, коли ключ зводиться в квадрат і береться кілька цифр в середині. Тут і далі передбачається, що ключ спочатку приводиться до цілого числа, для здійснення з ним арифметичних операцій. Однак такий спосіб добре працює до моменту, коли немає великої кількості нулів зліва чи справа. p align="justify"> хешування згортка програмний колізія
РОЗДІЛ 2. ПРОЕКТНИЙ РОЗДІЛ
2.1 Принцип побудови хеш-функцій
Численні тести показали хорошу роботу двох основних типів хешування, один з яких заснований на розподілі, а інший на множенні. Втім, це не єдині методи, які існують, більше того, вони не завжди є оптимальними. p align="justify"> У міру зростання бази даних можна
В· користуватися початкової хеш-функцією, втрачаючи продуктивність через зростання колізій;
В· вибрати хеш-функцію В«із запасомВ», що спричинить невиправдані втрати дискового простору;
В· періодично міняти функцію, перераховувати всі адреси. Це забирає дуже багато ресурсів і виводить з ладу базу на деякий час.
Існує техніка, що дозволяє динамічно змінювати розмір хеш-структури. Це - динамічне хешування. Хеш-функція генерує так званий псевдоключ ( pseudokey ), який використовується лише частково для доступу до елементу. Іншими словами, генерується досить довга бітова послідовність, яка повинна бути достатня для адресації всіх потенційно можливих елементів. У той час, як при статичному хешуванні потрібна була б дуже велика таблиця (яка зазвичай зберігається в оперативній пам'яті для прискорення доступу), тут розмір використа...
