Асимптотическая сложность реализаций Java Map (HashMap, LinkedHashMap, TreeMap)

Question

Я пытаюсь справиться с асимптотической сложностью HashMap, LinkedHashMap и TreeMap. На разных сайтах и ​​статьях пишут, что в среднем get = O(1), а в худшем - O(n). (если все ключи добавить в одну корзину).

Но я читаю книгу Bruce Eckel thinking in java и есть пример сравнения

Если вы посмотрите на эти данные, то они исчезнут O(n)

Я полностью сбит с толку. Кто-нибудь может объяснить асимтотическую сложность реализаций Map - HashMap, LinkedHashMap и TreeMap, по крайней мере для get и put? (может быть, есть хорошая статья, где все ясно и собрано?)

EDIT

Больше всего интересует метод put. С каких пор resize() возникает определенный размер аналогично ArrayList.

Answer 1

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

Изменение размера действительно происходит в некоторых случаях, но это даже не близко к тому, как ArrayList делает это. ArrayList только увеличит внутренний массив, всегда ; HashMap удвоит внутренние сегменты до определенной точки ( смотрите, когда именно здесь ), после чего преобразует определенный интервал в Tree, что ускоряет поиск - это было добавлено в Java-8.