Eingebettete Hash-Karte Groß (O)?

Question

Wenn Sie eine Hash-Karte einbetten wie so:

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 

dies, dass so lange, heißt das, da beide Karten zu suchen Zeiten O relativ nahe bleiben (1), dann können Sie im Wesentlichen durch eine zweite Ebene eines hashmap suchen noch in O (1) Zeit?

Meine Aufgaben als Praktikant beschäftigen mich sehr mit Datenvergleichen, und ich habe neulich etwas Ähnliches verwendet. Ich hatte einen String-Schlüsselwert, der den Namen eines bestimmten "Plans" und einen Wert als Hashmap enthielt. Die interne hashmap hatte einen String-Schlüsselwert einer Angestellten-ID und einer Beziehung (wenn ein Mitarbeiter zweimal besucht wurde, was bedeutet, dass er zwei unterschiedliche Deckungsgrade innerhalb des Plans von der externen Karte hatte, dann würde seine Beziehung aktualisiert werden.) ein guter? ich versuche, eine Lookup & bearbeiten Zeit von O (1)

Answer 1

Sie fragt, ist grundsätzlich zu erreichen, wenn die Laufzeit ein Element in einem hashmap innerhalb eines anderen hashmap findet konstant ist. die Antwort ist ja Weil Sie zuerst an eine Hashmap von hashmaps denken: Wie Sie bereits gesagt haben, ist die Zeit, die es braucht, um einen Wert mit einem Schlüssel zu finden, konstant, die gesamte Laufzeit ist genau dies zweimal, also O (1) * 2 = O (2) was ist immer noch O (1). Natürlich müssen Sie Kollisionen in Betracht ziehen, die im Übermaß den Suchprozess verlangsamen können natürlich vermieden durch die Auswahl eines geeigneten Ladefaktors.

Answer 2

O(1) bedeutet nicht "in einem Schritt abgeschlossen". Es bedeutet, dass es (ungefähr) die gleiche Menge an Zeit abschließt, egal wie groß die Population ist. Deshalb wird O(1) auch konstante Zeit genannt.

Eine feste Anzahl von Wiederholungen einer konstanten Zeit Operation ist auch konstante Zeit, dh O(1).

Die Antwort ist "Ja", Ihre Datenstruktur hat O(1) Zeit Komplexität für den Zugriff auf Werte aus den verschachtelten Karten.