Hash array mapped trie - Data Structures

A hash array mapped trie(HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.

Problems with HAMTs

Implementation of a HAMT involves the use of the population count function, which counts the number of ones in the binary representation of a number. This operation is available in many instruction set architectures (where it is sometimes called "CTPOP"), but it is only available in some high -level languages. Although population count can be implemented in software in O(1) time using a series of shift and add instructions, doing so may perform the operation an order of magnitude slower.

Implementations

The programming language Clojure uses a persistent variant of hash array mapped tries for its native hash map type.


All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structures Topics