Generate the lowest ID number possible for every object instance - java

Question

I want to generate ID number for an object in the following rules: Each new object will get a unique ID number (the first one will be 1), and then each new object will get the lowest available ID number.

For instance if I declare 4 object Object 1 ID: 1 Object 2 ID: 2 Object 3 ID: 3 Object 4 ID: 4

then if I delete object number 3. so the next object that will be made will get ID: 3 and not 5.

what is the best way of doing that ID generator?

Answer 1

I assume you want to do it in Java. I suggest the following:

1. Have a sequence that is used to provide entities with IDs. It is quite simple and I think require no detailed explanation - it just returns 1, 2, 3, etc.

2. Now we need to handle deletion. Together with the sequence I'd suggest to have a SortedSet of IDs that was deleted and can be assigned to new entities.

3. Having this two structures together, act like:

   • If set is not empty, return its first value and remove it from a set. It will be the lowest value, because you use SortedSet.

   • If it is empty, just return next number from the sequence.

Of course, you'll need to handle atomicity of this operation and may encounter concurrency issues, but detailed discussion of it is a little bit offtopic for this question IMO.

Answer 2

You could have a ConcurrentHashMap<Integer, Boolean> to set the unique IDs to use. Use the Boolean value to check if they're used. Then, use a ConcurrentHashMap<YourObject, Integer> to store the desired object within its relevant ID. From this, you have to manually synchronize the addition/removal from both structures to always define the lowest key available to use.

Note that having all this is very costly and hard to maintain. It would be better to use a third party element (a embedded database maybe?) that handles all these problems for you.

Answer 3

_{Note: this is my way of doing it because I'm not privy to lists. If there's a list that behaves in a way to complete this problem without an algorithm, great. Don't downvote my answer just because it's unnecessary.}

I suppose you could have an ArrayList and just add IDs from it and always take the lowest one available.

So for example:

static ArrayList<Integer> ids = new ArrayList<Integer>();

public static void assignId() {
    boolean foundId = false;
    for (int i = 0; i < ids.size(); i++) {
        if (ids.get(i) < 0) { // if it's negative, it was removed before
            // make object ID to be i+1
            ids.set(i, i+1); // and add it to the list
            foundId = true;
            break;
        }
    }
    if (!foundId) { // can't find ID mid list to fill in
        ids.add(ids.size()+1); // so give it a brand new one
    }
}

public static void removeId(int id) {
    ids.set(id-1, -1); // negative value means it was removed
}

So what I've done is create a list that has positive values for IDs, and negative values in places where there used to be an id, but isn't anymore. The reason for this is so that if the value in the list is negative, we can just replace it. For example:

// assign five IDs (1 through 5)
assignId();
assignId();
assignId();
assignId();
assignId();

// print ids for testing
for (int id : ids) {
    System.out.print(id + ", ");
}
// outputs 1, 2, 3, 4, 5, 

// now remove the id 3
removeId(3);
removeId(2);

// print ids for testing
for (int id : ids) {
    System.out.print(id + ", ");
}
// outputs 1, 2, -1, 4, 5, 

assignId(); // give this new object a new id (should be 2 replacing -1)

// print ids for testing
for (int id : ids) {
    System.out.print(id + ", ");
}
// outputs 1, 2, -1, 4, 5, 

assignId(); // give this new object a new id (should be 3 replacing -1)

// print ids for testing
for (int id : ids) {
    System.out.print(id + ", ");
}
// outputs 1, 2, 3, 4, 5, 

assignId(); // give this new object a new id (should a brand new ID)

// print ids for testing
for (int id : ids) {
    System.out.print(id + ", ");
}
// outputs 1, 2, 3, 4, 5, 6,