Hash array mapped trie

Hash array mapped trie

A hash array mapped trie [Bagwell, P. (2001) [http://lampwww.epfl.ch/papers/idealhashtrees.pdf Ideal Hash Trees] . Technical Report, 2001.] (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie [Bagwell, P. (2000) [http://citeseer.ist.psu.edu/rd/61998956%2C282572%2C1%2C0.25%2CDownload/http%3AqSqqSqlampwww.epfl.chqSqpapersqSqtriesearches.pdf.gz Fast And Space Efficient Trie Searches] . Technical Report, 2000.] .

Advantages of HAMTs

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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Ctrie — A concurrent hash trie or Ctrie[1] is a concurrent thread safe lock free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and… …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

  • Associative array — In computer science, an associative array (also called a map or a dictionary) is an abstract data type composed of a collection of (key,value) pairs, such that each possible key appears at most once in the collection. Operations associated with… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”