Где я могу найти показатели производительности (обозначение big-Oh) для различных контейнеров Java?

Question

Принимая решение об использовании определенного контейнера (List / Set / Map), я хотел бы учитывать метрики производительности (нотация big-Oh) таких операций, как вставка, удаление, получение и т. Д. Это позволяет мне выбрать лучший контейнер для моих нужд.

Документы API всегда указывают синхронизированные / несинхронизированные, но не другие показатели производительности.

Есть ли где-нибудь справочная таблица, к которой я могу обратиться?

Answer 1

Generics и коллекции Java содержит такие данные для всех реализаций коллекции.

Answer 2

Если вы посмотрите на конкретную реализацию одного из интерфейсов, он даст вам информацию о производительности.Например, ArrayList можно прочитать следующим образом:

Операции size, isEmpty, get, set, iterator и listIterator выполняются в постоянное время.Операция добавления выполняется за амортизированное постоянное время, то есть для добавления n элементов требуется время O (n).Все остальные операции выполняются за линейное время (грубо говоря).Постоянный коэффициент является низким по сравнению с таковым для реализации LinkedList.