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).

Хеш-таблица

Хэш-функции, используемые в хэш-таблицах для вычисления индекса в массив слотов. Хэш-таблица - это структура данных для реализации словарей (структура ключевых значений). Хорошие реализованные хеш-таблицы имеют O (1) время для следующих операций: вставка, поиск и удаление данных по ключу. Более одного ключа могут иметь хэш в том же слоте. Существует два способа разрешения столкновения:

1. Цепочка: связанный список используется для хранения элементов с одинаковым значением хэша в слоте

2. Открытая адресация: нулевой или один элемент сохраняется в каждом слоте

Следующие методы используются для вычисления последовательностей зондов, необходимых для открытой адресации

Где i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) - вспомогательные хэш-функции, c1, c2 - положительные вспомогательные константы.

Примеры

Пусть x ∈ U{1, 1000}, h = x mod m . Следующая таблица показывает значения хэша в случае не простых и простых. Полужирный текст указывает те же значения хэша.

связи

• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Введение в алгоритмы.

• Обзор таблиц Hash

• Wolfram MathWorld - Функция хэша

Хэш коды для обычных типов в 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));
}

Рекомендации

• GitHub .Net Core CLR