BeniBela online


Hash Array Mapped Trie (HAMT)

A HAMT is a hashmap/set stored as trie, which provides update and lookup performance similarly to a normal hashmap/set, but needs no rehashing and also allows one to copy the entire map/set in constant time. This implementation uses a 32 bit hash and trie nodes with 32 children, so 5 bits of the hash are consumed to choose the next child. When there are no hash collisions, this HAMT can store 2^32 items with a maximal tree depth of (log_32 2^32) = 6, i.e., you need 6 memory accesses to find any key/value which is practically O(1). Although when there are hash collisions, they are put in an array.

Each HAMT node carries a reference counter, since FreePascal has no garbage collector. If the reference count is 1, the node can mutate, otherwise it is immutable with a copy-on-write semantic like strings. The counter is updated atomically, so the map could be shared across threads. This might lead to a large number of memory writes when a path of a full tree is copied (6 levels of up 32 children), but still less than copying a full hash table.

Everything is implemented using generics, so it can be used with all types.


Mutable Map:

```pascal type TMutableMapStringString = specialize TMutableMap; var map: TMutableMapStringString; p: TMutableMapStringString.PPair; begin map := TMutableMapStringString.create; map.Insert('hello', 'world'); map.insert('foo', 'bar'); map['abc'] := 'def';

writeln(map['hello']); // world writeln(map.get('foo')); // bar writeln(map.get('abc', 'default')); // def

//enumerate all for p in map do writeln(p^.key, ': ', p^.value);; end. ```

Immutable Map:

```pascal type TImmutableMapStringString = specialize TImmutableMap; var map, map2, map3: TImmutableMapStringString; p: TImmutableMapStringString.PPair; begin map := TImmutableMapStringString.create; map2 := map.Insert('hello', 'world'); map3 := map2.insert('foo', 'bar');

writeln(map.get('hello', 'default')); // default writeln(map.get('foo', 'default')); // default

writeln(map2.get('hello')); // world writeln(map2.get('foo', 'default')); // default

writeln(map3['hello']); // world writeln(map3['foo']); // bar

//enumerate all for p in map3 do writeln(p^.key, ': ', p^.value);;;; end. ```

Mutable Set: ```pascal type TMutableSetString = specialize TMutableSet; var stringSet: TMutableSetString; p: TMutableSetString.PItem; begin stringSet := TMutableSetString.create; stringSet.Insert('hello'); stringSet.insert('foo');

writeln(stringSet['hello']); // true writeln(stringSet.contains('foo')); // true writeln(stringSet.contains('abc')); // false

//enumerate all for p in stringSet do writeln(p^);; end. ```

Immutable Set:

```pascal type TImmutableSetString = specialize TImmutableSet; var set1, set2, set3: TImmutableSetString; p: TImmutableSetString.PItem; begin set1 := TImmutableSetString.create; set2 := set1.Insert('hello'); set3 := set2.insert('foo');

writeln(set1.contains('hello')); // false writeln(set1['foo']); // false

writeln(set2.contains('hello')); // true writeln(set2['foo']); // false

writeln(set3.contains('hello')); // true writeln(set3['foo']); // true

//enumerate all for p in set3 do writeln(p^);;;; end. ```




This library requires no installation, there are no dependencies besides the FreePascal compiler. Just copy the hamt.* files in the unit search path of FreePascal. Then you can use the maps with uses hamt.maps and the sets with uses hamt.sets.

However, beware that the last stable release of FreePascal, 3.0.4, cannot compile the complex generics used here. You need to have at least FreePascal 3.1.1, preferably 3.3.1 with revision r39690.

To run the tests cases in tests/hamt_tests.pas, you also need to have bbutils in the search path.


Ideal Hash Trees

Efficient Immutable Collections

How to clone

You can clone this repository with
hg clone

directory / @ :e35827bd8aa0

name size permissions
[up] drwxr-xr-x
dir. tests/ drwxr-xr-x
file .travis.yml 952 -rw-r--r--
file 4690 -rw-r--r--
file hamt.internals.pas 33240 -rw-r--r--
file hamt.maps.pas 13142 -rw-r--r--
file hamt.sets.pas 9713 -rw-r--r--