Parentheticals & Excursions

Building on the perfect minimal hash I’ve developed for Java String objects, I’ve developed an memory efficient implementation of Java’s Map interface.

View the map source code in SVN

The map implementation is not general purpose, it’s specifically targeted to situations where:

• The map is keyed by strings; the valid keys are known ahead of time.
• The map values are, on average, anticipated to be fairly dense (ie. you don’t have situation where the map could contain any of several thousand keys, but only contains one value)
• There will be many map instances with the same keys.
• Performance comparable to that of a ‘HashMap’ is acceptable.

Even given these constraints, I frequently encounter situations where all of these apply:

• High volume HTTP services where values need to be parsed out of the query string and bundled into a map.
• Data querying APIs where query parameters need to be supplied via Map for substitution into a query.
• Proxy implementations of setter/getter interfaces that are backed by a Map of values.

The implementation stores the set of valid keys in an object that can be shared between ‘like’ maps. The keys are hashed perfectly so that the map values can be stored directly into a single object array; no entry objects are required. This means that the memory required to store large numbers of similar maps can . Furthermore, none of the basic map operations (put/get/contains etc.) performs any memory allocation. This means that for many applications both memory overhead and object churn is minimal.

From the javadocs:

Unlike regular Map implementations, there is no default, or copy, constructor. Instead the map must be constructed around a set of possible String keys. Only the keys supplied to a constructor may be used in the maps it constructs. Re-using constructors (by repeatedly using them to create ParameterMap instances) minimizes the memory required to store the map. Furthermore, the only map operations that allocate new objects are those methods that required to do so by the Map interface; in-short, object creation strictly minimized. This makes the class ideal for environments where reducing GC overhead is important.

The source code is under the Apache 2.0 licence, built with Maven, and is available from my website’s google code project:

http://code.google.com/p/tomgibara/