Wie schreibt man einen Hash-Code für eine baumartige Datenstruktur auf der Grundlage der Position des Elements im Baum?

Question

Jedes Element sieht wie folgt aus:

public interface IEffect
{
    string Name { get; }
    bool Compute ( );

    List<IEffect> SubEffects { get; set; }
    IEffect ElseIfEffect { get; set; }
}

Ich möchte eine baumartige Struktur mit vielen Instanzen dieser Elemente erstellen, die miteinander verbunden sind und eine baumartige Struktur bilden. Aber später möchte ich jedes Element zu einem Dictionary Hash, so dass ich dachte, wenn ich einen Hash-Wert erstellen könnte, basierend auf, wo sie auf dem Baum sind, dann könnte ich eindeutig genug Hash-Werte erhalten.

Haben Sie eine Idee, wie man das machen kann?

Answer 1

je nach ihrer Position im Baum

Diese Informationen sind nicht Teil des Knotens, sondern des Baumes. Es wäre also eine sehr schlechte Idee (etwas wie HashCode über externe Faktoren zu definieren).

Glücklicherweise, wie @spintheblack darauf hinweist, gibt es absolut keinen Grund, GethashCode() hier zu überschreiben.

Answer 2

Kopiert von meinem Kommentar per Kommentar :). Warum brauchen Sie einen Hash-Wert? Was ist falsch daran, einfach die Standard-Objekt-Hash-Funktion zu verwenden? Wenn es sich um einen vollständigen Binärbaum handeln würde, könnte man die Knoten auf Integer-Werte abbilden, aber bei einem beliebigen n-ary Baum sehe ich keine einfache Möglichkeit, die Position in einen Wert zu kodieren.

Answer 3

Jedes Element, das die Schnittstelle IEffect implementiert, sollte ToString & GetHashCode außer Kraft setzen

ToString sollte den eindeutigen Status der IEffect-Eigenschaften einschließlich des ausgewählten Werts enthalten GetHashCode sollte ToString().GetHashCode() sein

und dort haben Sie einen eindeutigen Hash für jedes Objekt, der auf den inneren Daten Ihres Objekts basiert.

Answer 4

Damit sollte es klappen. Warnung: Überschreiben Sie GetHashCode nicht mit dieser Methode. GetHashCode sollte sich nicht ändern, weil sich die Position eines Objekts in einer übergeordneten Entität geändert hat. Verwenden Sie diesen Trick nur, wenn Sie andere Pläne für den Hashcode haben. Hier ist ein grobes Beispiel von etwas, das tun sollte, was Sie verlangen. Dies zeigt nur, wie Sie die Position des aktuellen Elternteils finden würden, aber Sie könnten es erweitern, um den Baum zu durchlaufen, bis er kein Elternteil mehr hat.

class MyEffect : IEffect
{
    IEffect _owner;
    public MyEffect(IEffect owner) 
    {
        _owner = owner;
    }

    public int GetFunkyHash()
    {
        int hash = this.GetHashCode();
        int index = _owner.IndexOf(item);
        return hash | index.GetHashCode();
    }
}

Answer 5

So habe ich das gemacht, was Sie meiner Meinung nach wirklich tun müssen. Dies wird die gesamte Baumverarbeitung effets gehen. Es ist nicht nötig, eine Verknüpfung zu einem übergeordneten Element herzustellen, es sei denn, Sie müssen in der Mitte des Baums beginnen. Natürlich ist dies nur meine wilde Interpretation dessen, was Sie versuchen könnten zu tun.

public void HandleEffects(IEffect effect)
{
    if(effect.Compute())
        foreach(IEffect child in effect.SubEffects)
            HandleEffects(child);

    else
        HandleEffect(effect.ElseEffect);
}