[java] HashMap get / put сложность



Answers

Я не уверен, что hashcode по умолчанию является адресом - я читал исходный код OpenJDK для генерации hashcode некоторое время назад, и я помню, что это было что-то более сложное. По-видимому, это не то, что гарантирует хорошее распределение. Тем не менее, это в некоторой степени спорным, поскольку несколько классов, которые вы хотите использовать в качестве ключей в HashMap использовать хэш-код по умолчанию - они поставляют свои собственные реализации, которые должны быть хорошо.

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

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

Question

Мы привыкли говорить, что операциями HashMap get/put являются O (1). Однако это зависит от реализации хэша. Хэш-объект по умолчанию - это фактически внутренний адрес в куче JVM. Мы уверены, что достаточно хорошо утверждать, что get/put - O (1)?

Еще одна проблема - доступная память. Как я понимаю из javadocs, load factor HashMap должен быть 0,75. Что делать, если у нас недостаточно памяти в JVM, а load factor превышает лимит?

Таким образом, похоже, что O (1) не гарантируется. Это имеет смысл или я что-то упускаю?




Операция HashMap является зависимым фактором реализации hashCode. Для идеального сценария можно сказать, что хорошая хэш-реализация, которая предоставляет уникальный хеш-код для каждого объекта (отсутствие хеш-коллизии), тогда лучшим, худшим и средним сценарием будет O (1). Рассмотрим сценарий, когда плохая реализация hashCode всегда возвращает 1 или такой хеш, который имеет хеш-коллизию. В этом случае временной сложностью будет O (n).

Теперь, перейдя ко второй части вопроса о памяти, тогда да, ограничение памяти будет зависеть от JVM.






Links