Читая документацию по MSDN для метода Object.GetHashCode, я натолкнулся на такие фразы, как хэш-функция должна обеспечивать случайное или полезное распределение в хеш-таблице. Что означает это распределение в отношении хеш-функции или хеш-таблицы?
Что означает распределение хеш-функции?
06.04.2012
- en.wikipedia.org/wiki/Hash_table 06.04.2012
- Примерно: хеш-значения должны быть распределены случайным образом по их домену без видимой закономерности (например, минимальное скопление и максимальное распространение при визуальном просмотре). Многие реализации хеширования будут повторно хешировать хеш, чтобы уменьшить вероятность появления сгустков при помещении в корзины. 06.04.2012
Ответы:
1
Хеш-функция производит 32-битное целое число с целью «уравновешивания» хеш-таблицы. Предположим, в вашей таблице есть сотня «корзин», и вы помещаете элементы в таблицу в корзину на основе двух нижних десятичных цифр хеш-функции.
Теперь предположим, что хеш-функция всегда выдает числа, кратные сотне. Каждый элемент будет помещен в одну и ту же корзину, и хеш-таблица будет несбалансированной. Это была бы плохая хеш-функция.
Хороший алгоритм хеширования обеспечивает примерно равномерное распределение независимо от того, сколько у вас сегментов и независимо от того, как вы извлекаете номер сегмента из хеша.
06.04.2012
2
Чтобы хеш-таблицы работали с максимальной эффективностью, хеш-значения должны быть как можно более уникальными, чтобы предотвратить коллизии. Например, давайте рассмотрим чрезвычайно наивную хеш-функцию: допустим, ваши объекты - это имя и фамилия, а в качестве хеш-значения вы выбираете инициалы. Таким образом, значение хеш-функции Джинджер Роджерс - GR, а значение хеш-функции Фреда Астера - FA. Пока все хорошо, но что произойдет, если Фрэнк Аллен предоставит хеш-значение FA? Теперь у вас есть конфликт между Фредом Астером и Фрэнком Алленом, и реализация хеш-таблицы должна обрабатывать это как особый случай, что снижает эффективность.
Лучшие хеш-функции берут входное пространство (Фред Астер) и производят случайное значение (в идеале), уникальное для входного пространства. Пока размер вашего хэша меньше размера ваших данных, невозможно полностью избежать коллизий, но их следует минимизировать, тщательно выбирая алгоритм хеширования.
Как указывает Эрик ниже, хеш-алгоритмы для балансировки хеш-таблиц должны быть очень быстрыми, поэтому вам нужно найти баланс между скоростью и коллизиями. Вы можете изучить криптографические хэш-алгоритмы, такие как SHA-1 (http://en.wikipedia.org/wiki/SHA-1), чтобы понять сложности создания уникальных хешей, но хеш-алгоритмы для балансировки хеш-таблиц должны быть как можно более быстрыми. .
06.04.2012
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально
Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение
Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования
Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv)
Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..