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

Question

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

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

У кого-нибудь есть указатели?

Answer 1

Этот веб-сайт довольно хороший, но не относится к Java: http://bigocheatsheet.com/

Answer 2

Книга 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 содержит несколько хороших ссылок:

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

Answer 3

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

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

TreeMap:

Эта реализация обеспечивает гарантированные затраты времени log(n) для операций containsKey, get, put и remove.

TreeSet:

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

(акцент мой)

Answer 4

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

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

ArrayList:

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

LinkedList:

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