Fastest and most efficent way of seaching a key-value pair in Java?

views:

195

answers:

+8 Q:

Fastest and most efficent way of seaching a key-value pair in Java?

DISCLAIMER:
THIS QUESTION WAS NOT MEANT TO BE ARGUMENTATIVE!!!!!!!

What is fastest and less memory draining way of searching a key-value pair? I will be storing items in a key-value like relation and I need to access them quickly. Should I use a SQLite database? A Map? A Hashtable? A HashMap? Please give some advantages/disadvantages of using whatever method of searching.

+8 A:

Any hash-based Map structure is the way to go as long as your hash function for the key is efficient. You can use value id:s as the result for the lookup to conserve memory during search.

If your data is already in database though, you can leave this search entirely to the RDBMS, after all they're made for this stuff.

Esko 2010-06-18 08:58:16

+6 A:

If your data is in memory, Maps in general are your friends - they are meant for this.

Don't use a Hashtable however. It is much slower than newer Map implementations. because its methods are synchronized, which most of the time is not needed (and when needed, there is a much better alternative - see below).

In single-threaded context, HashMap is probably going to be OK.

If you need thread safety, use a ConcurrentHashMap.

Péter Török 2010-06-18 09:01:51

HashTable is NOT synchronized and faster than ConcurrentHashMap in single-threaded-environments while it does not have any locking !If the access to the map is multithreaded ConcurrentHashMap is really the best solution.

Tobias P. 2010-06-18 12:48:03

@Tobias, "Unlike the new collection implementations, Hashtable is synchronized" - from http://java.sun.com/j2se/1.5.0/docs/api/java/util/Hashtable.html

Péter Török 2010-06-18 13:03:45

Since we're talking about semantics... "`ConcurrentHashMap` implementation performs better than `HashMap` in nearly all situations. It also allows for simultaneous concurrent reads and writes, and it has methods supporting common composite operations that are otherwise not thread safe. If Java 5 is the deployment environment, start with `ConcurrentHashMap`." *Clean Code - A Handbook of Agile Software Craftsmanship, Robert C. Martin, p.183*

Esko 2010-06-18 13:16:26

@Esko, good find, I didn't remember that :-) However, the difference seems to be negligible. Says _Java Generics and Collections_, ch. 16.4.1: "Disregarding locking overheads such as those just described, the cost of the operations of `ConcurrentHashMap` are similar to those of `HashMap`". It recommends `HashMap` for single threaded use.

Péter Török 2010-06-18 13:26:58

@Péter Török: Ah right, i was talking of HashMap not HashTable, which is nor synchronized and therefore the best solution for single-threaded-environments. Java Concurrency in Practise too recommends non-locking collection if locking is not needed.

Tobias P. 2010-06-18 13:38:08

ansaurus

tags:

views:

answers:

Fastest and most efficent way of seaching a key-value pair in Java?

related questions