Zusammengesetzte Schlüssel: Eine Anleitung zum Umgang damit

Bei zusammengesetzten Schlüsseln ist eine Kombination von Daten erforderlich, um den „Schlüssel“ für Ihre Karten- oder Cache-Suche zu definieren. Ein Beispiel hierfür könnte sein, dass Sie Werte basierend auf einem Kundennamen und einer Benutzerrolle zwischenspeichern müssen. In einem solchen Fall müsste Ihr Cache in der Lage sein, eindeutige Werte basierend auf jedem dieser beiden (oder mehr) Kriterien zu speichern.

Es gibt verschiedene Möglichkeiten, zusammengesetzte Schlüssel im Code zu verarbeiten.

Kombinieren Sie die Kriterien zu einer Zeichenfolge

Die erste Antwort, zu der am häufigsten gesprungen wird, ist die Kombination der Kriterien zu einer Zeichenfolge, die als Schlüssel verwendet wird. Es ist einfach und erfordert keinen großen Aufwand:

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

Dies ist eine ziemlich einfache Möglichkeit, das Problem zu lösen. Die Verwendung eines Zeichenfolgenschlüssels kann das Debuggen und Untersuchen erleichtern, da der Cache-Schlüssel in einem für Menschen lesbaren Format vorliegt. Bei diesem Ansatz sind jedoch einige Probleme zu beachten:

1. Es erfordert, dass bei jeder Interaktion mit der Karte eine neue Zeichenfolge erstellt wird. Obwohl diese Zeichenfolgenzuordnung im Allgemeinen gering ist, kann sie bei häufigem Zugriff auf die Karte zu einer großen Anzahl von Zuweisungen führen, die Zeit in Anspruch nehmen und durch Müll gesammelt werden müssen. Der Umfang der String-Zuweisung kann auch größer sein, je nachdem, wie groß die Komponenten Ihres Schlüssels sind bzw. wie viele Sie haben.

   
   

2. Sie müssen sicherstellen, dass der von Ihnen erstellte zusammengesetzte Schlüssel nicht in einen anderen Schlüsselwert gefälscht werden kann:

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

Wenn Sie oben „groupId = 1“ und „accessType = 23“ hätten, wäre das derselbe Cache-Schlüssel wie „groupId = 12“ und „accessType = 3“. Durch Hinzufügen eines Trennzeichens zwischen den Zeichenfolgen können Sie diese Art von Überlappung verhindern. Seien Sie jedoch vorsichtig mit optionalen Teilen eines Schlüssels:

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

Im obigen Beispiel ist extensionName ein optionaler Teil des Schlüssels. Wenn der Erweiterungsname optional ist, könnte userProvidedString ein Trennzeichen und einen gültigen Erweiterungsnamen enthalten und Zugriff auf Cache-Daten erhalten, auf die er keinen Zugriff haben sollte.

Wenn Sie Zeichenfolgen verwenden, sollten Sie darüber nachdenken, wie Sie Ihre Daten kombinieren, um Kollisionen in den Schlüsseln zu vermeiden. Insbesondere im Hinblick auf alle benutzergenerierten Eingaben für den Schlüssel.

Verwenden Sie verschachtelte Karten/Caches

Eine andere Möglichkeit besteht darin, die Schlüssel überhaupt nicht zu kombinieren und stattdessen Ihre Datenstrukturen zu verschachteln (Maps of Maps of Maps):

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

Dies hat den Vorteil, dass bei der Interaktion mit den Karten kein neuer Speicher zugewiesen werden muss, da die übergebenen Werte für die Schlüssel bereits zugewiesen sind. Und obwohl Sie mehrere Suchvorgänge durchführen müssen, um den endgültigen Wert zu erhalten, werden die Karten kleiner sein.

Der Nachteil dieses Ansatzes besteht jedoch darin, dass er umso komplizierter wird, je tiefer die Verschachtelung erfolgt. Selbst mit nur zwei Ebenen kann die Karteninitialisierung verwirrend aussehen. Wenn Sie mit drei oder mehr Daten arbeiten, kann dies dazu führen, dass Ihr Code sehr ausführlich wird. Darüber hinaus erfordert jede Ebene eine Nullprüfung, um Nullzeiger zu vermeiden.

Einige „Schlüsselteile“ funktionieren möglicherweise auch nicht gut als Kartenschlüssel. Arrays oder Sammlungen verfügen nicht über standardmäßige Equals-Methoden, die ihren Inhalt vergleichen. Sie müssten sie also entweder implementieren oder eine andere Alternative verwenden.

Die Verwendung verschachtelter Karten könnte auch weniger platzsparend sein, je nachdem, wie einzigartig jede Ebene Ihrer Schlüssel ist.

Erstellen Sie ein zusammengesetztes Schlüsselobjekt

