If been working on legacy data import code in the last months with a lot of code searching for exisiting objects in lists. I realized I needed a different collection to speed up searching for identifiers and couldn’t find any standard collection that matches my needs. I basically need an index like Maps.uniqueIndex() from the Google Collections Library provides but it should be updating dynamically and not only be generated once.

To summarize my requirements:

• A List (ArrayList) which can be modified as usual
• A way to find objects (contains and get) in constant time by a custom attribute (like a HashMap)
• No reliance on equals() and hashcode() because they cover more attributes (an can not be changed)

The LinkedHashMap seems to almost fit the bill but it is not a true List and therefore not a great drop in replacement.

What I’m using right now is a wrapper around a List which maintains an additional HashMap to find objects by the index criterium. The index is automatically updated whenever the list is modified. This is an example on how I use it:

// function to index Persons by their social security number
Function<Person, String> getSsnrForPerson =
  new Function<Person, String>() {
    String apply(Person person) {
      return person.getSocialSecurityNumber();
    }
  }

To create an indexed list for an empty ArrayList<Person> with an index on a person’s social security number you can then easily use the Class UniqueIndexedList:

UnqiueIndexedList<Person, String> myList =
  UnqiueIndexedList.create(getSsnrForPerson);

Of course all the usual methods of the List<Person> interface can be used as usual:

myList.add(somePerson);
myList.add(anotherPerson);
myList.get(i);
myList.iterator();

Additionaly there are  methods to access objects by index:

boolean personIsInList = myList.containsByIndex("34897634853");

Person p = myList.getByIndex("34897634853");

The code for the list implementation currently resides here:

• IndexedList.java
• UniqueIndexedList.java

It is basically a hybrid of a List and a special index-Map and works well so far. I am sure that finding objects in list for a given attribute is a very common usecase. Why hasn’t anyone solved this yet? Are there (better) alternatives that I’ve missed?