The Full Wiki

More info on Hash array mapped trie

Hash array mapped trie: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

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

Contents

Advantages of HAMTs

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.[3]

References

  1. ^ Bagwell, P. (2001) Ideal Hash Trees. Technical Report, 2001.
  2. ^ Bagwell, P. (2000) Fast And Space Efficient Trie Searches. Technical Report, 2000.
  3. ^ Java source file of Clojure's hash map type.

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message