Пространственная сложность структур данных Java

Question

Я искал множество веб-сайтов, содержащих информацию о пространственной сложности структур данных Java. Я ищу специально для космической сложности HashMap, ArrayList, Stack и LinkedList. Один сайт, который я обнаружил, приблизился и имел информацию только о Stack и LinkedList: http://bigocheatsheet.com/, но у него был только худший случай. Кто-нибудь знает о каких-либо других источниках, которые имеют информацию о сложности пространства HashMap или ArrayList, предпочтительно в среднем случае и в худшем случае?

Answer 1

Все они O(N) при использовании в нормальных условиях. (Итак, все стандартные структуры сбора данных, я думаю ...)

Конечно, это не говорит вам о некоторых важных фактах о том, сколько пространства эти структуры данных будут использовать на практике. Например:

• ArrayList или HashMap с использованием пространства не прямо пропорционален размером списка. Оба имеют стратегию «вдвое больше, чем когда бывают полные» для некоторых или всех их использования в пространстве.

• В лучшем случае, ArrayList использует меньше места для каждого элемента, чем LinkedList и LinkedList использует меньше места для каждого элемента, чем HashMap.

И так далее.

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

• ArrayList не удаляет пространство при удалении элементов.

• С помощью HashMap пространство, занимаемое цепями, может расти и уменьшаться, но массив хэшей только растет.

Answer 2

Если вы проверите код для этих классов, вы увидите, что они внутренне представлены в виде массивов. Следовательно, сложность операций должна быть такой же, как и на массивах.