Java equivalent of C++ std::map?

Question

I'm looking for a Java class with the characteristics of C++ std::map's usual implementation (as I understand it, a self-balancing binary search tree):

1. O(log n) performance for insertion/removal/search
2. Each element is composed of a unique key and a mapped value
3. Keys follow a strict weak ordering

I'm looking for implementations with open source or design documents; I'll probably end up rolling my own support for primitive keys/values.

This question's style is similar to: Java equivalent of std::deque, whose answer was "ArrayDeque from Primitive Collections for Java".

Answer 1

The closest class to a binary tree in the standard Java libraries is java.util.TreeMap but it doesn't support primitive types, except by boxing (i.e. int is wrapped as an Integer, double as a Double, etc).

java.util.HashMap is likely to give better performance for large maps. Theoretically it is O(1) but its precise performance characteristics depend on the hash code generation algorithm(s) for the key class(es).

According to Introduction to Collections: "Arrays ... are the only collection that supports storing primitive data types."

Answer 2

You can take a look at commons-collections FastTreeMap as well.

I doubt you will find many collections that support primitive types without boxing, so just live with it. And that is not necessarily needed, because of autoboxing.

If you really want to use primitive (after making benchmarks that show insufficient performance!), you can see the source of the FastTreeMap and add methods for handling primitives.

Answer 3

ConcurrentSkipListMap is a sorted map backed by a skip list (a self-balancing tree-like structure with O(log n) performance). Generally the bounds on CSLM are tighter than TreeMap (which is a self-balancing red-black tree impl) so it will probably perform better, with the side benefit of being thread-safe and concurrent, which TreeMap is not. CSLM was added in JDK 1.6.

Trove has a set of collections for primitive types and some other interesting variants of the common Java collection types.

Other collection libraries of interest include the Google Collection library and Apache Commons Collections.