Hashed array tree
In computer science, Hashed array tree (HAT) is a dynamic array algorithm invented by Sitarski in 1996. [1] Hashed Array Tree wastes order n1/2 amount of storage space, where n is the number of elements in the array. The algorithm has O(1) amortized performance when appending a series of objects to the end of a Hashed Array Tree.

Definitions
As defined by Sitarski, a Hashed Array Tree has a top level directory containing power of 2 number of leaf arrays. All leaf arrays are the same size as the top level directory. This structure superficially resembles a hashtable with array based collision chains, thus the name of Hashed Array Tree was coined. A full Hashed Array Tree can hold n2 elements, with n being a power of 2 integer. [1]
Expansions and size reductions
When a Hashed Array Tree is full, its directory and leaves must be restructured to twice its prior size. There are considerable more flexibility to size reduction strategies. When a Hashed Array Tree is one eighth full, it can be restructured to a smaller Hashed Array Tree of half full. Other alternatives include only freeing unused leaf arrays.
Related data structures
Brodnik et al. [2] presented a dynamic array algorithm with a similar space wastage profile to Hashed Array Tree. Brodnik's implementation retains previously allocated leaf arrays, with a more complicated address calculation function as compared to Hashed Array Tree.
See also
References
- ^ a b Sitarski, Edward (September 1996), "HATs: Hashed array trees", Dr. Dobb's Journal, 21 (11)
{{citation}}
:|contribution=
ignored (help) - ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (Technical Report CS-99-09), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo
{{citation}}
: Check date values in:|date=
and|year=
/|date=
mismatch (help)