Unique Id for a collection of objects

Imagine that I have a tree of three levels

    |->B->C
A-->|  |->D
    |------->E->F
             |->G

Then, I have another process (TreeToPathProcess) that calculates/generates me 4 paths from the root to the leaves :

A->B->C
A->B->D
A->E->F
A->E->G

Now, I am exposing an endpoint where my clients ask for an id for each path (too complicated to explain the whole requirement). I have to be able to associate an Id to each path, and always the same id for the same path.

Exemple :

The first time I run TreeToPathProcess it generates me the following :

ID=100, path=A->B->C
ID=101, path=A->B->D
ID=102, path=A->E->F
ID=103, path=A->E->G

Next time I run the same process, I need to get the same result as precedent.

Is that possible ?

Have you any idea that helps me to solve this issue ?

Just to clarify, in my real paths I get many hundred of elements.

Fundamental informatics preamble

We immediately have a bit of a pigeonhole principle issue here. Presumably you're thinking about a specific format for these IDs (perhaps, an int). Some formats (int, long, double, and fixed-width String, for example) have a delimited set of values - for example, int has 4 billion values but no more than that: From -2^31 up to +2^31. Whilst 4 billion is a lot, your tree structure has an infinite space (that means: Any particular tree structure could have any of an infinite amount of nodes in it. Not that all trees are infinitely large), and therefore, in theory what you want is therefore impossible - you can't map an infinite universe onto a finite one; not without overlap / error.

In practice, the same principle applies to UUIDs (128-bit, so, finite universe), which is used by all sorts of unrelated parties for infinite universes. And yet, UUIDs are fine; nobody is complaining about errors or collisions. The saving grace is pragmatics: The odds that 2 computers both rolling up a random 128-bit value ending up at the same value are many, many orders of magnitude smaller than errant cosmic rays causing bit flips in your memory banks and cuasing problems that way; it's just not going to happen / so unlikely, you should be worrying about other things. Even with all the world rolling up UUIDs all the time, no colissions.

Still, it's an important distinction here: Do you want your IDs to theoretically be able to cover even infinite trees (which implies more or less that a list of IDs is all you need to completely reconstitute the entire tree, after all, if there is a unique mapping for any imaginable tree node to an ID, then therefore I can 'map back' any ID back to the exact tree node, without having the tree). This is all a lot of highly fundamental informatic wonkery to push you towards a conclusion that you might initially find distasteful:

The best answer is highly likely to involve a hashing algorithm that cannot actually guarantee uniqueness; but for all practical purposes, is unique.

The above wonkery is just highlighting that any attempt to go: "Well, if you just...." to get around that restriction, is merely indicative of a lack of understanding of just (heh) how much difficult is hiding behind "just" in that sentence.

Mapping tree paths to IDs

This gets us to the right answer (or, rather, if this isn't right, what you do want is either incredibly complicated unless tree paths have serious limitations, such as 'never has a depth more than 4 and each node can be described by a single uppercase ASCII letter' - in which case you need to ask a new question and add these limits to it):

You first describe the path in a unique fashion. If path nodes are literally 'strings', you can for example simply concatenate these strings with slashes in between, i.e. turn what you have in your snippet is ID=100 as the string "/A/B/C".

Then, hash that string. You could use java's string hasher (just "/A/B/C".hashCode()), which produces 32-bit output. Alternatively, use a hash algorithm that is somewhat more robust, such as SHA-256. This produces (hence the name) 256-bit output which is rather large (encoding that using Base64, you end up with 43-length string). If you want it smaller, just XOR bit ranges on top of each other, e.g. if you want 128-bit output just XOR the top 128 bit onto the bottom 128 bit. Base64-ing that, you end up with 12 characters. If you want IDs to be numeric - easiest answer is to apply this 'XOR on top of each other' one more time, to end up with 64 bits, which fits in a long.

It does not guarantee uniqueness. However, in practice, it will be, unless someone is messing with you and intentionally picking strings that are known to collide. If you want to fight this somewhat, it can help to hash in some additional static data, such as the path depth (i.e. hash up "/1A/2B/3C").

This looks something like:

public long pathToId(List<Node> nodesInPath) {
  Charset charset = StandardCharsets.UTF_8;
  MessageDigest digest = MessageDigest.getInstance("SHA-256");
  for (int i = 0; i < nodesInPath.size(); i++) {
    digest.update((byte) '/');
    digest.update((byte) i);
    digest.update(nodesInPath.get(i).getName().getBytes(charset));
  }
  byte[] h = digest.digest();
  long out = 0;
  // hash all bytes into the first 8 (longs are 8 bytes)
  for (int i = 8; i < h.length; i++) h[i % 8] ^= h[i];
  return ByteBuffer.wrap(h).getLong();
}

Note, of course, that the preamble cuts both ways: By hashing, you make the job of going from a hash value (an ID) back to the indicated tree path difficult - essentially you have to calculate all IDs first. Whichever tree path has the same ID - that's the path they meant with that ID. Presumably that's what you wanted.

I want perfect mapping

Okay, just, shove slashes in between. Voila. Your path with id 100 should turn into the ID "/A/B/C". Yes, this means the entire path data is in the 'ID' and the ID can theoretically be infinitely large. Certainly they aren't compact. But, if you don't like it - reread the Fundamental informatics preamble which proves you can't have perfect mapping to short IDs.

Why not using a UUID attached on each node to build your path ?
Too much long, really ?

Why not using a randomly unique generated string then, lets say using between 5-10 characters ?

An unique path could be build from each node randomly generated string :

path : "/"+node1.rsg1+"/"+node2.rsg2+"/"+node3.rsg3 // rsg: randomly generated string

For a tree of only 3 levels, I don't think your use case as a blocking stuff.