Judy array

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. 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. [Alan Silverstein, " [http://judy.sourceforge.net/application/shop_interm.pdf Judy IV Shop Manual] ", 2002]

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. [ [http://www.cs.rice.edu/~scrosby/hash/ Denial of Service via Algorithmic Complexity Attacks] ]

The Judy array was invented by Doug Baskins and named for his sister.

External links

* [http://judy.sourceforge.net/ Main Judy arrays site]
* [http://docs.hp.com/en/B6841-90001/index.html Programming with Judy: C LanguageJudy]
* [http://judy.sourceforge.net/downloads/10minutes.htm How Judy arrays work and why they are so fast]
* [http://judy.sourceforge.net/application/shop_interm.pdf A complete technical description of Judy arrays]
* [http://www.nothings.org/computer/judy/ An independent performance comparison of Judy to Hash Tables]

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Judy — may refer to: * Judy, Kentucky * Judy (ship s dog) * Judy Yiddish letter for Greek character of Delta * Judy, Yokosuka D4Y aircraft * Judy Neutron, a character in The Adventures of Jimmy Neutron: Boy Genius media * Judy (given name)People with… …   Wikipedia

  • Array — In computer science an array [Paul E. Black, array , in Dictionary of Algorithms and Data Structures , Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 August 2008 (accessed 10 September 2008).… …   Wikipedia

  • Judy Davis — Infobox actor birthdate = birth date and age|1955|04|23|df=y birthplace = Perth, Western Australia, Australia spouse = Colin Friels (1984 present) afiawards = Best Actress 1981 Winter of Our Dreams 1986 Kangaroo 1987 High Tide 1996 Children of… …   Wikipedia

  • Bit array — A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). It implements a simple set data structure storing a subset of {1,2,..., n } and is effective at exploiting bit level… …   Wikipedia

  • Associative array — In computer science, an associative array (also called a map or a dictionary) is an abstract data type composed of a collection of (key,value) pairs, such that each possible key appears at most once in the collection. Operations associated with… …   Wikipedia

  • Passive electronically scanned array — A passive electronically scanned array (PESA), as opposed to its active counterpart AESA, is a phased array which has a central radiofrequency source (such as a magnetron, a klystron or a travelling wave tube), sending energy into (usually… …   Wikipedia

  • AN/SPQ-11 — Close up of the front of Cobra Judy radar, 1983. Country of origin United States Number built …   Wikipedia

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

  • UNITED STATES OF AMERICA — UNITED STATES OF AMERICA, country in N. America. This article is arranged according to the following outline: introduction Colonial Era, 1654–1776 Early National Period, 1776–1820 German Jewish Period, 1820–1880 East European Jewish Period,… …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”