MasterZiv
> Дословно:
> 1) Данные помещаются в хэш-таблицу.
> 2) Значение хэша служит индексом в этой таблице.
> 3) Таблицы упорядочена по возрастанию индекса.
>
> i и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.

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

Я извиняюсь, но...

У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование хэш-функций и хэш-таблиц.
По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться хэш-функциями, а индексы в БД - хэш-таблицами.
Соответствеенно, и сама хэш-функция известна, и доступ к ее результату тоже имеется.
И у Вас не совсем правильный вывод о том, что значение хэш-функции "меняется со временем": на самом деле хеширование выполняется с конкатенацией метки времени и оригинальным значением - потому и создается такое впечатление...

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

MasterZiv
> У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование
> хэш-функций и хэш-таблиц.
> По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться
> хэш-функциями, а индексы в БД - хэш-таблицами.

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

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

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

Извините, но это - БРЕД!

Я допускаю, что некоторые библиотеки могут позволять выбор разных хэш-функции для реализации хэш-таблиц.
Но вот то, что в ран-тайме в течение всего периода жизни экземпяра хэш-таблицы вне зависимости от степени ее роста хэш-функция НЕ меняется - это, как бы, аксиома... Любая попытка замены хэширующей функции "на лету" приводит к эскалации коллизий и некорректности функционирования ЛЮБОГО алгоритма, работающего с этой хэш-таблицей.
MasterZiv> При необходимости часто делать выборки из больших таблиц по точному совпадению в
> полях больших размеров (например, текстовых идентификаторов), для ускорения
> поиска и уменьшения места, занимаемого индексами физической таблицы, можно
> использовать индекс по значению хэш-функции для этого конкретного поля.
> Соотвественно, в условии выборки используется уже не значение поля, а значение
> хэш-функции от кроиерия выборки по этому полю. Естественно, что не следует
> забывать про возможные коллизии при этом.

Большего идиотизма трудно придумать.
-- можно просто не использовать длинные текстовые поля в индексах.

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

Вы неверно понимаете сжатие ключей индексов, которые могут выполнять некоторые промышленные СУБД.
Исключения из ключа индекса незначащей части не дает существеной экономии места, когда ключ заполнен "в-среднем" процентов на 90-95 для каждой записи... При длине ключа байт хотя бы на 100... С учетом "сжатия"...