Hashed array tree
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.
- Comment
- enIn 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.
- Depiction
- Has abstract
- enIn 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(√n) storage space. An optimization of the algorithm allows elimination of 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.
- Is primary topic of
- Hashed array tree
- Label
- enHashed array tree
- Link from a Wikipage to another Wikipage
- Array data structure
- Big O notation
- B-tree
- Category:Arrays
- Computer science
- Dynamic array
- File:HashedArrayTree16.svg
- Hash function
- Hash table
- Power of two
- Quotient
- Random access
- Remainder
- Unrolled linked list
- SameAs
- 4kqRz
- Hashed array tree
- m.02w zt
- Q5678892
- Хеширано стабло
- درخت آرایه درهم
- Subject
- Category:Arrays
- Thumbnail
- WasDerivedFrom
- Hashed array tree?oldid=1076479510&ns=0
- WikiPageLength
- 5230
- Wikipage page ID
- 12673184
- Wikipage revision ID
- 1076479510
- WikiPageUsesTemplate
- Template:Data structures
- Template:List data structure comparison
- Template:Reflist
- Template:Sqrt
