Интересует каким образом реализован hash table. Непонятно следующее: хеш функция от любых значений ключа должна выдвавать целые значение в строго фиксированном дипазоне напрмер от 0..n? Массив размером n для хранения значений выделается сразу или по мере заполнения таблицы?

Здравствуйте, sergey_benkov, Вы писали:

_>Интересует каким образом реализован hash table. Непонятно следующее: хеш функция от любых значений ключа должна выдвавать целые значение в строго фиксированном дипазоне напрмер от 0..n?

hash(x) % n позволит иметь диапазон от 0 до n при любой хеш-функции. Пользовательская хеш-функция обычно выдаёт результаты на всём диапазоне значений возвращаемого типа (например от -2^31 до 2^31 — 1 в Java).

> Массив размером n для хранения значений выделается сразу или по мере заполнения таблицы?

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

Здравствуйте, sergey_benkov, Вы писали:

_>Интересует каким образом реализован hash table. Непонятно следующее: хеш функция от любых значений ключа должна выдвавать целые значение в строго фиксированном дипазоне напрмер от 0..n? Массив размером n для хранения значений выделается сразу или по мере заполнения таблицы?
простейший вариант, который я использую в наколенной реализации — нужно сразу выделять массив размера n, где n минимум в два раза будет больше максимального кол-ва добавляемых элементов.

Здравствуйте, vsb, Вы писали:

_>>Интересует каким образом реализован hash table. Непонятно следующее: хеш функция от любых значений ключа должна выдвавать целые значение в строго фиксированном дипазоне напрмер от 0..n?

vsb>hash(x) % n позволит иметь диапазон от 0 до n при любой хеш-функции.

Кстати, поэтому внутри реализации обычно выбирают n простым числом.
Вот пример, из недавнего обсуждения:
http://rsdn.ru/forum/dotnet/3956346.aspx

Автор: andy1618
Дата: 13.09.10