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.[1] Judy arrays are also believed to be less vulnerable to algorithmic complexity attacks.[2] The Judy array was invented by Doug Baskins and named for his sister.
External links
- Main Judy arrays site
- How Judy arrays work and why they are so fast
- A complete technical description of Judy arrays
- An independent performance comparison of Judy to Hash Tables
References
- ^ Alan Silverstein, "Judy IV Shop Manual", 2002
- ^ Denial of Service via Algorithmic Complexity Attacks
