Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
An efficient trie implementation.
C C++
branch: master

This branch is 19 commits ahead, 30 commits behind dcjones:master

Failed to load latest commit information.
m4 ensure the m4 directory for autoreconf
src fix hattrie_iter_with_prefix() for trie node
test change longest_match to a more generic method: hattrie_walk
.gitignore ignore more files
COPYING array hash tables implemented (but untested) Remove strict dependence on autoconf detection of stdint. (fixes #3) Add missing common.h and document installation. (fixes #1)
TODO implemented iteration Remove strict dependence on autoconf detection of stdint. (fixes #3)


This a ANSI C99 implementation of the HAT-trie data structure of Askitis and Sinha, an extremely efficient (space and time) modern variant of tries.

The version implemented here maps arrays of bytes to words (i.e., unsigned longs), which can be used to store counts, pointers, etc, or not used at all if you simply want to maintain a set of unique strings.

For details see,

  1. Askitis, N., & Sinha, R. (2007). HAT-trie: a cache-conscious trie-based data structure for strings. Proceedings of the thirtieth Australasian conference on Computer science-Volume 62 (pp. 97–105). Australian Computer Society, Inc.

  2. Askitis, N., & Zobel, J. (2005). Cache-conscious collision resolution in string hash tables. String Processing and Information Retrieval (pp. 91–102). Springer.


git clone
cd hat-trie
autoreconf -i
make install

To use the library, include hat-trie.h and link using lhat-trie.

Something went wrong with that request. Please try again.