ansaurus

Question

Searchable list of objects in Java

Answer 1

+2 A:

Wouldn't you use TreeMap instead of List using the ID as your Key?

Mike Cornell 2010-03-26 14:21:07

FYI, the reason I suggested TreeMap is because TreeMap is guaranteed to run contains, get and put in O(log n)

Mike Cornell 2010-03-26 14:34:19

if you don't need to have the keys ordered, then this is unnecessary

matt b 2010-03-26 15:02:10

The requirement was for logarithmic search, so I think it must be.

Mike Cornell 2010-03-26 15:06:58

The advantage of TreeMap is that you can retrieve the items in order by key. This was not stated as a requirement in the original question, though of course that doesn't prove it isn't a requirement. But the requirement for a logarithmic search is met by a HashMap. You don't need a TreeMap if that's the only issue.

Jay 2010-03-26 16:34:58

Since the user originally suggested List, it would seem order is required. But true, it was not explicitly stated.

Mike Cornell 2010-03-26 17:23:38

Answer 2

+4 A:

The various implementations of the Map interface should do what you want.

Just remember to override the hashCode() method of your Drug class if you plan to use a HashMap.

Etienne de Martel 2010-03-26 14:21:14

Not that I don't believe you, but remind me why hashCode() must be overridden? Isn't the default one pretty good?

Bart van Heukelom 2010-03-26 14:23:26

You only need to implement `hashCode` and `equals` only if you want to use your class as the **key** of a `Map` or if you want to put it in a `Set`. If you simply want to use it as the value of a `Map` then you don't need to implement them. Also: **If** you implement `equals()`, then you **must** implement `hashCode()` as well.

Joachim Sauer 2010-03-26 14:25:40

Having fine grained control over the hashcode you can guarantee that map entries are evenly distributed among buckets. The worst case scenario is when all entries land in the same bucket and the complexity of lookup becomes O(n).

mindas 2010-03-26 14:27:36

The default implementation just takes the address in memory to be the hash code. If you use your Drug object as a key, you could not do the following:myMap.put(new Drug("Whatever"), 23.42);myMap.get(new Drug("Whatever"));because both Drug instance have a different hashCode and the latter will return null. See http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode() for details.

Malax 2010-03-26 14:27:58

Assuming that the type of an ID is String, and that that is the key, there is no need (and no way) to override the `equals(Object)` and `hashCode()` methods.

Stephen C 2010-03-26 14:54:02

RE Malax: But bear in mind that this only applies if you are using your Object as the key, as Joachim notes. But normally the key is not the target object itself, but some identifier. In this case Christian says he has a "drug id". If this can be stored in a String or an Integer, as seems likely, then those classes already have generally good hashCode functions.

Jay 2010-03-26 16:30:58

@Malax: the default implementation does *not* just take the address in memory. It takes the identityHashCode (as defined by `System.identityHashCode()`) which *may* be based on the position in memory. Think of a 64bit JVM: how could a 32bit value **be** the position in memory in that case?

Joachim Sauer 2010-03-27 10:55:53

@Joachim, you are absolutely right, I omitted the whole identityHashCode part in my comment to keep it simple. But you are right. :-)@Jay: "If you use your Drug object as a key" is exactly what i wrote ;-)

Malax 2010-03-28 10:38:36

Answer 3

+1 A:

If searching by a key is important for you, then you probably need to use a Map and not a List. From the Java Collections Trail:

The three general-purpose Map implementations are HashMap, TreeMap and LinkedHashMap. If you need SortedMap operations or key-ordered Collection-view iteration, use TreeMap; if you want maximum speed and don't care about iteration order, use HashMap; if you want near-HashMap performance and insertion-order iteration, use LinkedHashMap.

kgiannakakis 2010-03-26 14:21:21

Answer 4

+2 A:

Due to the high number of entries you might consider to use a database instead of holding everything in memory.

If you still want to keep it in memory you might have a look at b-trees.

Patrick Cornelissen 2010-03-26 14:23:03

Answer 5

+1 A:

You could use any list, and as long as it is sorted you can use a binary search. But I would use a Map which searches in O(1).

idrosid 2010-03-26 14:23:14

Answer 6

+1 A:

public class Drug implements Comparable<Drug> {

    public int compareTo(Drug o) {
         return this.id.compareTo(o.getId());
    }
}

Then in your List you can use binarySearch

    List<Drug> drugList; <--- List of all drugs
    Drug drugToSearchFor; <---- The drug that you want to search for, containing the id
    // Sort before search
    Collections.sort(drugList);
    int index = Collections.binarySearch(drugList, drugToSearchFor);

    if (index >= 0) {
        return true;
    } else {
        return false;
    }

Shervin 2010-03-26 14:29:06

Answer 7

A:

I know I am pretty redundant with this statement, but as everybody said isnt this exactly the case for a Map ?

anilit99 2010-03-26 15:38:23

ansaurus

tags:

views:

answers:

Searchable list of objects in Java

related questions