2 =============================
4 This is a Java port of a concurrent trie hash map implementation from the Scala collections library. It is almost a line-by-line
5 conversion from Scala to Java.
7 Idea + implementation techniques can be found in these reports written by Aleksandar Prokopec:
8 * http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
9 * http://lamp.epfl.ch/~prokopec/ctries-snapshot.pdf - a more up-to-date writeup which describes the snapshot operation
11 The original Scala implementation can be found here and is a part of scala.collection.concurrent:
12 * [Scala implementation](https://github.com/scala/scala/blob/930c85d6c96507d798d1847ea078eebf93dc0acb/src/library/scala/collection/concurrent/TrieMap.scala)
14 Some of the tests and implementation details were borrowed from this project:
15 * https://github.com/flegall/concurrent-hash-trie
17 Implementation status :
18 * The given implementation is complete and implements all features of the original Scala implementation including support for
20 * Wherever necessary, code was adapted to be more easily usable in Java, e.g. it returns Objects instead of Option<V> as
21 many methods of Scala's collections do.
22 * This class implements all the ConcurrentMap & Iterator methods and passes all the tests. Can be used as a drop-in replacement
23 for usual Java maps, including ConcurrentHashMap.
26 What is a concurrent trie hash map also known as ctrie?
27 ========================================================
28 ctrie is a lock-Free Concurrent Hash Array Mapped Trie.
30 A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie.
32 It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations
33 and is memory-efficient.
35 It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations.
36 The cost of evaluating the (lazy) snapshot is distributed across subsequent updates, thus making snapshot evaluation horizontally scalable.
38 The original Scala-based implementation of the Ctrie is a part of the Scala standard library since the version 2.10.
40 More info about Ctries:
42 - http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
43 - 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
47 ===============================
49 This library is licensed under the Apache 2.0 license.
53 ===============================
55 Usage of this library is very simple. Simply import the class com.romix.scala.collection.concurrent.TrieMap and use it as a usual Map.
57 import com.romix.scala.collection.concurrent.TrieMap;
59 Map myMap = new TrieMap <Object, Object> ();
60 myMap.put("key", "value");
64 ===============================
66 Use a usual `mvn clean install`
68 Using the library with Maven projects
69 =====================================
70 The prebuilt binaries of the library are available from Maven central. Please use the following dependency in your POM files:
73 <groupId>com.github.romix</groupId>
74 <artifactId>java-concurrent-hash-trie-map</artifactId>
75 <version>0.2.1</version>
80 =====================================
81 This library is self-contained. It does not depend on any additional libraries. In particular, it does not require the rather big Scala's
82 standard library to be used.