Ist es möglich, Hashcodes als Bitmaske zu verwenden, um Sammlungsmitgliedschaft effizient zu speichern/zu verfolgen?

Question

Derzeit habe ich eine Lösung, wo ich Objekte, die mich interessieren, verfolgen, indem ich ihren Hashcode über Object.GetHashCode erhalte und sie dann in einem HashSet<int> speichern.

Allerdings habe ich auch über Bitmasken und bitweise Operationen gelernt, und ich bin ziemlich fasziniert von ihnen. Here is a great question, die ich in der Nähe zu dem, was ich suche, gefunden habe. Ich kann jedoch nicht scheinen, dass dies effizient für Hash-Codes funktioniert.

There is also this question, aber es scheint sich mit 5-Bit-Nummern zu beschäftigen, wenn Hash-Codes int 's (32-Bit) sind.

Ich bekomme die Lösung (von der ersten referenzierten Frage) funktioniert, aber es ist nicht so schnell wie meine aktuelle HashSet-Ansatz ist. Dies ist auf die schiere Anzahl der Elemente in zurückzuführen, die erstellt werden müssen, um alle bekannten Hash-Codes zu berücksichtigen (int.MaxValue).

Gibt es eine bitmask/bitweise Operation, die ich bei der Arbeit mit einem BitArray berücksichtigen sollte? Oder bin ich hier völlig ausgetreten und sollte einfach bei meiner HashSet<int> Lösung bleiben?

Answer 1

Dies war in der Tat ein Beispiel für einen ausgetretenen Pfad, gepaart mit einem Missverständnis der Referenzen/Speicherverwaltung. In meinem Fall habe ich ein Objekt Dictionary<TKey, TValue> verwendet, um zwischengespeicherte Ergebnisse aus Methodenaufrufen für eine Instanz zu speichern. Ich konnte keine ConditionalWeakTable weil es mindestens drei Teile zu einem Schlüssel verwenden:

1. Die Instanz, die die Methode enthält, wo die Ergebnisse im Cache gespeichert werden.
2. Diese Methode.
3. Argumente, die an die Methode übergeben werden.

Wenn ich früher ein ConditionalWeakTable ich hätte „noch eine weitere Aufgabe“ erstellen (Klasse), die noch eine andere Zuordnung erfordern würde, aber schlimmer wäre noch nicht alles verwiesen werden (neben dem ConditionalWeakTable) und würde sich Müll gesammelt auf den ersten Durchgang (das ist in der Tat related to another open -- but now also solved -- question of mine).

Nach vielen Überlegungen habe ich festgestellt, dass die Antwort tatsächlich in ConditionalWeakTable liegt. Anstatt die drei oben genannten Elemente als Schlüssel zu verwenden, verwenden Sie eine Delegate, die aus den Teilen 1 und 2 besteht, und verbinden Sie dann eine Dictionary mit dieser.

Oder als Feldinitialisierung zu setzen:

readonly ConditionalWeakTable<Delegate, Dictionary<object[], object>> cache = new ConditionalWeakTable<Delegate, Dictionary<object[], object>>(); 

(Bemerkenswert ist auch die Verwendung eines StructuralEqualityComparer mit dem obigen Wörterbuch diese Arbeit zu machen).

Dies tut natürlich alles, was ich will. Es wird Objekte verfolgen, bis das referenzierte Objekt, das die Methode enthält (und aus der Delegate besteht), aus dem Speicher gelöscht wird. An diesem Punkt wird auch das zwischengespeicherte Wörterbuch freigegeben, wobei alle Inhalte gelöscht werden.