Hash Array Mapped Trie (C++ Templates)
C C++ CMake Batchfile
Switch branches/tags
Nothing to show
Latest commit f5f702f Feb 9, 2017 @chaelim committed on GitHub Merge pull request #3 from chaelim/dev
Merge dev to master.

README.md

Build status

C++ Template class implementation of Hash Array Mapped Trie

Do you want space-efficient and fast hash table? HAMT is just here for you. Based on the paper Ideal Hash Trees by Phil Bagwell, and as the title stated, it has really ideal features as a hash table as below.

Features

  • No initial root hash table required. (Empty hash table just takes 8 bytes in 32 bit build or 12 bytes in 64 bit build.)
  • No stop the world rehashing.
  • Faster and smaller.
  • Constant add/delete O(1) operations
  • C++ Template implementation can be easily used to any data type.
  • 32 bit hash key and 32 bit bitmap to index subhash array.
  • 32 bit integer and string (ANSI and Unicode) hash key templates are included.
  • Expected tree depth: equation.
    w = 5
    n : number of elements stored in the trie
  • Hamming weight of bitmap can be caculated using POPCNT(Population count) CPU intruction (introduced in Nehalem-base and Barcelona microarchitecture CPU). POPCNT can speed up overall performance about 10%.

Test program build notes

More information