Saltar al contenido

¿Resumen de Big-O para implementaciones de Java Collections Framework?

Luego de investigar en diferentes repositorios y sitios webs de internet al concluir nos encontramos con la respuesta que te enseñamos pronto.

Solución:

El libro Java Generics and Collections tiene esta información (páginas: 188, 211, 222, 240).

Lista de implementaciones:

                      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)

Establecer implementaciones:

                      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)

Implementaciones de mapas:

                      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)

Implementaciones de cola:

                      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)

La parte inferior del javadoc para el paquete java.util contiene algunos buenos enlaces:

  • Collections Overview tiene una buena tabla de resumen.
  • Esquema anotado enumera todas las implementaciones en una página.

Este sitio web es bastante bueno pero no específico para Java: http://bigochatsheet.com/
Aquí hay una imagen en caso de que este enlace no funcione

Los Javadocs de Sun para cada clase de colección generalmente le dirán exactamente lo que desea. Hash Map, por ejemplo:

Esta implementación proporciona rendimiento en tiempo constante para las operaciones básicas (obtener y poner), asumiendo que la función hash dispersa los elementos adecuadamente entre los cubos. La iteración sobre vistas de colección requiere tiempo proporcional a la “capacidad” de la instancia de HashMap (el número de cubos) más su tamaño (el número de key-mapeos de valores).

ÁrbolMapa:

Esta implementación proporciona costo de tiempo de log(n) garantizado para las operaciones containsKey, get, put y remove.

ÁrbolConjunto:

Esta implementación proporciona costo de tiempo log(n) garantizado para las operaciones básicas (agregar, quitar y contener).

(énfasis mío)

Comentarios y valoraciones de la guía

Acuérdate de que tienes la capacidad de reseñar si te ayudó.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *