Приемлемые типы для использования в качестве ключей в HashTable

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

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

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

Лучшие хеш-ключи - это те, которые

1. имеют хорошие (например, при низких коллизиях ) хеши (см. Object.GetHashCode для .NET, Object.hashcode для Java)
2. Быстро сравнивайте (при наличии хеш-коллизий).

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

Большинство строковых реализаций, хотя они могут отображаться как типы ссылок в управляемых средах, их реализация обычно неизменяема. type.

Что делает хеш-функция, так это то, что она отображает очень большое количество состояний на меньшее количество состояний.

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

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

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

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

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

Если бы вы использовали сложный тип в качестве ключа, то:

• Для реализации хеш-таблицы было бы сложно сгруппировать элементы в сегменты для быстрого поиска; как он решит, как сгруппировать диапазон хэшей в ведро?
• Для выбора сегмента хеш-таблице может потребоваться точное знание типа.
• Существует риск свойств объекта изменяется, в результате чего элементы попадают в неправильные корзины. Хэши должны быть неизменяемыми.

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