Crate hashed_array_tree Copy item path

An implementation of Hashed Array Trees by Edward Sitarski.

From the original article:

To overcome the limitations of variable-length arrays, I created a data structure that has fast constant access time like an array, but mostly avoids copying elements when it grows. I call this new structure a “Hashed-Array Tree” (HAT) because it combines some of the features of hash tables, arrays, and trees.

To achieve this, the data structure uses a standard growable vector to reference separate data blocks which hold the array elements. The index and the blocks are at most O(√N) in size. As more elements are added, the size of the index and blocks will grow by powers of two (4, 8, 16, 32, etc).

§Memory Usage

An empty hased array tree is approximately 72 bytes in size, and while holding elements it will have a space overhead on the order of O(√N). As elements are added the array will grow by allocating additional data blocks. Likewise, as elements are removed from the end of the array, data blocks will be deallocated as they become empty.

§Performance

The get and set operations are O(1) while the push and pop may take O(N) in the worst case, if the array needs to be grown or shrunk.

§Safety

Because this data structure is allocating memory, copying bytes using pointers, and de-allocating memory as needed, there are many unsafe blocks throughout the code.