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.

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.

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.