algorithm
Хэш-функции
Поиск…
Введение в хэш-функции
Хэш-функция h()
- это произвольная функция, которая отображает данные x ∈ X
произвольного размера в значение y ∈ Y
фиксированного размера: y = h(x)
. Хорошие хэш-функции имеют следующие ограничения:
хеш-функции ведут себя одинаково
хэш-функции детерминированы.
h(x)
всегда должно возвращать одно и то же значение для заданногоx
быстрый расчет (имеет время выполнения O (1))
В общем случае размер хеш-функции меньше размера входных данных: |y| < |x|
, Хэш-функции не обратимы, иначе говоря, это может быть столкновение: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)
. X
может быть конечным или бесконечным множеством, а Y
- конечным множеством.
Функции хэши используются во многих частях информатики, например, в разработке программного обеспечения, криптографии, базах данных, сетях, машинах и т. Д. Существует множество различных типов хеш-функций с различными свойствами домена.
Часто hash представляет собой целочисленное значение. Существуют специальные методы программирования языков для вычисления хешей. Например, в методе C#
GetHashCode()
для всех типов возвращается значение Int32
(32-битное целочисленное число). В Java
каждый класс предоставляет метод hashCode()
который возвращает int
. Каждый тип данных имеет собственные или определенные пользователем реализации.
Хэш-методы
Существует несколько подходов к детерминированной хэш-функции. Без ограничения общности, пусть x ∈ X = {z ∈ ℤ: z ≥ 0}
- положительные целые числа. Часто m
является простым (не слишком близко к точной мощности 2).
метод | Хэш-функция |
---|---|
Метод разделения | h(x) = x mod m |
Метод умножения | h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1} |
Хеш-таблица
Хэш-функции, используемые в хэш-таблицах для вычисления индекса в массив слотов. Хэш-таблица - это структура данных для реализации словарей (структура ключевых значений). Хорошие реализованные хеш-таблицы имеют O (1) время для следующих операций: вставка, поиск и удаление данных по ключу. Более одного ключа могут иметь хэш в том же слоте. Существует два способа разрешения столкновения:
Цепочка: связанный список используется для хранения элементов с одинаковым значением хэша в слоте
Открытая адресация: нулевой или один элемент сохраняется в каждом слоте
Следующие методы используются для вычисления последовательностей зондов, необходимых для открытой адресации
метод | формула |
---|---|
Линейное зондирование | h(x, i) = (h'(x) + i) mod m |
Квадратичное зондирование | h(x, i) = (h'(x) + c1*i + c2*i^2) mod m |
Двойной хэш | h(x, i) = (h1(x) + i*h2(x)) mod m |
Где i ∈ {0, 1, ..., m-1}
, h'(x), h1(x), h2(x)
- вспомогательные хэш-функции, c1, c2
- положительные вспомогательные константы.
Примеры
Пусть x ∈ U{1, 1000}, h = x mod m
. Следующая таблица показывает значения хэша в случае не простых и простых. Полужирный текст указывает те же значения хэша.
Икс | m = 100 (не простое) | m = 101 (простой) |
---|---|---|
+723 | 23 | 16 |
103 | 3 | 2 |
+738 | 38 | 31 |
292 | 92 | 90 |
61 | 61 | 61 |
87 | 87 | 87 |
995 | 95 | 86 |
549 | 49 | 44 |
+991 | 91 | 82 |
757 | 57 | 50 |
920 | 20 | 11 |
626 | 26 | 20 |
557 | 57 | 52 |
831 | 31 | 23 |
619 | 19 | 13 |
связи
Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Введение в алгоритмы.
Хэш коды для обычных типов в C #
Хэш-коды, созданные методом GetHashCode()
для встроенных и общих типов C # из пространства имен System
, показаны ниже.
логический
1, если значение истинно, 0 в противном случае.
Байт , UInt16 , Int32 , UInt32 , Single
Значение (если необходимо, заносится в Int32).
SByte
((int)m_value ^ (int)m_value << 8);
голец
(int)m_value ^ ((int)m_value << 16);
Int16
((int)((ushort)m_value) ^ (((int)m_value) << 16));
Int64 , Double
Xor между нижним и верхним 32 битами 64-разрядного номера
(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));
UInt64 , DateTime , TimeSpan
((int)m_value) ^ (int)(m_value >> 32);
Десятичный
((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];
объект
RuntimeHelpers.GetHashCode(this);
В реализации по умолчанию используется индекс блока синхронизации .
строка
Вычисление кода хэш-кода зависит от типа платформы (Win32 или Win64), особенности использования хеширования рандомизированных строк, режима отладки / выпуска. В случае платформы Win64:
int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
hash1 = ((hash1 << 5) + hash1) ^ c;
c = s[1];
if (c == 0)
break;
hash2 = ((hash2 << 5) + hash2) ^ c;
s += 2;
}
return hash1 + (hash2 * 1566083941);
Тип ценности
Первое нестатическое поле ищет и получает его hashcode. Если тип не имеет нестатических полей, возвращается хэш-код типа. Хэш-код статического члена нельзя принять, потому что если этот элемент имеет тот же тип, что и исходный тип, вычисление заканчивается в бесконечном цикле.
Nullable <T>
return hasValue ? value.GetHashCode() : 0;
массив
int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}