Sumário Big-O para implementações do Java Collections Framework?

Eu posso estar ensinando em breve um “curso rápido de Java”. Embora seja provavelmente seguro assumir que os membros do público saberão a notação Big-O, provavelmente não é seguro assumir que eles saberão qual é a ordem das várias operações em várias implementações de coleta.

Eu poderia reservar um tempo para gerar uma matriz de resumo, mas se já estiver no domínio público em algum lugar, eu certamente gostaria de reutilizá-la (com o devido crédito, é claro).

Alguém tem alguma ponteira?

Este site é muito bom, mas não específico para Java: http://bigocheatsheet.com/ Aqui está uma imagem caso este link não funcione

O livro Java Generics and Collections contém essas informações (páginas: 188, 211, 222, 240).

Listar implementações:

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) 

Definir implementações:

  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) 

Implementações de mapa:

  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) 

Implementações de fila:

  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) 

A parte inferior do javadoc para o pacote java.util contém alguns links bons:

  • A Visão geral das collections tem uma boa tabela de resumo.
  • Contorno anotado lista todas as implementações em uma página.

Os Javadocs da Sun para cada class de coleção geralmente lhe dirão exatamente o que você deseja. HashMap , por exemplo:

Essa implementação fornece desempenho em tempo constante para as operações básicas (get e put), assumindo que a function hash dispersa os elementos corretamente entre os buckets. A iteração sobre visualizações de coleção requer tempo proporcional à “capacidade” da instância do HashMap (o número de depósitos) mais seu tamanho (o número de mapeamentos de valor-chave).

TreeMap :

Essa implementação fornece um custo de log (n) garantido para as operações containsKey, get, put e remove.

TreeSet :

Essa implementação fornece um custo de log (n) garantido para as operações básicas (adicionar, remover e conter).

(ênfase minha)

O cara acima deu a comparação para HashMap / HashSet vs. TreeMap / TreeSet.

Eu vou falar sobre ArrayList vs. LinkedList:

ArrayList:

  • O (1) get()
  • amortizado O (1) add()
  • se você inserir ou excluir um elemento no meio usando ListIterator.add() ou Iterator.remove() , será O (n) para deslocar todos os elementos a seguir

LinkedList:

  • O (n) get()
  • O (1) add()
  • se você inserir ou excluir um elemento no meio usando ListIterator.add() ou Iterator.remove() , será O (1)