I want to create a large (~300,000 entries) List of self defined objects of the class Drug.
Every Drug has an ID and I want to be able to search the Drugs in logarithmic time via that ID.
What kind of List do I have to use?
How do I declare that it should be searchable via the ID?
-
1What is the range of the IDs?Michael Myers– Michael Myers ♦2010-03-26 14:21:03 +00:00Commented Mar 26, 2010 at 14:21
-
1Any chance to put them in a DB and let it do the work with help of SQL/JDBC? This is undoubtely going to be more fast and efficient.BalusC– BalusC2010-03-26 14:21:30 +00:00Commented Mar 26, 2010 at 14:21
-
@BalusC only if the data is not changing too much. If he has to update everything in short intervals and persistence is not needed, then a DB won't make much sense. But my first thoughts are pointing towards a DB too.Patrick Cornelissen– Patrick Cornelissen2010-03-26 14:35:01 +00:00Commented Mar 26, 2010 at 14:35
Add a comment
|
7 Answers
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.
answered Mar 26, 2010 at 14:21
Etienne de Martel
37.2k10 gold badges95 silver badges119 bronze badges
8 Comments
Bart van Heukelom
Not that I don't believe you, but remind me why hashCode() must be overridden? Isn't the default one pretty good?
Joachim Sauer
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.
mindas
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).
Malax
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 java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode() for details.
Stephen C
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. |
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;
}
Comments
Wouldn't you use TreeMap instead of List using the ID as your Key?
5 Comments
Mike Cornell
FYI, the reason I suggested TreeMap is because TreeMap is guaranteed to run contains, get and put in O(log n)
matt b
if you don't need to have the keys ordered, then this is unnecessary
Mike Cornell
The requirement was for logarithmic search, so I think it must be.
Jay
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.
Mike Cornell
Since the user originally suggested List, it would seem order is required. But true, it was not explicitly stated.
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.
Comments
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.
answered Mar 26, 2010 at 14:23
Patrick Cornelissen
7,9987 gold badges51 silver badges74 bronze badges
Comments
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).
Comments
I know I am pretty redundant with this statement, but as everybody said isnt this exactly the case for a Map ?
