Почему мы используем хэш-код в HashTable вместо индекса?

Question

• Как этот целочисленный хэш генерируется функцией GetHashCode ()? Это случайное значение, которое не является уникальным?

• В строке переопределяется, чтобы убедиться, что существует только один хэш-код для конкретной строки. Как это сделать?

• Как ускоряется поиск определенного ключа в хеш-таблице с использованием хеш-кода?

• В чем преимущества использования хеш-кода по сравнению с использованием индекса непосредственно в коллекции (как в массивах)?

Может кто-нибудь помочь?

Answer 1

В основном, хеш-функции используют некоторую универсальную функцию для переваривания данных и генерирования отпечатка пальца (и целого числа здесь) для этих данных. В отличие от индекса, этот отпечаток пальца зависит ТОЛЬКО от данных и должен быть свободен от любого предсказуемого порядка, основанного на данных. Любое изменение в одном бите данных также должно значительно изменить отпечаток пальца.

Обратите внимание, что нигде это не гарантирует, что разные данные не дадут одинаковый хэш. На самом деле, совсем наоборот: это случается очень часто и называется столкновением. Но с целым числом вероятность составляет примерно 1 на 4 миллиарда против этого (1 на 2 ^ 32). Если происходит столкновение, вы просто сравниваете реальный объект, который хэшируете, чтобы увидеть, совпадают ли они.

Этот отпечаток может быть использован в качестве индекса для массива (или массива) сохраненных значений. Поскольку отпечаток пальца зависит только от данных, вы можете вычислить хеш для чего-то и просто проверить элемент массива для этого значения хеша, чтобы увидеть, сохранено ли оно уже. В противном случае вам придется пройти весь массив, проверяя, соответствует ли он элементу.

Вы также можете ОЧЕНЬ быстро создавать ассоциативные массивы, используя 2 массива: один со значениями Key (индексируется по хешу), а второй со значениями, сопоставленными с этими ключами. Если вы используете хеш, вам просто нужно знать хеш ключа, чтобы найти соответствующее значение для ключа. Это гораздо быстрее, чем выполнять бинарный поиск в отсортированном списке ключей или сканировать весь массив, чтобы найти подходящие ключи.

Есть много способов генерировать хеш, и все они имеют различные достоинства, но немногие из них просты. Я предлагаю обратиться к странице википедии о хэш-функциях для получения дополнительной информации.

Answer 2

Хеш-код - это индекс, а хеш-таблица на самом низком уровне - это массив. Но для данного значения ключа мы по-разному определяем индекс в хеш-таблице, чтобы сделать поиск данных намного быстрее.

Пример: у вас есть 1000 слов и их определения. Вы хотите сохранить их так, чтобы вы могли получить определение слова очень, очень быстро - быстрее, чем бинарный поиск, что вы должны сделать с массивом.

Итак, вы создаете хеш-таблицу. Вы начинаете с массива, существенно превышающего 1000 записей, скажем, 5000 (чем больше, тем эффективнее время).

То, как вы будете использовать свою таблицу, заключается в том, что вы берете слово для поиска и конвертируете его в число от 0 до 4999. Вы выбираете алгоритм для этого; это алгоритм хеширования. Но вы, несомненно, могли бы написать что-нибудь очень быстрое.

Затем вы используете преобразованное число в качестве индекса в массиве из 5000 элементов и вставляете / находите свое определение по этому индексу. Поиска вообще нет: вы создали индекс непосредственно из поискового слова.

Все операции, которые я описал, имеют постоянное время; Ни один из них не занимает больше времени, когда мы увеличиваем количество записей. Нам просто нужно убедиться, что в хэше достаточно места, чтобы минимизировать вероятность «коллизий», то есть вероятность того, что два разных слова будут преобразованы в один и тот же целочисленный индекс. Поскольку это может произойти с любым алгоритмом хеширования, нам нужно добавить проверки, чтобы увидеть, есть ли столкновение, и сделать что-то особенное (если «hello» и «world» и hash to 1,234, и «hello» уже есть в таблице, что будем ли мы делать с «миром»? Простейшим является поместить его в 1235 и настроить нашу логику поиска, чтобы учесть эту возможность.)

Редактировать: после перечитывания вашего поста: алгоритм хеширования определенно не случайный, он должен быть детерминированным. Индекс, сгенерированный для "hello" в моем примере, должен быть 1234 каждый раз; только так может работать поиск.

Answer 3

HashCode - это псевдо-уникальный ключ. Мы хотели бы иметь действительно уникальный ключ, но это невозможно. Мы соглашаемся на быструю и безопасную (без исключений) функцию.

A HashTable использует HashCode для первоначального поиска за время O (1). Любая схема индексации требует времени O (log (n)). Но с неэффективной функцией HashCode обработка коллизий может сделать HashTable намного медленнее.

В .NET есть реализация по умолчанию для GetHashCode, но типы могут переопределять это.

System.String переопределяет GetHashCode (), потому что переопределяет Equals (), а затем GetHashCode должен оставаться согласованным.

Answer 4

Отвечая на каждый из ваших вопросов напрямую:

Как генерируется этот целочисленный хэш функция GetHashCode ()? Это случайное значение, которое не является уникальным?

Целочисленный хэш генерируется любым подходящим для объекта методом. Метод генерации не является случайным, но должен следовать согласованным правилам, гарантируя, что хеш, сгенерированный для одного конкретного объекта, будет равен хешу, сгенерированному для эквивалентного объекта. Например, хеш-функция для целого числа будет просто возвращать это целое число.

В строке перезаписывается уверен, что существует только один хеш код для конкретной строки. Как сделать это?

Есть много способов сделать это. Вот пример, о котором я думаю на месте:

int hash = 0;
for(int i = 0; i < theString.Length; ++i)
{
    hash ^= theString[i];
}

Это действительный алгоритм хеширования, потому что одна и та же последовательность символов всегда будет давать один и тот же хеш-номер. Это не хороший алгоритм хеширования (крайнее занижение), потому что многие строки будут выдавать один и тот же хеш. Действительный алгоритм хеширования не должен гарантировать уникальность. Алгоритм хеширования good даст возможность двум разным объектам создать одно и то же число крайне маловероятно.

Как ускоряется поиск определенного ключа в хеш-таблице с использованием хеш-кода? Каковы преимущества использования хеш-кода по сравнению с использованием индекса непосредственно в коллекции (как в массивах)?

Хеш-код обычно используется в хеш-таблицах. Хеш-таблица - это массив, но каждая запись в массиве - это «набор» элементов, а не только один элемент. Если у вас есть объект, и вы хотите знать, к какому ведру он принадлежит, рассчитайте

 hash_value MOD hash_table_size. 

Тогда вам просто нужно сравнить объект с каждым предметом в корзине. Таким образом, поиск в хэш-таблице, скорее всего, будет иметь время поиска O (1), а не O (log (N)) для отсортированного списка или O (N) для несортированного списка.