Резюме для Big-O для реализации Java Collections Framework?

Question

Возможно, я скоро научусь «крушению курса Java». Хотя, вероятно, можно предположить, что члены аудитории будут знать нотацию Big-O, вероятно, небезопасно предположить, что они будут знать, что такое порядок различных операций над различными реализациями коллекции.

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

Кто-нибудь есть любые указатели?

Answer 1

Этот сайт очень хороший, но не относится к Java: http://bigocheatsheet.com/

Answer 2

Javadocs от Sun для каждого класса коллекции обычно скажет вам, что именно вы хотите. HashMap, например:

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

TreeMap:

Эта реализация обеспечивает гарантировано журнал (п) стоимость для ContainsKey, получить, поставить и удалить операции.

TreeSet:

Эта реализация обеспечивает стоимость гарантировано журнал (п) времени для основных операций (добавление, удаление и содержит).

(курсив мой)

Answer 3

Книга Java Generics and Collections имеет эту информацию (стр: 188, 211, 222, 240).

реализация Списка:

     get add contains next remove(0) iterator.remove 
ArrayList    O(1) O(1) O(n)  O(1) O(n)  O(n) 
LinkedList   O(n) O(1) O(n)  O(1) O(1)  O(1) 
CopyOnWrite-ArrayList O(1) O(n) O(n)  O(1) O(n)  O(n) 

Набора реализации:

     add  contains next  notes 
HashSet    O(1)  O(1)  O(h/n) h is the table capacity 
LinkedHashSet   O(1)  O(1)  O(1) 
CopyOnWriteArraySet O(n)  O(n)  O(1) 
EnumSet    O(1)  O(1)  O(1) 
TreeSet    O(log n) O(log n) O(log n) 
ConcurrentSkipListSet O(log n) O(log n) O(1) 

реализации Карта:

     get  containsKey next  Notes 
HashMap    O(1)  O(1)  O(h/n) h is the table capacity 
LinkedHashMap   O(1)  O(1)  O(1) 
IdentityHashMap  O(1)  O(1)  O(h/n) h is the table capacity 
EnumMap    O(1)  O(1)  O(1) 
TreeMap    O(log n) O(log n) O(log n) 
ConcurrentHashMap  O(1)  O(1)  O(h/n) h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n) O(1) 

очередь реализации:

     offer peek poll  size 
PriorityQueue   O(log n) O(1) O(log n) O(1) 
ConcurrentLinkedQueue O(1)  O(1) O(1)  O(n) 
ArrayBlockingQueue O(1)  O(1) O(1)  O(1) 
LinkedBlockingQueue O(1)  O(1) O(1)  O(1) 
PriorityBlockingQueue O(log n) O(1) O(log n) O(1) 
DelayQueue   O(log n) O(1) O(log n) O(1) 
LinkedList   O(1)  O(1) O(1)  O(1) 
ArrayDeque   O(1)  O(1) O(1)  O(1) 
LinkedBlockingDeque O(1)  O(1) O(1)  O(1) 

Дно Javadoc для java.util пакета содержит несколько хороших ссылок:

• Collections Overview имеет приятную сводную таблицу.
• Annotated Outline перечисляет все реализации на одной странице.

Answer 4

Парень выше дал сравнение для HashMap/HashSet против TreeMap/TreeSet.

Я буду говорить о ArrayList против LinkedList:

ArrayList:

• O (1) get()
• амортизируется O (1) add()
• если вставить или удалить элемент в в середине, используя ListIterator.add() или Iterator.remove(), это будет O (n) для смещения всех следующих элементов:

LinkedList:

• O (п) get()
• O (1) add()
• если вставить или удалить элемент в середине использованием ListIterator.add() или Iterator.remove(), будет O (1)