How to write hash code for a tree-like data structure based on the location of the item in the tree?

Question

Each item looks like this:

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

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

I want to create a tree-like structure using many instances of these items connected to each other forming a tree-like structure. But later I want to hash each item to a Dictionary, so I thought if I could create a hash value based on where they are on the tree, then I could get unique-enough hash values.

Any ideas on how to do this?

Answer 1

based on where they are on the tree

That information is not part of the node but of the tree. So it would be a very bad idea (defining somethings HashCode on external factors).

Luckily, as @spintheblack points out, there is absolutely no reason to override GethashCode() here.

Answer 2

Copied from my comment per comments :). Why do you need a hash value? What's wrong with simply using the default object hash function? If this were a complete binary tree, you could map nodes to integer values but with an arbitrary n-ary tree, I don't see a simple way to encode the position to a value.

Answer 3

every item the implements the interface IEffect should override ToString & GetHashCode

ToString shold include unique state of the IEffect properties including the selected value GetHashCode should be ToString().GetHashCode()

and there u have a unique hash for each object based on your object inner data.

Answer 4

This should do the trick. Warning: Don't override GetHashCode with this method. GetHashCode should not mutate because an objects position in a parent entity has changed. Only use this trick if you have other plans for the hash code. Here is a rough sample of something that should do what you ask. This only shows how you would find the position of the current parent, but you could extend it to walk the tree until it has no parent.

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

Here is how I've done what I think you really need to do. This will walk the entire tree processing effets. No need to link to a parent unless you need to start in the middle of a tree. Of course, this is just my wild interpretation of what you might be trying to do.

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

    else
        HandleEffect(effect.ElseEffect);
}