Repository files navigation

This is a Java port of a concurrent trie hash map implementation from the Scala collections library. It is almost a line-by-lineconversion from Scala to Java.

Idea + implementation techniques can be found in these reports written by Aleksandar Prokopec:

• http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
• http://lamp.epfl.ch/~prokopec/ctries-snapshot.pdf - a more up-to-date writeup which describes the snapshot operation

The original Scala implementation can be found here and is a part of scala.collection.concurrent:

• Scala implementation

Some of the tests and implementation details were borrowed from this project:

• https://github.com/flegall/concurrent-hash-trie

Implementation status :

• The given implementation is complete and implements all features of the original Scala implementation including support forsnapshots.
• Wherever necessary, code was adapted to be more easily usable in Java, e.g. it returns Objects instead of Option asmany methods of Scala's collections do.
• This class implements all the ConcurrentMap & Iterator methods and passes all the tests. Can be used as a drop-in replacementfor usual Java maps, including ConcurrentHashMap.

ctrie is a lock-Free Concurrent Hash Array Mapped Trie.

A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie.

It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operationsand is memory-efficient.

It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations.The cost of evaluating the (lazy) snapshot is distributed across subsequent updates, thus making snapshot evaluation horizontally scalable.

The original Scala-based implementation of the Ctrie is a part of the Scala standard library since the version 2.10.

More info about Ctries:

• http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
• http://lamp.epfl.ch/~prokopec/ctries-snapshot.pdf - a more up-to-date writeup (more coherent with the current version of the code) which describes the snapshot operation

This library is licensed under the Apache 2.0 license.

Usage of this library is very simple. Simply import the class com.romix.scala.collection.concurrent.TrieMap and use it as a usual Map.

import com.romix.scala.collection.concurrent.TrieMap;Map myMap = new TrieMap <Object, Object> ();myMap.put("key", "value");

Use a usualmvn clean install

The prebuilt binaries of the library are available from Maven central. Please use the following dependency in your POM files:

<dependency><groupId>com.github.romix</groupId><artifactId>java-concurrent-hash-trie-map</artifactId><version>0.2.23</version></dependency>

This library is self-contained. It does not depend on any additional libraries. In particular, it does not require the rather big Scala'sstandard library to be used.