Die letzte Option besteht darin, statt die Schlüsselwerte in einer Zeichenfolge zu kombinieren, stattdessen ein benutzerdefiniertes Objekt für den Schlüssel zu erstellen:

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

Während jede Interaktion immer noch eine neue Speicherzuweisung für ein neues Objekt erfordert. Die Objektschlüsselzuweisung ist deutlich kleiner als die, die für eine zusammengesetzte Zeichenfolge erforderlich ist. Der Grund dafür ist, dass die Teile, aus denen der Schlüssel besteht, nicht als Zeichenfolgen neu zugewiesen werden müssen. Stattdessen benötigt nur der Wrapping-Objektschlüssel neuen Speicher.

Ein zusammengesetztes Schlüsselobjekt kann auch Anpassungen in den Schlüsselgleichheits- und Hashcode-Implementierungen ermöglichen. Beispielsweise wird die Groß- und Kleinschreibung in einer Zeichenfolge ignoriert oder ein Array oder eine Sammlung als Teil eines Schlüssels verwendet.

Der Nachteil hierbei ist jedoch, dass wiederum viel mehr Code erforderlich ist als für eine zusammengesetzte Zeichenfolge. Und es erfordert sicherzustellen, dass Sie gültige Equals- und Hashcode-Verträge in der Schlüsselklasse für Ihre Karte haben.

Was soll ich also wählen?

Im Allgemeinen würde ich die Verwendung eines zusammengesetzten Zeichenfolgenschlüssels empfehlen. Es ist einfach und leicht zu verstehen, erfordert am wenigsten Code und lässt sich später am einfachsten debuggen. Obwohl dies wahrscheinlich die langsamste Methode ist, ist das Schreiben von einfachem, lesbarem Code im Allgemeinen wichtiger als die Vorteile, die Sie mit einer der beiden anderen Optionen erzielen würden. Erinnern:

„Vorzeitige Optimierung ist die Wurzel allen Übels“ Donald Knuth

Wenn Sie keine Beweise oder keinen Grund zu der Annahme haben, dass Ihre Karten-/Cache-Suche einen Leistungsengpass darstellt, entscheiden Sie sich für die Lesbarkeit.

Wenn Sie sich jedoch in einem Szenario befinden, in dem der Durchsatz Ihrer Karte oder Ihres Caches sehr hoch ist, kann es sinnvoll sein, zu einer der beiden anderen Optionen zu wechseln. Sehen wir uns an, wie sich alle drei hinsichtlich der Leistung und der Speicherzuteilungsgröße vergleichen.

Um die drei oben genannten Szenarien zu testen, habe ich Code geschrieben, der die gleiche Implementierung aller drei Szenarien für einen zusammengesetzten Schlüssel repliziert. Der Schlüssel selbst besteht aus einem ganzzahligen Wert, einem Zeichenfolgenwert und einem langen Wert. Alle drei Implementierungen verwendeten bei jedem Durchlauf dieselben Testdaten, um die Schlüssel zu erstellen.

Alle Läufe wurden mit 1 Million Datensätzen in der Karte ausgeführt (es wurde Javas Hashmap verwendet). Es wurden 3 Durchläufe zum Aufbau des Schlüssels mit unterschiedlichen Kombinationen von Schlüsselgrößen durchgeführt:

• 100 Ints, 100 Strings, 100 Longs – 1 Million einzigartige Schlüssel

• 1 int, 1 string, 1.000.000 longs – 1 Million eindeutige Schlüssel

• 1.000.000 Ints, 1 String, 1 Long – 1 Million eindeutige Schlüssel

  
  

Schauen wir uns zunächst an, wie viel Platz jede Karte im Heap einnimmt. Dies ist wichtig, da es sich darauf auswirkt, wie viel Speicher zum Ausführen Ihrer Anwendung benötigt wird.

Hier ist eine interessante, offensichtliche Anmerkung zu machen: Im letzten Szenario (1.000.000 Ints) ist die Größe der verschachtelten Karten deutlich größer als bei den anderen. Dies liegt daran, dass in diesem Szenario die verschachtelten Karten eine Karte der ersten Ebene mit 1 Million Einträgen erstellen. Dann werden für die zweite und dritte Ebene 1 Million Karten mit nur einem Eintrag erstellt.

Alle diese verschachtelten Karten verursachen zusätzlichen Overhead und sind größtenteils leer. Dies ist offensichtlich ein Randfall, aber ich wollte ihn zeigen, um einen Punkt zu verdeutlichen. Bei der Verwendung der Nest-Maps-Implementierung ist die Einzigartigkeit (und die Reihenfolge dieser Einzigartigkeit) von großer Bedeutung.

Wenn man die Reihenfolge auf 1, 1, 1 Million umdreht, erhält man tatsächlich den geringsten Speicherbedarf.

