What's the best way to search in this specific type of List?

[Avor Nadal]

Hello to everybody:

I'm facing the following situation. I'm receiving a long list of object arrays (java.util.List <Object []>) from a query to a database. Every object array has a length of 2, and the first slot stores an object which is unique, so it can be considered a key. Later, I'm running through a long loop, in which I need to search into such List for a specific key. This means a lot of array loops and comparisons.

One approach which I've thought about to reduce loops and comparisons, is to sort the List and use a binary search. But, since it's very a long List, I'd like to implement a better system.

I've been using the class java.util.HashMap for many years, but I didn't know about its exact internal behaviour until I dug into its source code and read some articles on the Internet some weeks ago. And I've to admit that I got astonished for such an intelligent and good implementation.

Because of it, now I've thought that I can make a HashMap based on the content of the List, using the first element of every array as the key and the second one as the value. Then, I would simply need to call the method get (Object key) to retrieve the value very fast. Do you believe that it's a good way to do this task?

Thank you a lot.

Edition # 1: I typed get (int index) by mistake. I meant get (Object key) .

[Matthew Brown]

That's exactly how I'd do it, assuming the Object is suitable to be used as a key in a HashMap*.

Note, though, that it would be get(Object key), not get(int index).

* That is, either you're retrieving via the Object itself, not a copy, or it has equals() and hashCode() suitably implemented.

[Avor Nadal]

Matthew Brown: Ops, you're right. I meant get (Object key) . I was in a rush, he he he.

The objects which act as keys are entity beans which have the methods hashCode () and equals () overridden, so I believe that I shouldn't have problems with that. Thanks for your help .

[Campbell Ritchie]

Depends how many times you need to search. If you do a linear search, it runs in O(n) time, so there will be on average n/2 comparisons before your pair is found. So it is quickest to do a linear search if you only want one search.
If you put the contents of your array into a Map, that will require n examinations of the elements (when they are "put" into the Map) and 1 comparison per pair sought (yes, "get" runs in constant tiem O(1)). So that would be n + m comparisons, where m is the number of searches.
If you sort your array, that runs in O(nlogn) time, and each binary search runs in O(logn) time . . .

Your pair of Objects, on one of which you are searching, exactly matches the usual contents of a Map, so it looks as if, for multiple searches, the Map will win by a large margin. You must ensure that the "key" class has a well-designed hashCode method, otherwise all the elements will end up in the same "bucket" and you will go back to linear time for each search.

for (Obect[] array : myList)
{
   myMap.put(array[0], array[1]); //Dependent on each array having the correct contents
}
 . . .
result = myMap.get(key123); //Can return null if the key isn't in the Map, or null is entered.

[Avor Nadal]

Campbell Ritchie: very interesting information. I'll take that into account for future reference. I thought about the cost of building the map, but had no idea about the "exact figures". Thank you too .

[Rob Spoor]

If the order is important, you may also want to check out LinkedHashMap. It's a HashMap that maintains insertion order.

[Campbell Ritchie]

Igor Nadal wrote:Campbell Ritchie: very interesting information. I'll take that into account for future reference. I thought about the cost of building the map, but had no idea about the "exact figures". Thank you too .

You're welcome

That sort of information is standard algorithms and data structures stuff, and is also appears in the documentation for HashMap.