Hashed array tree

Hashed array tree

In computer science, a hashed array tree (HAT) is a dynamic array algorithm invented by Edward Sitarski in 1996. Citation | title=HATs: Hashed array trees | contribution=Algorithm Alley | journal=Dr. Dobb's Journal | date=September 1996 | first1=Edward | last1=Sitarski | volume=21 | issue=11 | url=http://www.ddj.com/architect/184409965?pgno=5 ] Whereas simple dynamic array data structures based on geometric expansion waste linear (Ω("n")) space, where "n" is the number of elements in the array, hashed array trees waste only order "n"1/2 storage space. It can perform indexing in constant (O(1)) time, but indexing is not as quick in practice as for simple dynamic arrays. The algorithm has O(1) amortized performance when appending a series of objects to the end of a hashed array tree. Contrary to its name, it does not use hash functions.

Definitions

As defined by Sitarski, a hashed array tree has a top-level directory containing a power of two number of leaf arrays. All leaf arrays are the same size as the top-level directory. This structure superficially resembles a hash table with array-based collision chains, which is the basis for the name "hashed array tree". A full hashed array tree can hold "m"2 elements, where "m" is the size of the top-level directory.

Expansions and size reductions

When a hashed array tree is full, its directory and leaves must be restructured to twice its prior size to accomodate additional append operations. There are multiple alternatives for reducing size: when a Hashed Array Tree is one eighth full, it can be restructured to a smaller, half-full hashed array tree; another option is only freeing unused leaf arrays.

Related data structures

Brodnik et al. [ Citation | title=Resizable Arrays in Optimal Time and Space | date=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo ] presented a dynamic array algorithm with a similar space wastage profile to hashed array trees. Brodnik's implementation retains previously allocated leaf arrays, with a more complicated address calculation function as compared to hashed array trees.

ee also

* VList

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dynamic array — Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Θ(n) time,… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Comparison of programming languages (mapping) — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • Memory management unit — This 68451 MMU could be used with the Motorola 68010 A memory management unit (MMU), sometimes called paged memory management unit (PMMU), is a computer hardware component responsible for handling accesses to memory requested by the CPU. Its… …   Wikipedia

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

  • Pick operating system — Company / developer Don Nelson, Dick Pick, TRW Programmed in Assembly language Initial release 1965 (GIRLS), 1973 (Reality Operating System) Marketing target Business data processing Available …   Wikipedia

  • Forth (programming language) — infobox programming language name = Forth paradigm = Procedural, stack oriented year = 1970s designer = Charles H. Moore typing = typeless dialects = colorForth, Open Firmware implementations = Forth, Inc., GNU Forth, MPE influenced by =… …   Wikipedia

  • Nokia phone series — Nokia s nomenclature can be traced back since 2005, when the Nseries line was introduced.[1] Because of the demands and peak of that line, Nokia again introduced another series of phones named Eseries,[2] made mostly for the enterprise market.[3] …   Wikipedia

Share the article and excerpts

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