Java Algorithm String-ID-generation hierarchical parent child

Question

What is a good algorithm to generate unique IDs to be put into a Map<String, Entity> with Entity being a container/folder class that can contain other Entities and String being the ID? I think when generating a new Entity it should always use the ID of its parent, so right now what I do is

(Math.abs((parentName+entityName).hashCode())).toString;

But it seems pretty inefficient as the ID can be a String but may not contain "-", so it contains only numbers when it may as well contain letters and Math.abs halves the number of possible IDs. Oh, and the ID has to be of same length (8 letters). It has only to function as a key in the map and inside an XML-file and does not have to be secure.

Answer 1

There doesn't seem to be any advantage to including the parent id in the child id. A potential advantage of this would be to find all children by their parent id (i.e. return all ids that start with parent_id), but you're hashing the concatenated id and you have a max id length which makes this approach infeasible.

If your keys don't have to be secure then a counter would be efficient and guarantee uniqueness. A sample implementation would be to generate ids composed of case-sensitive alphanumerics, which would give you about 10^14 ids (you can also add special characters to increase the number of ids). You'll need an array of 62 characters: indices 0-25 have lowercase letters, indices 26-51 have uppercase letters, and indices 52-61 have numbers. You'll also need a state array of 8 integers (or shorts or bytes), initialized to all 0's. To retrieve an id, use the state array to look up characters in the character array and concatenate them together (so a state of {0, 1, 2, 0, 1, 2, 0, 1} generates an id of "abcabcab"); then increment the 0th index of the state array, if this results in a number greater than 61 then set the 0th index to 0 and increment the 1st index of the state array, if this results in a number greater than 61 then set the 1st index to 0 and increment the 2nd index of the state array, etc.

I suggest that you use a StringBuilder to concatenate the substrings, otherwise you're going to generate a lot of garbage strings. You might also be able to replace the state array with a StringBuilder, using StringBuilder#replace in place of the int/short/byte increment operations.

---

If your application is multi-threaded then the counter can become a bottleneck. One way to fix this is for each worker thread to reserve either 62 or 62^2 ids, for example: ID_Thread is the thread with the id generator, and its getBatchId method is synchronized and returns a copy of the state array. ID_Thread increments the 2nd index of the state array (not the 0th index), if this results in a number greater than 61 then it sets the 2nd index to 0 and increments the 3rd index, etc. Meanwhile, Worker_Thread has called getBatchId and now has a copy of a state array; it uses this to generate ids, after which it increments the 0th index of the state array, if this results in a number greater than 61 then it sets the 0th index to 0 and increments the 1st index, and if this results in a number greater than 61 then it calls getBatchId for a new state array. This means that the Worker_Thread instances only need to call a synchronized method for one out of every 62^2 ids.

An alternative multi-threaded implementation would be for Id_Thread to continually generate ids and place them in a BlockingQueue (with maximum queue size of, say, 32), with the Worker_Thread instances pulling ids from this queue.