Пространственная сложность структур данных 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

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