aspose file tools*
The moose likes Java in General and the fly likes What's the best way to search in this specific type of List? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "What Watch "What New topic
Author

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

Avor Nadal
Ranch Hand

Joined: Sep 15, 2010
Posts: 105

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
Bartender

Joined: Apr 06, 2010
Posts: 4420
    
    8

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
Ranch Hand

Joined: Sep 15, 2010
Posts: 105

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
Sheriff

Joined: Oct 13, 2005
Posts: 39393
    
  28
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.
Avor Nadal
Ranch Hand

Joined: Sep 15, 2010
Posts: 105

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
Sheriff

Joined: Oct 27, 2005
Posts: 19718
    
  20

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39393
    
  28
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: What's the best way to search in this specific type of List?