ejemplo - hashmap java example

Embedded Hash Map Big(O)?

Question

Si incrusta un mapa hash como ese:

Map<String, Map<String, String>> map = new HashMap<String, Map<String, String>();
Map<String, String> innerMap = new HashMap<String, String>();
innerMap.put("x","y");
map.put("z", innerMap);
innerMap = map.get("z"); <---------- O(1) time
String y = innerMap.get("x"); <-------- O(1) time

¿Esto significa que mientras los tiempos de búsqueda de ambos mapas se mantengan relativamente cerca de O (1), entonces usted puede esencialmente buscar a través de un segundo nivel de un hashmap aún en O (1) vez?

Mis responsabilidades de pasantía me tienen que ocupar mucho de las comparaciones de datos y usé algo similar a esto el otro día. Tenía un valor de clave de cadena que era el nombre de un cierto "Plan" y un valor como un hashmap. El hashmap interno tenía un valor de clave de cadena de una identificación de empleado y una relación (si se visitó a un empleado dos veces lo que significa que tenían dos niveles de cobertura diferentes dentro del plan del mapa externo, entonces su relación se actualizaría. Fue mi elección de DS aquí uno bueno? Estaba tratando de lograr un tiempo de búsqueda y edición de O (1)

Answer 1

Básicamente, estás preguntando si el tiempo de ejecución para encontrar un elemento en un hashmap dentro de otro hashmap es constante. La respuesta es sí . Porque piense primero en un hashmap de hashmaps. Como dijiste antes, el tiempo que lleva encontrar un valor usando una tecla es constante. El tiempo de ejecución total es solo dos veces; por lo tanto O (1) * 2 = O (2) que todavía es O (1). Por supuesto, debe considerar las colisiones, que en exceso pueden ralentizar el proceso de búsqueda. Esto se puede evitar, por supuesto, eligiendo un factor de carga adecuado.

Answer 2

O(1) no significa "completa en un solo paso". Significa que se completa en (aproximadamente) la misma cantidad de tiempo sin importar cuán grande sea la población. Es por eso que O(1) también se llama tiempo constante .

Un número fijo de repeticiones de una operación de tiempo constante también es tiempo constante, es decir O(1) .

La respuesta es "sí", su estructura de datos tiene O(1) complejidad de tiempo para acceder a los valores de los mapas anidados.