I am creating a unique "key" object type for a tree, we will call this object type a TreeCoordinate.
A tree in this case is a fairly standard mapping of nodes from parent to children where each child holds a reference to the parent. The parent holds a list of children based on their index. A node can have zero to N number of children.
Therefore, any position in the tree can be mapped to an exact array of integers representing an ordered list of indices, which will have no collision and can be reliably used to look up the object at the given coordinate in the tree. The code of an equality check would look like this:
TreeCoordinate lefttest = new(){Value = [0,3,1]};
TreeCoordinate righttest = new(){Value = [5,3,1,0]};
bool b = Equals(lefttest,righttest); //False
public bool Equals (TreeCoordinate left, TreeCoordinate right)
{
if(left.Length != right.Length) return false; //fast check
foreach (uint i in left.Value) //Value is uint[]
{
if(i != right.Value[i]) return false;
}
return true;
}
The equality check is easy. Now I would like to get a hash code.
The issue I see is that the default .Net Core implementation of GetHashCode() is non-deterministic when called in different program executions, but for my app logic's purpose, I want a deterministic hash that is a reliable representation of the index-based coordinate value.
I thought I could just append each position in the coordinate to the previous, i.e. [0,3,1] becomes 031, but that's not correct as that could mean node at [0,31] or node at [0,3,1] since index could be any length integer.
So it would mean that I have to hash a separator as well.
Now it seems I need to hash an array of char and not uint. Which I don't want to get into dealing with encoding systems and cultural specific chars.
Do you have any guidance on how I can create this deterministic hash of a TreeCoordinate data structure?
EDIT: I'm thinking that given an array of uint, I can string-ify the array into a A-Za-z prefix + uint. This would give me a logical separator with the ability to express a nested coordinate 52 levels deep, which I think would cover all of my use cases.
So [0,3,1] becomes A0B3C1, [5,0,4,1,6] becomes A5B0C4D1E6. This would help enforce complete addresses, (must start with A) or partial (Must start with {A-Za-z}).
At which point I use any of the given hashing algorithms.
Edit: @DocBrown is correct in his assumption I am misunderstanding. The refinement of the question based on your help: I need a deterministic encoding for business logic and a standard hash for use in dictionaries, etc.
I thought that a hashing algorithm could suffice as an encoding scheme, because there’s a clear deterministic definition of equality for the coordinate, which should have an equally deterministic mapping to an encoded version of itself.
I understand now conversion to an int during a hash will fundamentally introduce some acceptable potential for a collision due to the pidgeonhole principle.
Another commenter discussed fitting nodes into a byte, which is the kind of discussion I hoped to foster, because this is intended to be a simple struct type with low memory overhead, and not allocating additional strings is preferable.
If we hash some sort of encoding of bytes, that’s great and it avoids hashing an array of chars ostensibly extracted from a string. I just needed some direction on how to go from the array of uint to a low memory lightweight struct encoding. Then I can then completely satisfy equality checks with implementing GetHashCode().
GetHashCode()implementation, as most hash functions, is fully deterministic - the same input always leads to the same output. Hence I don't understand what you are after.