Judy array

From Free net encyclopedia

In computer science and software engineering, a Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. Unlike arrays, Judy arrays may be sparse; that is, they may have large ranges of unassigned indices.

Judy arrays are designed to keep the number of processor cache-line fills as low as possible, and the algorithm is internally complex in an attempt to satisfy this goal as often as possible. Due to these cache optimizations, Judy arrays are fast, sometimes even faster than a hash table and because Judy arrays are a type of trie they consume much less memory than hash tables.

Roughly speaking, it is similar to a highly-optimised 256-ary trie data structure.Template:Ref

Judy arrays also believed to be less vulnerable to algorithmic complexity attacks.Template:Ref

[edit]