PANTHEON.tech :: TrieMap

Java implementation of a concurrent trie hash map from Scala collections library

License

License

Categories

Categories

Ant Build Tools
GroupId

GroupId

tech.pantheon.triemap
ArtifactId

ArtifactId

triemap
Last Version

Last Version

1.2.0
Release Date

Release Date

Type

Type

bundle
Description

Description

PANTHEON.tech :: TrieMap
Java implementation of a concurrent trie hash map from Scala collections library
Project URL

Project URL

https://github.com/PantheonTechnologies/triemap
Project Organization

Project Organization

OpenDaylight
Source Code Management

Source Code Management

https://github.com/PantheonTechnologies/triemap

Download triemap

Dependencies

provided (4)

Group / Artifact Type Version
org.slf4j : slf4j-api jar 1.7.28
org.eclipse.jdt : org.eclipse.jdt.annotation jar 2.2.400
com.github.spotbugs : spotbugs-annotations Optional jar 3.1.12
org.gaul : modernizer-maven-annotations jar 2.1.0

test (5)

Group / Artifact Type Version
org.slf4j : slf4j-simple jar 1.7.28
org.hamcrest : hamcrest jar 2.2
org.hamcrest : hamcrest-library jar 2.2
junit : junit jar 4.13
org.mockito : mockito-core jar 3.3.3

Project Modules

There are no modules declared in this project.

Build Status Coverage Status CII Best Practices FOSSA Status Code Quality: Java Total Alerts Maven Central Javadocs License

About

This is a Java port of a concurrent trie hash map implementation from the Scala collections library. It used to be an almost line-by-line conversion from Scala to Java. These days it has been refactored to be Java 8 friendly and make some original assertions impossible via refactoring.

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

The code origins can be tracked through these links:

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

Implementation status :

  • The given implementation is complete and implements all features of the original Scala implementation including support for snapshots.
  • Wherever necessary, code was adapted to be more easily usable in Java, e.g. it returns Objects instead of Option as many 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 replacement for usual Java maps, including ConcurrentHashMap.
  • The code take advantage of Java 8 to supplant Scala constructs
  • The implementation is a Java 9+ JPMS module and can easily be depended upon by other modules

What is a concurrent trie hash map also known as ctrie?

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 operations and 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:

License

FOSSA Status

Usage

Usage of this library is very simple. Simply import the class tech.pantheon.triemap.TrieMap and use it as a usual Map.

    import tech.pantheon.triemap.TrieMap;

    Map<String, String> myMap = TrieMap.create();
    myMap.put("key", "value");

Building the library

Use a usual mvn clean install

Using the library with Maven projects

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

    <dependency>
        <groupId>tech.pantheon.triemap</groupId>
        <artifactId>triemap</artifactId>
        <version>1.0.6</version>
    </dependency>

External dependencies

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

tech.pantheon.triemap

PantheonTechnologies

PantheonTechnologies is now @PANTHEONtech

Versions

Version
1.2.0
1.1.0
1.0.6
1.0.5
1.0.4
1.0.3
1.0.2
1.0.1
1.0.0