Mapa/ArrayList: cuál es más rápido para buscar un elemento

Question

Tengo un conjunto de datos gigantesco que debo almacenar en una colección y necesito encontrar si hay duplicados allí o no.

El tamaño de los datos podría ser más de 1 millón. Sé que puedo almacenar más elementos en ArrayList comapre a Map.

Mis preguntas son:

1. es la búsqueda de una clave Map más rápido que buscar en la ordenada ArrayList?
2. está buscando La clave en HashMap es más rápida que TreeMap?
3. Solo en términos de espacio requerido para almacenar elementos n, ¿cuál sería más eficiente entre una implementación TreeMap y HashMap?

Answer 1

1) Sí. La búsqueda de un ArrayList es O (n) en promedio. El rendimiento de las búsquedas clave en un Mapa depende de la implementación específica. Puede escribir una implementación de Map que sea O (n) o peor si realmente lo desea, pero todas las implementaciones en la biblioteca estándar son más rápidas que O (n).

2) Sí. HashMap es O (1) en promedio para búsquedas de claves simples. TreeMap es O (log (n)).

Class HashMap<K,V>

Esta aplicación proporciona un rendimiento constante de tiempo para las operaciones básicas (get y put), asumiendo la función hash se dispersa adecuadamente los elementos entre los cubos.

Class TreeMap<K,V>

Esta aplicación proporciona registro garantizado (n) Coste tiempo para la containsKey, obtener, de poner y quitar operaciones. Los algoritmos son adaptaciones de aquellos en Cormen, Leiserson y Rivest's Introduction to Algorithms.

3) Los requisitos de espacio serán O (n) en ambos casos. Me gustaría SupongoTreeMap requiere un poco más de espacio, pero solo por un factor constante.

Answer 2

1. Depende del tipo de Map que esté utilizando.
2. A HashMap tiene una búsqueda promedio de constante de tiempo (O (1)), mientras que 's un TreeMap tiempo medio de búsqueda se basa en la profundidad del árbol (O (log (n))), por lo a HashMap es más rápido.
3. La diferencia es probablemente discutible. Ambas estructuras de datos requieren cierta cantidad de sobrecarga constante en la complejidad del espacio por diseño (ambas exhiben O (n) complejidad de espacio).