In den anderen beiden Szenarios ist die verschachtelte Zuordnung am effizientesten, wobei das benutzerdefinierte Schlüsselobjekt an zweiter Stelle und die Zeichenfolgenschlüssel an letzter Stelle stehen.

Schauen wir uns als Nächstes an, wie viel Zeit es dauert, jede dieser Karten von Grund auf zu erstellen:

Auch hier sehen wir, dass die verschachtelten Karten im 1-Million-1–1-Szenario hinsichtlich der Speicherzuweisung am schlechtesten abschneiden, aber selbst dann übertreffen sie die anderen bei der CPU-Zeit. Oben sehen wir auch, dass der String-Schlüssel in allen Fällen die schlechteste Leistung erbringt, während die Verwendung eines benutzerdefinierten Schlüsselobjekts etwas langsamer ist und mehr Speicherzuweisung erfordert als die verschachtelten Schlüssel.

Schauen wir uns zum Schluss das Szenario mit dem höchsten Durchsatz an und wie effektiv es beim Lesen ist. Wir haben 1 Million Lesevorgänge ausgeführt (1 für jeden erstellten Schlüssel); Wir haben keine nicht vorhandenen Schlüssel beigefügt.

Hier sehen wir wirklich, wie langsam die stringbasierte Schlüsselsuche ist. Von allen drei Optionen ist sie bei weitem die langsamste und reserviert bei weitem den meisten Speicher. Die Leistung des benutzerdefinierten Schlüsselobjekts ähnelt der der verschachtelten Kartenimplementierung, ist jedoch immer noch um einen kleinen Vorsprung langsamer.

Beachten Sie jedoch bei der Zuordnung von Suchspeicher, wie gut die verschachtelten Karten glänzen. Nein, das ist kein Fehler in der Grafik; Das Nachschlagen eines Werts in den verschachtelten Karten erfordert keine zusätzliche Speicherzuweisung für die Suche. Wie ist das möglich?

Nun, wenn Sie die zusammengesetzten Objekte zu einem String-Schlüssel kombinieren, müssen Sie jedes Mal Speicher für ein neues String-Objekt zuweisen:

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

Wenn Sie einen zusammengesetzten Schlüssel verwenden, müssen Sie dennoch Speicher für ein neues Schlüsselobjekt zuweisen. Da die Mitglieder dieses Objekts jedoch bereits erstellt und referenziert sind, weist es immer noch viel weniger zu als eine neue Zeichenfolge:

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

Die Implementierung verschachtelter Karten erfordert jedoch keine neue Speicherzuweisung bei der Suche. Sie verwenden die angegebenen Teile als Schlüssel für jede der verschachtelten Karten wieder:

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

Welches ist also, basierend auf dem oben Gesagten, das leistungsstärkste?

Es ist leicht zu erkennen, dass die verschachtelten Karten in fast allen Szenarien die Nase vorn haben. Wenn Sie in den meisten Anwendungsfällen nach purer Leistung suchen, ist dies wahrscheinlich die beste Option. Sie sollten jedoch eigene Tests durchführen, um Ihre Anwendungsfälle zu bestätigen.

Das Schlüsselobjekt stellt eine sehr gute Allzweckoption dar, wenn verschachtelte Karten für Ihre Implementierung unpraktisch oder gar nicht verwendbar sind. Und obwohl der zusammengesetzte Zeichenfolgenschlüssel am einfachsten zu implementieren ist, wird er fast immer am langsamsten sein.

Der letzte zu berücksichtigende Punkt bei der Implementierung zusammengesetzter Schlüssel ist, dass Sie die oben genannten Elemente kombinieren können. Sie könnten beispielsweise verschachtelte Karten für die erste oder zweite Ebene verwenden und dann ein zusammengesetztes Schlüsselobjekt verwenden, um die tieferen Ebenen zu vereinfachen.

Dadurch könnten Ihre Daten weiterhin für schnelle Suchvorgänge partitioniert bleiben und gleichzeitig die Speicher- und Suchleistung optimiert werden. Und sorgen Sie auch dafür, dass Ihr Code lesbar ist.

TLDR;

Halten Sie es meistens einfach einfach. Kombinieren Sie Ihre zusammengesetzten Schlüssel zu einem Zeichenfolgenschlüssel zur Speicherung in einer Karte oder einem Cache, wenn dies die einfachste Option ist und die Leistung kein großes Problem darstellt.

Stellen Sie in Szenarien, in denen die Leistung von entscheidender Bedeutung ist, sicher, dass Sie Ihre eigenen Tests durchführen. In den meisten Fällen ist die Verwendung verschachtelter Karten jedoch am leistungsstärksten. Es wird wahrscheinlich auch den geringsten Speicherbedarf haben. Und zusammengesetzte Schlüssel sind immer noch eine leistungsstarke Alternative, wenn verschachtelte Zuordnungen unpraktisch werden.

Auch hier veröffentlicht