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 normal 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 consumes more CPU time than other data structures, but aims to make up for this usage with less waiting on memory.
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
- Programming with Judy: C LanguageJudy
- 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
No comments have been added.
