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

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.