In computer science, a hashed array tree (HAT) is a dynamic array data-structure published by Edward Sitarski in 1996, maintaining an array of separate memory fragments (or "leaves") to store the data elements, unlike simple dynamic arrays which maintain their data in one contiguous memory area. Its primary objective is to reduce the amount of element copying due to automatic array resizing operations, and to improve memory usage patterns.
Whereas simple dynamic arrays based on geometric expansion waste linear (Ω(n)) space, where n is the number of elements in the array, hashed array trees waste only order O(n1/2) storage space. An optimization of the algorithm allows to eliminate data copying completely, at a cost of increasing the wasted space.
It can perform access in constant (O(1)) time, though slightly slower than 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.
Read more about Hashed Array Tree: Definitions, Expansions and Size Reductions, Related Data Structures
Famous quotes containing the words array and/or tree:
“Any one who knows what the worth of family affection is among the lower classes, and who has seen the array of little portraits stuck over a labourer’s fireplace ... will perhaps feel with me that in counteracting the tendencies, social and industrial, which every day are sapping the healthier family affections, the sixpenny photograph is doing more for the poor than all the philanthropists in the world.”
—Macmillan’s Magazine (London, September 1871)
“What signify a few lives lost in a century or two? The tree of liberty must be refreshed from time to time with the blood of patriots and tyrants. It is its natural manure.”
—Thomas Jefferson (1743–1826)