Direct Addressing
•Прямая адресация эффективна при небольшом m ключей
•Но если ключи 32-bit integers?
–Problem 1: таблица прямой адресации будет хранить 232 записей, больше чем 4 млрд
–Problem 2: Даже если есть такой объем памяти, то необходимо время для инициализации элементов значением NULL
•Solution: помещать ключи в меньший диапазон 0..p-1
Если ключей меньше, чем элементов массива, то в качестве хэш-функции можно использовать деление по модулю, то есть остаток от деления целочисленного ключа Key на размерность массива HashTableSize, то есть: Key % HashTableSize
Данная функция очень проста, хотя и не относится к хорошим. Вообще, можно использовать любую размерность массива, но она должна быть такой, чтобы минимизировать число коллизий. Для этого в качестве размерности лучше использовать простое число. В большинстве случаев подобный выбор вполне удовлетворителен. Для символьной строки ключом может являться остаток от деления, например, суммы кодов символов строки. Например,
A |
n |
t |
o |
n |
o |
v |
∑ = |
65 |
110 |
116 |
111 |
110 |
111 |
118 |
|
HashTableSize = 100 |
|
|
|
741 |
|||
|
|
|
|
||||
Ключ этой символьной строки => 741 % 100 = 7
Хэширование–это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую
строку фиксированной длины.
Такие преобразования также называются
хеш-функциями или функциями свертки, а
их результаты называют хэшем, хэш-кодом,
хэш-таблицей или дайджестом сообщения (message digest).
MD5 (Message Digest 5) - 128-битный алгоритм хеширования.
SHA-1 (Secure Hash Algorithm 1) - алгоритм генерирующий 160-битное хеш-значение.
SHA-2 (Secure Hash Algorithm Version 2) - алгоритмы, использующие хеш-функции SHA-224, SHA-256, SHA-384 и SHA-512.
Хэширование полезно, когда широкий диапазон возможных значений должен быть сохранен в
малом объеме памяти, и нужен способ
быстрого, практически произвольного доступа.
Хэш-таблицы часто применяются в
базах данных,
языковых процессорах типа компиляторов и ассемблеров, где они повышают скорость обработки таблицы идентификаторов.
В качестве использования хэширования в повседневной жизни можно привести примеры:
распределение книг в библиотеке по
тематическим каталогам,
упорядочивание в словарях по первым буквам
слов,
шифрование специальностей в вузах и т.д.
Hash-функции
Hash -функции
Функция которая связывает ключевые значения с индексами массива Входные записи всегда имеют уникальный ключ
Hash-функция связывает ключ с индексом массива Записи хранятся в виде data[hash(key)]
В идеале, каждый уникальный ключ имеет
уникальное значение hash(key)
Прямая адресация использует hash-функцию которая ничего не делает
int directAddressHash(int studentId) { return studentId;
}
Hash Functions
• В целом это сложная проблема.
|
|
U |
0 |
|
|
|
|
|
|
|
|
(universe of keys) |
|
|
|
||
k1 |
|
|
h(k1) |
|
|
|
|
h(k4) |
|
|
|
|
k4 |
|
|
|
|
K |
k5 |
|
|
|
|
|
|
|
|
||
(actual |
|
h(kh(k) )= h(k |
) |
||
|
|
||||
keys) |
|
|
2 2 |
5 |
|
|
|
|
|
|
|
|
k2 |
k3 |
h(k3) |
|
|
|
|
|
|
||
p - 1
Хеширование данных
Hash-таблицы
Student
IDs (Keys)
Hash
2
0 Function
4
|
Data |
Objects |
|
|
Student |
hash(4) |
0 |
3.2 John Doe |
|
|
|
2 |
2.6 |
Jane Doe |
hash(0) |
ID |
GPA |
Name |
|
|
|
|
hash(2) |
|
|
|
|
4 |
3.7 |
Some Guy |
Hash-таблицы
Hash-функции
Как можно избежать больших размеров массива, чтобы хранить все возможные ключи?
Простое решение: использовать модульную арифметику
Размер вспомогательного массива больше не зависит от количество уникальных ключей
int modularHash(int studentId) {
return studentId % ARRAY_SIZE;
}
Вспомним прямую адресацию:
int directAddressHash(int studentId) {
return studentId;
}
Хеширование применяется для сравнения данных:
если у двух массивов хеш-коды разные,
массивы гарантированно различаются;
если одинаковые — массивы, скорее всего, одинаковы.
В общем случае однозначного соответствия
между исходными данными и хеш-кодом нет в силу того, что количество
значений хеш-функций меньше, чем вариантов входного массива.