Warum sollte ich ein HashSet über ein Dictionary verwenden?

Question

Ich versuche, eine Liste der zwischengespeicherten Pfade auf einem A * -Algorithmus zu implementieren. Derzeit werden die im Cache gespeicherten Pfade in einer Liste wie folgt gespeichert:

readonly List<CachedPath> _cachedPaths = new List<CachedPath>(); 

Die Operationen über diese Liste durchgeführt werden:

FirstOrDefault ein Element zu erhalten, die bestimmten Bedingungen

var cached = _cachedPaths.FirstOrDefault(p => p.From == from && p.To == target && p.Actor == self); 

erfüllt entfernen und Element

_cachedPaths.Remove(cached); 

Ergänzungen

_cachedPaths.Add(new CachedPath { 
        From = from, 
        To = target, 
        Actor = self, 
        Result = pb, 
        Tick = _world.WorldTick 
       }); 

HINWEIS: Die Klasse CachedPath hat GetHashCode und Equals nur durch die von, nach und Schauspieler außer Kraft gesetzt, so dass zwei Instanzen, die diese Attribute haben den gleichen Hash und Gleichheit haben.

Da schnelle Lookups (enthält), Einfügungen und Löschungen in einem ‚HashSet‘ sind O (1) (wenn ich mich nicht irre), hielt ich mit einem ‚HashSet‘ diese Operationen zu tun. Das einzige Problem ist der FirstOrDefault, den ich die ganze Sammlung aufzählen musste, um es zu bekommen.

dieses Problem Da ich als auch durch den Hash von, nach und Schauspieler indiziert eine Dictionary:

Dictionary<int, CachedPath> cachedPath 

Noch einmal, wenn ich mich nicht irre, Wörterbuch bietet auch O (1) in Einfügungen, Löschungen und auch das Abrufen durch Key. Das führt mich zu der Annahme, dass ein Dictionary eine HashSet + O (1) -Element-Retrieval-Funktion ist.

Fehle ich etwas? Ist das Wörterbuch wirklich besser als HashSet in dem Sinne, dass es mehr Operationen unterstützt?

Vielen Dank im Voraus.

Answer 1

Dictionary ist nicht besser als HashSet, es ist nur anders.

• Sie verwenden einen HashSet, wenn Sie eine ungeordnete Sammlung von Elementen speichern möchten, und
• Sie verwenden einen Dictionary, wenn Sie eine Menge von Elementen „Schlüssel“ mit einer anderen Sammlung von Gegenständen als „Werte genannt zuordnen möchten "

Man könnte denken sie an einem HashSet als Dictionary ohne zugehörige Werte (in der Tat, HashSet manchmal ein Dictionary hinter der Szene implementiert ist), aber es ist nicht notwendig, um es auf diese Weise zu denken: denken die zwei als von enti verschiedene Dinge zu tun, funktioniert auch gut.

In Ihrem Fall könnten Sie möglicherweise die Leistung verbessern, indem ein Wörterbuch von dem Schauspieler zu machen, wie folgt aus:

Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor 

Auf diese Weise Ihre lineare Suche schnell eine Unterliste basierend auf einem Schauspieler wählen würde, und dann linear suchen von Ziel:

var cached = _cachedPathsByActor[self].FirstOrDefault(p => p.From == from && p.To == target); 

oder durch einen Gleichheitsvergleich machen, die alle drei Elemente betrachtet, und eine Dictionary mit CachedPath als beide Schlüssel und Werte verwenden, und dieser benutzerdefinierten IEqualityComparer<T> als Schlüssel comparer:

class CachedPathEqualityComparer : IEqualityComparer<CachedPath> { 
    public bool Equals(CachedPath a, CachedPath b) { 
     return a.Actor == b.Actor 
      && a.From == b.From 
      && a.To == b.To; 
    } 
    public int GetHashCode(CachedPath p) { 
     return 31*31*p.Actor.GetHashCode()+31*p.From.GetHashCode()+p.To.GetHashCode(); 
    } 
} 
... 
var _cachedPaths = new Dictionary<CachedPath,CachedPath>(new CachedPathEqualityComparer()); 
... 
CachedPath cached; 
if (_cachedPaths.TryGetValue(self, out cached)) { 
    ... 
} 

geht jedoch davon aus diesem Ansatz, dass es höchstens ein Eintrag im Wörterbuch mit identischen From, To und Actor wäre.

Answer 2

Ein Hashset wird beim Ausführen eines Adds keine Ausnahme auslösen. Stattdessen gibt es einen Bool zurück, der den Erfolg des Adds widerspiegelt.

Auch ein Hashset erfordert kein keyValue-Paar. Ich verwende Hashsets, um eine Sammlung von eindeutigen Werten zu garantieren.