Search using two keys in an arrayList

Question

Hi all,

I would like to implement a fast search on an ArrayList of objects. These objects consist of an int oldId, int newId and int inList, among with other things.

Now, I tried implementing a binary search using the Collections.binarySearch on my list, but the problem is I need to search using the oldId and inList, to get the newId from the corresponding object. Example: I have oldId = 9 and inList = 1, and try to get the newId that has been assigned somewhere else. Essentially mapped the oldId-newId's and grouped them. There may be duplicate oldId's but they must be in different lists, and have unique newIds.

Do you think it would be better to use a hashmap for these map objects? Or else, is there a solution (maybe a comparator for the objects) to get the newId's from the oldId and inList info. I am also looking for a fast search algorithm.

Thanks a lot for helps, I appreciate ideas.

Here is a comparator I have written for the binary search, however I couldn't figure out how to add the inList info here.

public class CompareTermId implements Comparator <MObj> {

public CompareTermId(){}

public int compare(MObj a, MObj b){

    if(a.oldTermId < b.oldTermId) return 1;
    else if(a.oldTermId > b.oldTermId) return -1;
    else return 0;
}

}

Answer 1

I think it'd be better to encapsulate all of it into a single class and use List and Comparator to find them.

Answer 2

If you make your comparator look like this:

public int compare(MObj a, MObj b) {
    if (a.oldTermId < b.oldTermId) return 1;
    else if (a.oldTermId > b.oldTermId) return -1;
    else if (a.inList < b.inList) return 1;
    else if (a.inList > b.inList) return -1;
    else return 0;
}

You should be golden, even for using the binarySearch methods. This comparator will sort items first by their oldTermId and then by their inList value, so that two items with the same oldID and different inList values are regarded as different.

Answer 3

As you have invited I am going to recommend HashMap :)

The reason is because HashMap provides effectively constant time lookups for a single key. If you can make a Map<Id, Map<InList, Id>> oldIdToNewIdMap = new HashMap<InList, Map<Id,Id>>(), then you can lookup as Id newId = oldIdToNewIdMap.get(inList).get(oldId).