Efficient look-up in a List

Question

I have a situation whereby I'm populating an ArrayList with "TransactionEvent"s. TransactionEvent has a property "transaction ID". In the large majority of cases each new event has a transaction ID greater the previous event's ID - However, this is not guaranteed; i.e. the data is almost sorted.

My question is this: How can I perform fast look-ups based on transaction ID? My current idea is to call Collections.binarySearch(...) and if this fails then perform a linear search. However, I notice the Javadoc states that the result of binarySearch is undefined is the data is unordered so I may have to roll my own implementation.

Additional:

• I have tried using a map of index -> transaction ID but this approach is flawed because whenever an list element is updated / deleted I have to rebuild the entire map; i.e. any gains are erased by this.
• This is not a case of premature-optimisation: The List is the basis for a TableModel currently performing very slowly when containing a large number of rows (100,000).

Any help appreciated.

Answer 1

You could keep the ArrayList sorted by searching for the insertion point as you add each TransactionEvent. Collections.binarySearch returns

index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Once you search for the insertion point you can use the ArrayList add(int index, Object element) method instead of just adding to the end of the list as you would normally. This will slow down each insertion by a small factor, but it will enable you to use binary search for fast look-up.