File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/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


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
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: 95

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: 4343
    
    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: 95

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: 38033
    
  22
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: 95

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: 19654
    
  18

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: 38033
    
  22
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?
 
Similar Threads
getting the index of the closest value in an array that is sorted in reverse order
Head First Java HashSet
Project Euler problems with Scala
Parsing encoded data?
Conflict with the Lead Developer