| has gloss | eng: In computer science, a hashed array tree (HAT) is a dynamic array algorithm invented by Edward Sitarski in 1996. 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 n1/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. |
