Judy array
|
|
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.
Roughly speaking, the data structure's designer describes it as similar to a highly-optimised 256-ary trie data structure.
External links
- Main Judy arrays site (http://judy.sourceforge.net/)
- How Judy arrays work and why they are so fast (http://judy.sourceforge.net/downloads/10minutes.htm)
- A complete technical description of Judy arrays (http://judy.sourceforge.net/application/shop_interm.pdf)