Skip to content
An efficient trie implementation.
C Other
  1. C 98.2%
  2. Other 1.8%
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.


Type Name Latest commit message Commit time
Failed to load latest commit information.
src Minor style fixes. Dec 6, 2018
test Ensure that returned key during prefix iteration doesn't include comm… Nov 24, 2018
COPYING array hash tables implemented (but untested) Aug 12, 2011 Remove strict dependence on autoconf detection of stdint. (fixes #3) Jul 28, 2012 Add links to other language bindings for hat-trie. Jul 1, 2014
TODO implemented iteration Aug 14, 2011 Version 0.1.2 Jun 19, 2017 a bit of cleanup Aug 13, 2011


Build Status

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.


Build and run the tests:

make check

Other Language Bindings

You can’t perform that action at this time.