Как изменяется производительность между хэш-таблицей из 1 миллиона элементов и хеш-таблицей из 100 элементов

Question

Я знаю, что могут быть проблемы с производительностью хеш-таблицы, но как хеш-таблица с 1 миллионом элементов может быть быстрее, чем хеш-таблица с 100 элементами?

Answer 1

Все зависит от количества коллизий: если в хэш-таблице с 1 млн. Элементов вообще нет коллизий, это будет намного быстрее, чем с 100 и 100 коллизиями.

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

Answer 2

Это зависит от эффективности используемого алгоритма хеширования.

Если на маленькой карте много столкновений, а на большей - нет, то большая будет быстрее.

Прочитайте HashMap javadocs, чтобы узнать о начальной емкости и коэффициент загрузки и прочитать о хэш-кодах (начиная с Object.hashCode() ). ( Hashtable - древняя реликвия, не используйте ее .)