Hash Trie


Javascript Hash Trie

The hash trie is a persistent map data structure with good lookup and update performance.

This is a fork from HAMT that only uses array nodes of sparse Javascript arrays. Benchmarks show that this library performs well, even for large maps.

Hashtrie is faster than HAMT in some cases for gets and updates, but has significantly worse fold performance. HAMT index nodes are stored in a dense array, while hashtrie's sparse arrays have a lot of overhead for folds.

Node source is in dist_node/hashtrie.js

$ npm install hashtrie

Amd source is in dist/hashtrie.js

    paths: {
        'hashtrie': 'dist/hashtrie'
function(ht) {
var ht = require('hashtrie');
// empty table
var h = ht.empty;
// Set 'key' to 'value'
h = ht.set('key', 'value', h);
// get 'key'
ht.get('key', h); // 'value'
// The data structure is persistent so the original is not modified.
var h1 = ht.set('a', 'x', ht.empty);
var h2 = ht.set('b', 'y', h1);
ht.get('a', h1); // 'x'
ht.get('b', h1); // null
ht.get('a', h2); // 'x'
ht.get('b', h2); // 'y'
// set if an entry exists
var h = ht.set('b', 'y', ht.set('a', 'x', ht.empty));
ht.has('b', h); // true
ht.has('w', h); // false
// Get with default value
ht.tryGet('default', 'b', h); // 'y'
ht.tryGet('default', 'w', h); // 'default'
// modify an entry
h2 = ht.modify('b', \x -> x + 'z', h2);
ht.get('b', h2); // 'yz'
// remove an entry
h2 = ht.remove('y', h2);
ht.get('a', h2); // 'x'
ht.get('b', h2); // null
// Custom hash Function
// The main hashtrie API expects all keys to be strings. Versions of all API functions
// that take a `hash` parameter are also provided so custom hashes and keys can be used.
// Collisions are correctly handled
var h1 = ht.setHash(0, 'a', 'x', ht.empty);
var h2 = ht.setHash(0, 'b', 'y', h1);
ht.get('a', h2); // 'x'
ht.get('b', h2); // 'y'
// Aggregate Info
var h = ht.set('b', 'y', ht.set('a', 'x', ht.empty));
ht.count(h); // 2
ht.keys(h); // ['b', 'a'];
ht.values(h); // ['y', 'x'];
ht.pairs(h); // [['b', 'y'], ['a', 'x']];
// Fold
var h = ht.set('a', 10, h.set('b', 4, ht.set('c', -2, ht.empty)));
var sum = ht.fold@(\p, [key, value] -> p + value, 0);
sum(h); //12