МІНІСТЕРСТВО ОСВІТИ І НАУКИ РФ
Ангарську ДЕРЖАВНА ТЕХНІЧНА АКАДАМІЯ
КІБЕРНЕТИЧНИЙ ФАКУЛЬТЕТ
КАФЕДРА ОБЧИСЛЮВАЛЬНІ МАШИНИ І КОМПЛЕКСИ
РЕФЕРАТ
З дисципліни" Структури та алгоритми
Тема: Особливості процесу хешування
Виконав:
студент гр. ІВТз - 11-1
Лужбін В.Г.
Перевірив:
доцент Кулакова І.М.
р. Ангарськ, 2013р.
Зміст
Введення
Хешування
Хеш-функції
Хеш-таблиці
Метод ланцюжків
Метод відкритої адресації
Контрольна сума
Список використаної літератури
Введення
З хешуванням стикаються чи не на кожному кроці: при роботі з браузером (список Web-посилань), текстовим редактором і перекладачем (словник), мовами скриптів (Perl, Python, PHP та ін), компілятором (таблиця символів). За словами Брайана Керніган, це «один з найбільших винаходів інформатики». Заглядаючи в адресну книгу, енциклопедію, алфавітний покажчик, ми навіть не замислюємося, що впорядкування за алфавітом є не чим іншим, як хешуванням.
Хешування застосовується для швидкого пошуку в структурах даних і в криптографії, а також для перевірки на наявність помилок.
Хешування це процес отримання унікального (частіше цифрового) ідентифікатора для об'єкта.
Хешування
Хешування ( hash - змішування, перемішування, розмішування) - перетворення вхідного масиву даних в короткий число фіксованої довжини (яке називається хешем <# «justify"> Це найпростіший приклад і тут же зрозуміло, що будуть колізії це коли одне і те ж слово дасть одне і теж число. Наприклад, слова будинку і мода дадуть одну і ту ж цифру. Тому звідси вихід або ускладнювати алгоритм для гарантії неповторності а значить важливо і розташування літер із слові в плані порядку або при збігу перевіряти вже саму рядок безпосередньо для гарантії того, що слова однакові. У будь-якому випадку прискорення виконання значно унаслідок того що порівнюється все за один раз.
Примітка
Раніше були пропозиції назвати метод хешування по русски - окрошка, а також російськомовним еквівалентом терміну хеширования - розстановка, але не один з них не прижився.
Хеш-функції
Нехай у нас є безліч X якихось об'єктів. Текстових файлів, чисел, пляшок пива. Ще є безліч чисел Y (N)={0, 1, 2,., N - 1}. Маємо функцію f (x)=k, де x - об'єкт з X, k - з Y (N). Така функція буде зватися хеш-функцією (можна кликати її також функцією хешування). Вона по суті розбиває X на N непересічних підмножин, це розбиття має назву хеширование.
Приклад: X - цілі невід'ємні числа, f (x)=x mod N (шукаємо залишок від ділення). Ця хеш-функція на...
