Я изучаю хеш-таблицы, хеш-карты и т. Д. Я только что реализовал хеш-таблицу на C с операциями: insert(HTable, key)
, delete(HTable, key)
, initialize(HTable)
и search(HTable, key)
.
Я хотел бы кое-что спросить. Поскольку в (правильной) хеш-таблице вычисленные хешированные индексы могут быть очень большими, не означает ли это, что потребляемое пространство будет похоже на INT_MAX
(что, конечно, по-прежнему O (n)) или больше? Я имею в виду, учитывая элемент ввода, который мы хотим сохранить в хеш-таблице (т.е. вставить его в), функция insert () вызовет хеш-функцию, которая затем вычислит хешированный индекс для элемента, который нужно ввести. Таким образом, она будет использовать хеш-функция, чтобы найти этот индекс.
Когда мы используем хеш-функцию для работы с элементом, хешированный индекс может стать очень большим. При правильной, например, криптографической хеш-функции, этот индекс может стать огромным (они используют простые числа с 300 цифрами - криптография с открытым ключом Диффи Хеллмана и т. Д.), Верно? Я знаю, что в обычных хэш-функциях (таких как тривиальные, которые используют новички для изучения) мы применяем операцию модификации, чтобы элемент соответствовал границам хеш-таблицы, но, возможно, при этом мы ограничим потенциал хеш-функции?
Итак, чтобы однозначно сопоставить элемент с хеш-таблицей, мы должны использовать ОГРОМНУЮ хеш-таблицу. Как реализованы эти криптографические хеш-таблицы? Они должны быть в полной безопасности, не так ли? Даже тег Stack Overflow в «криптографической хеш-функции» говорит, что крайне маловероятно найти два входа, которые будут отображаться на один и тот же элемент (поэтому вероятность коллизий мала). Разве для этого не потребовалось бы, чтобы ОГРОМНЫЙ массив хранился в памяти (или на диске)? Следовательно, потребление памяти будет огромным.
Конечно, временная сложность не проблема. Мы просто видим начальный адрес хэш-таблицы / массива, добавляем его с индексом и просто переходим в это место в памяти, чтобы получить значение (O (1) - принцип поиска по хеш-таблице).
Я где-то не прав? Что-то мне не хватает? Надеюсь, я ясно выразился. В заключение я хотел бы получить подтверждение по этому поводу. Требуется ли для хорошей хэш-функции огромный массив (хеш-таблица) и, как таковой, очень большой объем памяти для правильной реализации? Оправдано ли столько места, или я чего-то не понимаю? Спасибо.
String.hashCode()
в Java. - person Patrick M   schedule 09.01.2018