Jump to content

Judy array

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Nave.notnilc (talk | contribs) at 13:51, 10 August 2010 (grammar tweaks). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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, especially for very big datasets. Despite Judy arrays being a type of trie, they consume much less memory than hash tables. Also because a Judy array is a trie, it is possible to do an ordered sequential traversal of keys, which is not possible in hash tables.

Roughly speaking, it is similar to a highly-optimised 256-ary trie data structure.[1] To make memory consumption small, Judy array uses more than 20 various compression techniques to compress trie nodes.

Judy arrays are also believed to be less vulnerable to algorithmic complexity attacks.[2]

The Judy array was invented by Doug Baskins and named after his sister.[3]

References

  1. ^ Alan Silverstein, "Judy IV Shop Manual", 2002
  2. ^ Denial of Service via Algorithmic Complexity Attacks
  3. ^ http://judy.sourceforge.net/


Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Judy_array&oldid=378179050"