Capacity adapting Java collections

Question

Are there any Java libraries for maps and sets that alter their representation strategy based upon the capacity? I have an application where we have many many maps and sets, but most of the time they are small, usually 6 elements or less.

As such we've been able to extract some good memory improvements by writing some specialized maps and sets that just use arrays for small sizes and then default to standard Java Sets and Maps for larger capacities.

However, rolling our own specialized versions of set and maps seems kind of silly if there is already something off the shelf. I've looked at guava and the Apache collections and they do not seem to offer anything like this. Trove sounds like it is more memory efficient than the JDK's collections in general, but it isn't clear if it will attempt to minimize memory usage like this.

Answer 1

You may want to look at Clojure's persistent data structures. Although the "persistent" part may be overkill for you, it does exactly what you are looking for and is still really fast. There is a PersistentArrayMap that is promoted to a PersistentHashMap once the collection exceeds 16 entires.