Вопросы о сложности времени HashMap

Question

Это не вопросы кода, я просто пытаюсь понять концепцию хэш-карт и сложности времени.

Ну, я думаю, я знаю, как работает hashMaps / sets et c. работать, и я думаю, что я понимаю, почему HashMaps.get имеет постоянное время, но когда у нас очень большая хэш-карта, показатели, где хранятся значения, должны перекрываться. Когда 2 хеш-кода преобразуются в один и тот же индекс, они сохраняются в LinkList с этим индексом, верно?

Не может ли быть так, что все элементы были сохранены в одном индексе в виде списка ссылок. Теперь HashMap.get не должен запускаться в худшем случае в O (n).

Answer 1

Да, сложность времени в наихудшем случае для HashMap - это O (n), где n - это количество элементов, хранящихся в одном сегменте. Худший случай будет, когда все элементы n HashMap сохраняются в одном сегменте.

Однако это можно улучшить, если для каждого из блоков реализован двоичный поиск. В этом случае временная сложность наихудшего случая будет O(log(n)), так как binary search tree используется для хранения элементов вместо doubly linked list.