Erstellen einer hashmap mit einem zwei-Schlüssel -

Ich bin auf der Suche nach einer geeigneten Datenstruktur für mein problem. Ich möchte in der Lage sein zu wählen, node-Objekten so effizient wie möglich mit zwei Tasten. Einfügen und löschen muss auch effizient sein. Im Grunde ist jedes node-Objekt hat ein paar von zwei Schlüsseln. Die Paare sind einzigartig, aber die einzelnen Tasten nicht. Ich muss in der Lage sein zu wählen, einer Gruppe von Knoten, die einen bestimmten Wert für eine der zwei Tasten.

Beispiel:

Node1 hat die Schlüssel a1 und b1

Node2 hat die Schlüssel a1 und b2

Knoten3 hat die Schlüssel a2 und b2

Möchte ich zum Beispiel in der Lage sein, wählen Sie den Knoten mit dem Schlüssel a1,b1, sondern auch alle Knoten b2 Schlüssel2.

Könnte ich natürlich machen zwei HashMaps (einer für jeden Schlüssel), aber das ist irgendwie eine unschöne Lösung, weil wenn ich hinzufügen oder entfernen von etwas, das ich tun müsste, wäre es in beiden Karten. Da gibt es eine Menge, hinzufügen und entfernen geht würde ich es vorziehen, dies zu tun in einem Rutsch. Hat jemand irgendwelche Ideen, wie dies zu tun?

Offensichtlich mit einem einzigen Schlüssel verschmilzt, dass die beiden Tasten zusammen, löst das problem nicht, weil ich muss auch in der Lage sein, um die Suche für einen einzelnen Schlüssel ohne Suche durch die gesamte Karte. Das wäre nicht sehr effizient. Das problem ist ein Effizienz-problem. Ich konnte einfach nur suchen, jeder Eintrag in der Karte nach einem bestimmten Schlüssel, aber stattdessen würde ich gerne auf einen hash, so dass ich kann wählen Sie mehrere Knoten-Objekte mit einer der beiden Tasten sofort.

Ich bin nicht auf der Suche nach so etwas wie die MultiKeyMap, da in diese Daten-Struktur der erste Schlüssel bleibt immer gleich, Sie kann nur hinzufügen, Tasten, statt Sie zu ersetzen der erste Schlüssel mit einem anderen Schlüssel. Ich will Umschalten können zwischen der ersten und der zweiten Taste.

Ich tun und nicht wollen, um zu speichern mehrere Objekte mit dem gleichen Schlüssel. Wenn man sich die Beispiel können Sie sehen, dass die beiden Tasten zusammen, sind immer einzigartig. Dies kann gesehen werden als ein einzelner Schlüssel daher würde ich nicht speichern mehrerer Objekte unter dem gleichen Schlüssel. Aber wenn man sich die einzelnen Tasten, diese sind nicht eindeutig, deshalb möchte ich mir zum speichern mehrerer Objekte verwiesen wird, die von den einzelnen Tasten.

sind Sie auf der Suche nach so etwas wie dieser ?
möchten Sie Sie speichern mehrere Objekt mit dem gleichen key?

InformationsquelleAutor Danielle | 2011-12-21

6

Wenn Sie können, verwenden Sie eine Bibliothek, einen Blick auf die Tabelle Schnittstelle von Guave. Es ordnet einer Zeile und einer Spalte mit einem Wert. Die Zeilen-und Spalten können die ersten und zweiten Schlüssel. Sie können auch Suche nach Zeile oder Spalte.

Einer der Implementierungen dieser Schnittstelle ist hash-basierte.

InformationsquelleAutor Luciano

Müssen Sie einen key-Klasse (Gleichheit behandelt wird, als Punkt):

public class Key {

    int field1;
    int field2;

    public boolean equals(Object o) {
        if (o == null || !(o instanceof Key)) return false;
        Key other = (Key) o;
        return field1 == other.field1 && field2 == other.field2;
    }

    public int hashCode() {
        return field1*field2; //doesn't matter if some keys have same hash code
    }

}

Zur Auswahl-keys mit einem bestimmten Wert in das erste Feld:

public List<Key> getKeysWithField1EqualsTo(int value) {
    List<Key> result = new ArrayList<>();
    for (Key k: map.keySet()) {
        if (k.field1 == value) result.add(k);
    }
    return result;
}

InformationsquelleAutor Alberto

2

Da dies sehr spezifisch auf dein problem an der hand, werden Sie sehr wahrscheinlich benötigen, um die Entwicklung Ihrer eigenen Sammlung. Ich würde wickeln zwei MultiMaps von Apache Commons in meiner eigenen collection-Klasse, die sich mit updates der beiden multi-Karten zur gleichen Zeit, und meine Klasse zum durchführen von Einfügungen und Abfragen.

InformationsquelleAutor dasblinkenlight
1

Schreiben Sie eine einfache Klasse ist in der Lage, zwei Werte enthalten (die Schlüssel) und überschreiben von equals ( ... ) und hashCode() für die Gleichstellung Prüfungen von der Karte. Nutzen Sie diese einfache Klasse als key für die map.

Hier finden Sie eine hashmap kompatibel pair-Klasse (2. Antwort):

Was ist das äquivalent der C++ - Pair<L,R> in Java?
- Dies löst nicht die OP ' s problem (er braucht, um die Suche auf eine Taste, und Holen Sie mehrere Werte).
InformationsquelleAutor Dennis
1

Da eine HashMap kann nur eine Art auf ein hash für jedes Objekt, das Sie nie in der Lage sein zu wählen, die unterschiedliche Listen 'out of the box'. Was würde ich vorschlagen, wird mit einem Tupel mit zwei Tasten, und dann die Iteration über die HashMap und wählen Sie nur diejenigen Elemente, die Tupel.key1=X.

InformationsquelleAutor Willem Mulder
1

HashMaps kann jedes Objekt als Key-also warum nicht eine Klasse erstellen mit 2 Feldern und betrachten diese Klasse als Ihre Schlüssel. Sie können auch Überschreiben der Equals-Methode sagen, wie die Tasten sind gleich,

InformationsquelleAutor Adel Boutros
0

Ich denke, wir können es tun auf diese Weise: Für jeden Schlüssel, können wir berechnen die entsprechenden hashcode.
```
key1 -> hashcode1
key2 -> hashcode2
```
Dann haben wir eine 2-d-array mit N Spalten und N Zeilen.
```
key1 -> rowIndex: hashcode1 MOD N
key2 -> columnIndex: hashcode2 MOD N
```
Dann speichern wir das Element in array[rowIndex][columnIndex].

In dieser Implementierung können Sie die Einträge mit einem Ziel-key1, und alle key2. Sie können auch alle Einträge mit dem Ziel, key2, und alle key1.

Dieses array kann erweitern, wenn es gibt eine Menge von Kollisionen, genau wie das, was Sie tun, mit den normalen hashmap.

InformationsquelleAutor nisxiya

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.