AirConcurrentMap Space Efficiency

AirConcurrentMap is a Java ConcurrentNavigableMap that is more memory efficient above about 1K Entries than any library Java Map and has faster direct access at any size than ConcurrentSkipListMap. It out-performs all standard Java Maps for Iterating and has a proprietary threaded visitor capability that is faster than any library Map including streams. For more info, contact

In a very high-level way, AirConcurrentMap is a ‘big-data in-memory noSQL DBMS’. AirConcurrentMap implements the standard Java ConcurrentNavigableMap interface, so it is compatible with all other Java Maps and can be dropped in place anywhere. Because it is a NavigableMap, the key/value associations are in key order during iteration and the higher/lower/ceilng/floor direct accesses. Because it is a ConcurrentMap, all access is thread-safe and concurrent without locks, thereby activating multiple CPU cores for maximum compute speed. See the wiki page about ConcurrentMaps: Java_ConcurrentMap and the extensive performance testing in AirConcurrentMap_Performance_Testing.pdf. AirConcurrentMap also provides the proprietary very fast  VisitorsAndThreadedVisitors ordered scan techniques.

AirConcurrentMap allocates in 8KB blocks

AirConcurrentMap allocates memory in blocks of very roughly 8KB, so as it grows, it becomes more and more efficient, eventually reaching 50% to 70% improvement or more over the other standard Java Maps. In fact an AirConcurrentMap will quickly reach about 39 Bytes per entry, while ConcurrentHashMap or ConcurrentSkipListMap, the two standard library Java Maps. take about 59 to 65 Bytes per entry, which is similar to HashMap and TreeMap. Some of this space is used by the key and value objects, and AirConcurrentMap’s own internal structures are very nearly minimal, consisting of almost only two references. Future versions of AirConcurrentMap will optimize these internal structures for primitive types as well, allowing the key and value Objects to be avoided – these Objects are relatively large compared to the primitive types such as long and int.

AirConcurrentSet is even more efficient

AirConcurrentSet, which uses most of the same technology as AirConcurrentMap, can avoid the space taken by the value references as well. This is not so in almost all other Set implementations, which simply use the corresponding Map, with a placeholder value.

Efficiency versus Size

Here is a graph showing the relative efficiency as a function of size for the Java Maps AirConcurrentMap, ConcurrentHashMap and ConcurrentSkipListMap. These are typical curves for the non-concurrent Java Maps as well: HashMap and TreeMap. The x axis is logarithmic, but a linear x-axis would show better the practical space taken in memory as the Java Map grows. The logarithmic x-axis allows the full spectrum of use cases to be seen. Note that the red line, AirConcurrentMap, becomes very efficient above about 1K entries and the total space used by the AirConcurrentMap Java Map in large or memory-constrained system will be minimal.


Continuous Effective Space Reclamation

Many Java Maps are crude at space management. For example, the Java HashMap or ConcurrentHashMap do not return the table part for re-use, and only the list entries in each bucket are garbage collected after remove(). Hence a HashMap or ConcurrentHashMap that even temporarily stores many entries will become a hidden space leak that is almost impossible to identify, because the table part doubles in size on each rehash during growth. Some simple Java Maps pre-allocate a fixed space. AirConcurrentMap continuously minimizes memory use to keep the efficiency high even when there are concurrent puts or removes or iterators or other scanning. Client code does not need to invoke any kind of compression method.

Low latency and no rehashing

While ConcurrentHashMap and HashMap cause occasional rehashes and significant delays, AirConcurrentMap has a smooth put() and remove(). These hash-based Maps contain an internal table of references to linked lists of entries, and these tables need to be grown occasionally as the Map grows so that the linked lists remain only a few entries long. As the Map grows, the tables are normally doubled in size as needed and all entries are moved from table to table. The doubling and re-hashing becomes very slow when the map is large.