CODEWITHSUNDEEP
javalistsearch
Christian
Christian

Reputation: 26437

Searchable list of objects in Java

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?

Upvotes: 9

Views: 3825

Answers (7)

anilit99
anilit99

Reputation: 597

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

Upvotes: 0

Shervin Asgari
Shervin Asgari

Reputation: 24517

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;
    }

Upvotes: 3

idrosid
idrosid

Reputation: 8029

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).

Upvotes: 1

Patrick Cornelissen
Patrick Cornelissen

Reputation: 7958

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.

Upvotes: 2

kgiannakakis
kgiannakakis

Reputation: 104196

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.

Upvotes: 2

Etienne de Martel
Etienne de Martel

Reputation: 36995

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.

Upvotes: 4

Mike Cornell
Mike Cornell

Reputation: 6069

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

Upvotes: 2

Related Questions