Как этот целочисленный хэш генерируется функцией GetHashCode()? Это случайное значение, которое не является уникальным?
В строке это переопределяется, чтобы убедиться, что для конкретной строки существует только один хэш-код. Как это сделать?
Как ускорить поиск определенного ключа в хеш-таблице с помощью хеш-кода?
Каковы преимущества использования хеш-кода по сравнению с использованием индекса непосредственно в коллекции (например, в массивах)?
Кто-нибудь может помочь?
По сути, хэш-функции используют некоторую общую функцию для обработки данных и создания отпечатка пальца (и здесь целого числа) для этих данных. В отличие от индекса, этот отпечаток зависит ТОЛЬКО от данных и не должен иметь предсказуемого порядка, основанного на данных. Любое изменение одного бита данных также должно значительно изменить отпечаток пальца.
Обратите внимание, что нигде это не гарантирует, что разные данные не дадут один и тот же хэш. На самом деле совсем наоборот: такое случается очень часто и называется столкновением. Но с целым числом вероятность составляет примерно 1 из 4 миллиардов против этого (1 из 2^32). Если происходит столкновение, вы просто сравниваете фактический объект, который вы хешируете, чтобы увидеть, совпадают ли они.
Затем этот отпечаток можно использовать в качестве индекса для массива (или списка массивов) сохраненных значений. Поскольку отпечаток пальца зависит только от данных, вы можете вычислить хэш для чего-то и просто проверить элемент массива для этого хеш-значения, чтобы увидеть, было ли оно уже сохранено. В противном случае вам придется пройти через весь массив, проверяя, соответствует ли он элементу.
Вы также можете ОЧЕНЬ быстро создавать ассоциативные массивы, используя 2 массива: один со значениями ключа (индексированный хэшем), а второй со значениями, сопоставленными с этими ключами. Если вы используете хэш, вам просто нужно знать хэш ключа, чтобы найти соответствующее значение для ключа. Это намного быстрее, чем выполнять двоичный поиск в отсортированном списке ключей или сканирование всего массива для поиска совпадающих ключей.
Существует МНОЖЕСТВО способов генерации хэша, и все они имеют различные достоинства, но лишь немногие из них просты. Я предлагаю обратиться к странице википедии по хеш-функциям для получения дополнительной информации.
Хэш-код — это индекс, а хэш-таблица на самом низком уровне — это массив. Но для заданного значения ключа мы определяем индекс в хэш-таблице по-разному, чтобы обеспечить гораздо более быстрое извлечение данных.
Пример: у вас есть 1000 слов и их определений. Вы хотите сохранить их, чтобы вы могли получить определение слова очень, очень быстро — быстрее, чем бинарный поиск, который вам пришлось бы делать с массивом.
Итак, вы создаете хэш-таблицу. Вы начинаете с массива, значительно превышающего 1000 записей, скажем, 5000 (чем больше, тем эффективнее время).
Вы будете использовать свою таблицу следующим образом: вы берете слово для поиска и конвертируете его в число от 0 до 4999. Вы выбираете алгоритм для этого; это алгоритм хеширования. Но вы, несомненно, могли бы написать что-то, что было бы очень быстро.
Затем вы используете преобразованное число в качестве индекса в свой массив из 5000 элементов и вставляете/находите свое определение по этому индексу. Нет никакого поиска: вы создали указатель непосредственно из слова для поиска.
Все операции, которые я описал, выполняются с постоянным временем; ни один из них не занимает больше времени, когда мы увеличиваем количество записей. Нам просто нужно убедиться, что в хеше достаточно места, чтобы свести к минимуму вероятность «коллизий», то есть вероятность того, что два разных слова будут преобразованы в один и тот же целочисленный индекс. Поскольку это может случиться с любым алгоритмом хеширования, нам нужно добавить проверки, чтобы увидеть, есть ли коллизия, и сделать что-то особенное (если «hello» и «world» оба хэшируют до 1234, а «hello» уже есть в таблице, что что мы будем делать с «миром»? Проще всего поместить его в 1235 и настроить нашу логику поиска, чтобы учесть эту возможность.)
Редактировать: после повторного прочтения вашего сообщения: алгоритм хеширования определенно не является случайным, он должен быть детерминированным. Индекс, сгенерированный для «привет» в моем примере, должен быть равен 1234 каждый раз; это единственный способ поиска может работать.
HashCode — это псевдоуникальный ключ. Мы хотели бы иметь действительно уникальный ключ, но это невозможно. Мы соглашаемся на быструю и безопасную (без исключений) функцию.
HashTable использует HashCode для первоначального поиска за время O(1). Любая схема индексации требует O(log(n)) времени. Но с неэффективной функцией HashCode обработка коллизий может сделать HashTable намного медленнее.
В .NET есть реализация по умолчанию для GetHashCode, но типы могут переопределить ее.
System.String переопределяет GetHashCode(), потому что он переопределяет Equals(), а затем GetHashCode должен оставаться согласованным.
Отвечая на каждый из ваших вопросов напрямую:
Как этот целочисленный хэш генерируется функцией GetHashCode()? Это случайное значение, которое не является уникальным?
Целочисленный хэш генерируется любым методом, подходящим для объекта. Метод генерации не является случайным, но должен следовать согласованным правилам, гарантирующим, что хэш, сгенерированный для одного конкретного объекта, будет равен хешу, сгенерированному для эквивалентного объекта. Например, хэш-функция для целого числа должна просто возвращать это целое число.
В строке это переопределяется, чтобы убедиться, что для конкретной строки существует только один хэш-код. Как это сделать?
Есть много способов сделать это. Вот пример, о котором я думаю на месте:
int hash = 0;
for(int i = 0; i < theString.Length; ++i)
{
hash ^= theString[i];
}
Это допустимый алгоритм хэширования, поскольку одна и та же последовательность символов всегда будет давать одно и то же число хеш-функции. Это не хороший хэш-алгоритм (это сильное преуменьшение), потому что многие строки будут давать один и тот же хэш. Действительный хеш-алгоритм не обязательно должен гарантировать уникальность. Хороший хеш-алгоритм делает вероятность того, что два разных объекта будут выдавать одно и то же число, крайне маловероятной.
Как ускорить поиск определенного ключа в хеш-таблице с помощью хеш-кода? Каковы преимущества использования хеш-кода по сравнению с использованием индекса непосредственно в коллекции (например, в массивах)?
Хэш-код обычно используется в хеш-таблицах. Хеш-таблица — это массив, но каждая запись в массиве — это «корзина» элементов, а не один элемент. Если у вас есть объект и вы хотите знать, к какой корзине он принадлежит, рассчитайте
hash_value MOD hash_table_size.
Затем вам просто нужно сравнить объект с каждым элементом в ведре. Таким образом, поиск в хеш-таблице, скорее всего, будет иметь время поиска O (1), в отличие от O (log (N)) для отсортированного списка или O (N) для несортированного списка.
