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

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

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

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

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