Map/store run time ID for objects

Question

What I want to achieve: I need to obtain a run time (unique) id for "any object" (for classes either in java SE, classes I have created or classes provided by other third parties... any instance of a class).

Ideally it should be as easy as:

Map<Object, UUID> objId = new HashMap<>();
MyClassFoo foo = new MyClassFoo();
UUID fooId = objId.getOrElse(foo, UUID.randomUUID());
if (!objId.containsKey(foo)) {
 objId.put(foo, fooId);
}
// From here onwards whenever I need the runtime ID for foo I can get it from the map objId

The problem:

This won't work for mutable objects since my object can keep changing hence its hash code, and we all know the problems that would/may introduce when working with a map using a mutable object as key.

Besides such approach does not work due to the limitations like: you cannot use an ArrayList as a key if the ArrayList is a List of Lists containing itself, since the map will attempt to use its hashCode. The implementation of hash code for ArrayList requires calculating the hashCode of all its contained objects causing a stack overflow for self-contained lists.

What I need from the community: I need to know the most (or a couple of good proposals for alternatives to that map) efficient way to achieve what I want. I've considered a sorted List<Pair<Object, UUID>> and do some binary search on it whenever I need the id for an object, but besides making the implementation a bit more complex I'm also worried about the performance impact of such change (given that such list may contain from a few couple of objects up to several million).

Have I done my homework? I think so, besides considering possible alternatives (as the one mentioned above) I tried to find a different implementation of a map that fulfills my needs, but all of them seem to use the hashCode of the key object.

Is this an opinion based question? Well... yes, but I wouldn't like it to be labeled as such since what I am requesting are alternatives to solve my issue and the performance implication/aspects to consider for the implementation of such proposals.

P.S: I am working in the Java language but the concept of the problem can be applied independently of that.

• Kwebble: Why does your software need to assign a unique ID per object? Perhaps this stackoverflow.com/a/909861/4167 is good enough.
• Ordiel: Already gave it a try, but when you store it in the map the map simply uses the hashCode(). The reason I need a unique runtime ID is that I am working on a serialization tool
• kdgregory: "Working on a serialization tool" is a critical piece of information that was omitted from the question. It leads to additional questions such as: (1) do you need to maintain the map just for one serialization (to replace circular) references, or across serializations (to reduce size on stream), and (2) do you expect the objects to mutate between serializations (in which case #2 is not valid).
• kdgregory: And a question that could be an answer: have you considered matching on object identity? You would create an object that uses System.identityHashCode() for its hashCcode() implementation, and == for its equals(), then use the map to associate this object with a unique identifier. You'd of course also need to use WeakReferences to prevent out-of-memory conditions.
• Ordiel: I totally agree with you, I also consider that saying that is a valuable piece of information, but I'm enough of an old salt on stack exchange and I didn't want my question to fall on "Have you considered using X or Y other library to do that?". To answer your other question, the idea of such map containing ID's is to be used only once per serialization process but be capable of handling circular references across each individual request

Answer 1

You could place objects in a bucket by their concrete class. The class of an object cannot change after instantiation, and this will help reduce your search space immediately (if there is a pretty even distribution of object's classes). The second recommendation I will make is that you can still use Map<Object, UUID>. You should iterate over the entire map if you have a map miss, and update the object in the map if the hash has changed. Here's a bit of code to illustrate:

Map<Class, Map<Object, UUID>> ids = new HashMap<>();
// Create new id for object
UUID assignId(Object obj) {
 UUID uuid = UUID.randomUUID();
 if (!ids.containsKey(obj.getClass())) {
 ids.put(obj.getClass(), new HashMap<>());
 }
 ids.get(obj.getClass()).put(obj, uuid);
}
// Get id of object
UUID retrieveId(Object obj) {
 Map<Object, UUID> classMap = ids.get(obj.getClass());
 if (classMap == null) {
 return null;
 }
 UUID hit = classMap.get(obj);
 // if hit is non-null then the object's hashcode hasn't changed 
 // and search is fast
 if (hit != null) {
 return hit;
 }
 // obj has mutated since we stored its id, or obj doesn't have an id
 Iterator<Entry<Object, UUID>> itr = classMap.entrySet().iterator();
 UUID uuid = null;
 while(itr.hasNext()){
 Entry<Object, UUID> entry = itr.next();
 if (entry.getKey() == obj) {
 // we found our object
 uuid = entry.getValue();
 // remove the entry from the map (with the old hashcode)
 itr.remove();
 }
 }
 if (uuid == null) {
 // object doesn't have an id at all
 return null;
 }
 // reinsert the object into the map to get a new hash code
 // makes search faster next lookup (if the hashcode doesn't change)
 classMap.put(obj, uuid);
}

This algorithm will execute in O(1) time if the object's hashcode hasn't changed or O(n) if the hashcode has changed.

• Ordiel: I'll let you know how it turns out once I finish with the implementation

Answer 2

If it is feasible, you can inherent all your classes from a superclass having UUID as a readonly property equal to the hash value of the timestamp when it was instantiated plus some other identifier related to the original class type.

if your application is running on multiple machines, you can append the hash value of the server you are running on.

you can implement the UUID generator method in the superclass, and call it in constructors.

• Ordiel: I thought about that too, sadly it wouldn't work for classes I do not own :(
• A.Rashad: You can replace the inheritance model with a factory method, instantiating both your object and a twin object associated with it with two fields, the UUID, and an object containing your created object.
• Ordiel: I can't do that for the objects that are created within the objects my function will be passed.