Как написать хеш-код для древовидной структуры данных, основанной на расположении элемента в дереве?

Question

Каждый элемент выглядит так:

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

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

Я хочу создать древовидную структуру, используя множество экземпляров этих элементов, связанных друг с другом, образуя древовидную структуру. Но позже я хочу хешировать каждый элемент в Словаре, поэтому я подумал, что если бы я мог создать хеш-значение на основе их расположения в дереве, то я мог бы получить достаточно уникальные хеш-значения.

Есть идеи, как это сделать?

Answer 1

в зависимости от того, где они находятся на дереве

Эта информация является не частью узла, а деревом.Так что это была бы очень плохая идея (определение чего-то HashCode по внешним факторам).

К счастью, как указывает @spintheblack, нет абсолютно никакой причины переопределять GethashCode () здесь.

Answer 2

Это должно сработать. Предупреждение: не переопределяйте GetHashCode с этим методом. GetHashCode не должен изменяться, потому что позиция объектов в родительской сущности изменилась. Используйте этот трюк, только если у вас есть другие планы для хэш-кода. Вот примерный пример того, что должно делать то, что вы просите. Это только показывает, как вы найдете положение текущего родителя, но вы можете расширить его, чтобы обойти дерево, пока у него нет родителя.

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 3

каждый элемент, который реализует интерфейс IEffect, должен переопределять ToString & GetHashCode

В ToString shold включено уникальное состояние свойств IEffect, включая выбранное значение, GetHashCode должен быть ToString (). GetHashCode ()

и у вас есть уникальный хэш для каждого объекта на основе внутренних данных вашего объекта.

Answer 4

Скопировано из моего комментария к комментариям :).Зачем вам хэш-значение?Что плохого в том, чтобы просто использовать объектную хэш-функцию по умолчанию?Если бы это было полное двоичное дерево, вы могли бы отобразить узлы на целочисленные значения, но с произвольным n-кратным деревом, я не вижу простого способа кодировать позицию в значение.

Answer 5

Вот как я сделал то, что, на мой взгляд, вам действительно нужно сделать. Это позволит пройти весь процесс обработки дерева. Нет необходимости связываться с родителем, если вам не нужно начинать с середины дерева. Конечно, это просто моя дикая интерпретация того, что вы пытаетесь сделать.

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

    else
        HandleEffect(effect.ElseEffect);
}