8
¿Alguien sabe la respuesta a esta pregunta?HashMap con ~ 100 millones de claves, ¿aún tiempo constante?
A
Respuesta
14
Sí. Para buscar un mapa hash con 100 millones de elementos agregados, haga esto:
1) Calcule el hash del objeto que está buscando.
2) Encuentra ese cubo
3) Busca a través de ese cubo para el artículo.
(1) es independiente del tamaño del mapa hash o la cantidad de elementos que contiene.
(2) es O (1), asumiendo un hashmap estándar implementado como una matriz de listas enlazadas.
(3) toma una cantidad de tiempo relacionada con la cantidad de elementos en el depósito, que debe ser aproximadamente (número de elementos agregados al hash)/(número de segmentos). Esta parte comenzará en O (1), pero aumentará muy lentamente a medida que el número de elementos comience a exceder en gran medida la cantidad de cubetas.
Para casi cualquier propósito, los mapas hash se pueden considerar O (1) tanto para la inserción como para la recuperación, incluso con conjuntos de datos muy grandes, siempre que comience con un número suficientemente grande de cubos.
7
Sí, aún tiempo constante (amortizado).
+0
lo que significa amortizado – SuperString
+1
En teoría ... La paginación de memoria podría ser un problema. Poco probable pero posible. –
+1
Amortizado significa que algunas inserciones individuales pueden tomar más tiempo que otras, pero el tiempo promedio permanece constante. –
Cuestiones relacionadas
- 1. ¿Arreglo eficiente de Python con 100 millones de ceros?
- 2. Obtener claves de HashMap en Java
- 3. Cambio de claves HashMap durante la iteración
- 4. ¿Cómo puedo tener un HashMap con claves únicas en java?
- 5. ¿Por qué mi HashMap permite duplicar claves?
- 6. Mejor enfoque NoSQL para manejar más de 100 millones de registros
- 7. ¿Cómo cargar 100 millones de registros en MongoDB con Scala para pruebas de rendimiento?
- 8. Tiempo amortizado constante
- 9. ¿Inicializar HashMap con una variedad de elementos?
- 10. ¿Es HashMap seguro para subprocesos para diferentes claves?
- 11. campo de conjunto de claves en HashMap es nulo
- 12. Cómo ordenar (millones/millones/...) enteros?
- 13. Clojure rseq en tiempo constante?
- 14. Obteniendo constante constante de recuperación de tiempo constante con listas inmutables en un contexto de programación funcional
- 15. hash de tiempo constante para cadenas?
- 16. Java: ¿Buscar en claves HashMap basadas en expresiones regulares?
- 17. ¿Por qué puedo usar cadenas como claves en un HashMap?
- 18. Análisis de grafos sociales. 60 GB y 100 millones de nodos
- 19. ¿Las claves privadas exportadas en GPG aún están encriptadas?
- 20. Crear un hashmap con una doble clave
- 21. Obtener las claves con los valores más altos de un hashmap?
- 22. Java XStream con HashMap
- 23. Treap con claves implícitas
- 24. Django Tabla con millones de filas
- 25. vector con tamaño constante
- 26. Complejidad del tiempo de los métodos de HashMap
- 27. Cocoa: ¿diccionario con claves enum?
- 28. Java Collection con 2 claves
- 29. Asignación de Hashmap a Hashmap
- 30. ¿Cómo imprimir todas las claves y valores de HashMap en Android?
+1 buena respuesta, el punto (3) es importante – Paolo
y siempre que el hash esté distribuido uniformemente para su conjunto de datos. –
¿hay alguna manera de aumentar el número de cubos en C++ para que cada cubo solo tenga 1 elemento? – SuperString