Hash array mapped trie

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

[edit] Advantages of HAMTs

[edit] Problems with HAMTs

Implementation of a HAMT involves the use of the "CTPOP" function, which counts the number of ones in the binary representation of a number. This operation is available in many instruction set architectures, but it is not commonly available in high-level languages. Although CTPOP can be implemented in software in O(1) time using a series of shift and add instructions, doing so results in a significant performance penalty.

[edit] References

  1. ^ Bagwell, P. (2001) Ideal Hash Trees. Technical Report, 2001.
  2. ^ Bagwell, P. (2000) Fast And Space Efficient Trie Searches. Technical Report, 2000.
Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.