Функция хеширования любого живого объекта (хеш-таблица)?

Question

Не уверен, имеет ли смысл снова открыть мою предыдущую ветку по хешированию URL . Тем не менее, мне все еще интересно знать, как эта работа под прикрытием.

Предположение: у нас есть хеш-таблица с n (где n 1).

Вопрос: Может ли кто-нибудь объяснить мне, как CLR отображает ключ к хеш-коду, когда мы ищем (извлекаем) какой-либо элемент (если используются разные хеш-функции)? Как CLR отслеживает (если это) хеш-функцию любого живого объекта (хеш-таблицы)?

Заранее спасибо.

Answer 1

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

Итак, представьте себе хеш-таблицу, которая вмещает 1024 элемента, и вы собираетесь вставить две клавиши: K1 и K2.

K1.GetHashCode() возвращает 1,023. K2.GetHashCode() возвращает 65 535

Затем код делит возвращаемый ключ на размер хеш-таблицы и принимает остаток. Таким образом, оба ключа соответствуют позиции 1023 в хэш-таблице.

K1 добавлено в таблицу. Когда приходит время добавить K2, возникает коллизия. Таким образом, код прибегает ко второй хэш-функции. Эта вторая хеш-функция, вероятно, представляет собой «битовый микшер» (часто последний этап вычисления хеш-кода), который рандомизирует биты в возвращаемом ключе. Концептуально код будет выглядеть примерно так:

int hashCode = K2.GetHashCode();
int slot = hashCode % 1024;
if (table[slot] != null)
{
    int secondHashCode = BitMixer(hashCode);
    slot = secondHashCode % 1024;
}

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

Answer 2

Хеш-код не уникально идентифицирует объект.Он просто используется для быстрого помещения этого объекта в ведро.Элементы в одном сегменте могут, но не обязательно, быть равными, но элементы в разных сегментах должны быть неравными.

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

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

---

Для типов с семантикой значений вы переопределяете как Equals, так и GetHashCode последовательно использовать поля, определяющие равенство.

Answer 3

Каждый объект реализует функцию GetHashCode() и функцию Equals(). Реализации по умолчанию для них связаны со ссылками на объекты. Например, a.Equals(b) вернет то же самое, что и object.ReferenceEquals(a,b). Это будет означать, что если две ссылки на объекты равны, то есть их хэш-коды.

В некоторых случаях вам нужно предоставить другую семантику для функции Equals(). В этих случаях вы должны соблюдать договор, если a.Equals(b), то a.GetHashCode() == b.GetHashCode().

Используется множество функций хэширования, каждая из которых имеет свои преимущества и недостатки. Здесь есть полезное объяснение . Фактическая используемая функция - это не то, о чем вам следует беспокоиться, главное, чтобы время поиска в 1015 * среднем o (1) времени в Hashtable было (в идеале) гарантирующим, что объекты, которые будут вставлены, имеют GetHashCode() результат максимально приближен к равномерно распределенному.

Answer 4

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

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