- Hashed array tree
In
computer science , a hashed array tree (HAT) is adynamic 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 thearray , 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 usehash function s.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 ahash 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.