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) .
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.
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 .
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 .
That sort of information is standard algorithms and data structures stuff, and is also appears in the documentation for HashMap.