Judy Array

An AssociativeArray data structure created by DougBaskins?, described alternately as a "optimized 256-ary trie" or with faint moaning sounds from those rendered speechless at the deep magic of its implementation. It apparently takes advantage of the CacheTunnel? effect, wherein extra instructions in complex operations that preserve a very tight locality of reference operate faster than more naive instructions that require extra cache line fills.

The reference implementation is found at http://judy.sf.net/.

See also StringTrie