В худшем случае сложность времени положить / получить HashMap

Question

Какова наихудшая временная сложность Hashmap, когда хеш-код его ключей всегда равен.

В моем понимании: так как каждый ключ имеет один и тот же хэш-код, он всегда будет идти к одному и тому же блоку и проходить по нему, проверяя метод equals, поэтому сложность по времени как для get, так и для put должна быть O (n), правильно ли я

Я смотрел на эту HashMap сложность get / put , но она не отвечает на мой вопрос.

Также здесь Wiki Hash Table они утверждают, что сложность времени для худшего случая для вставки равна O (1) , а для get O (n), почему это так?

Answer 1

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

Есть несколько способов смягчения поведения в худшем случае, например, использование самобалансирующегося дерева вместо связанного списка для переполнения сегмента - это уменьшаетнаихудшее поведение O (logn) вместо O (n).

Answer 2

В реализации HashMap в Java 8:

Обработка частых коллизий HashMap с сбалансированными деревьями: в случае коллизий с высоким хешем это повысит производительность в худшем случае с O (n) до O (logn).

С здесь .

Answer 3

в открытом хешировании, у вас будет связанный список для хранения объектов с одинаковым хеш-кодом.так: например, у вас есть хешированная таблица с размером 4. 1) предположим, что вы хотите сохранить объект с hashcode = 0. тогда объект будет отображен в индекс (0 mod 4 =) 0. 2), затем вы снова захотитепоместить другой объект с hashcode = 8. этот объект будет отображен в index (8 mod 4 =) 0, так как мы помним, что индекс 0 уже заполнен нашим первым объектом, поэтому мы должны поместить второй рядом с первым.

[0]=>linkedList{object1, object2}
[1]=>null
[2]=>null
[3]=>null

3) Какие шаги для поиска?Во-первых, вы должны хешировать ключевой объект и предполагать, что его хеш-код равен 8, поэтому вы будете перенаправлены на индекс (8 mod 4 =) 0, тогда, поскольку в одном и том же индексе хранится более одного объекта, мы должны искатьодин за другим все сохраненные объекты в списке, пока вы не найдете соответствующий или до конца списка.поскольку в примере есть 2 объекта, которые хранятся в одном и том же хеш-индексе 0, а искомый объект находится прямо в конце связанного списка, поэтому вам нужно пройтись по всем сохраненным объектам.вот почему это O (n) в худшем случае.худший случай произошел, когда все сохраненные объекты находятся в одном индексе в хеш-таблице.поэтому они будут храниться в связанном списке, в котором нам (возможно) потребуется пройти через все из них, чтобы найти наш искомый объект.

надеюсь, что эта помощь поможет.

Answer 4

При вставке не имеет значения , где в корзине, в которую вы ее положили, так что вы можете просто вставить ее куда угодно, таким образом, вставка равна O (1) .

Lookup - это O (n) , потому что вам придется пройтись по каждому объекту и убедиться, что это тот, который вы искали (как вы заявили).