Hashed array tree

From Wikipedia, the free encyclopedia

In computer science, Hashed array tree (HAT) is a dynamic array algorithm invented by Sitarski in 1996. ^[1] Hashed Array Tree wastes order n^1/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.

A full Hashed Array Tree with 16 elements

1 Definitions
2 Expansions and size reductions
3 Related data structures
4 See also
5 References

[edit] 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 n² elements, with n being a power of 2 integer. ^[1]

[edit] 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.

[edit] 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.