Hashed Array Trees

Overview

This Rust crate provides an implementation of hashed array trees as described by Edward Sitarski in the Algorithm Alley column of the September 1996 edition of Dr. Dobb's Journal.

This data structure supports push and pop operations and does not support inserts or removes at other locations within the array. One exception is the swap/remove operation which will retrieve a value from a specified index, overwrite that slot with the value at the end of the array, decrement the count, and return the retrieved value.

Memory Usage

Compared to the Vec type in the Rust standard library, this data structure will have substantially less unused space, on the order of O(√N). The dope vector contributes to the overhead of this data structure, and that is on the order of O(√N). Based on the current implementation of Vec, as much as 50% of the space may be unused since it has a growth factor of 2.

Examples

A simple example copied from the unit tests.

let mut sut = HashedArrayTree::<usize>::new();
for value in 0..13 {
    sut.push(value);
}
assert_eq!(sut.len(), 13);
assert_eq!(sut.capacity(), 16);
for value in 0..13 {
    assert_eq!(sut[value], value);
}

Supported Rust Versions

The Rust edition is set to 2024 and hence version 1.85.0 is the minimum supported version.

Troubleshooting

Memory Leaks

Finding memory leaks with Address Sanitizer is fairly [easy](https
://doc.rust-lang.org/beta/unstable-book/compiler-flags/sanitizer.html) and seems to work best on Linux. A Docker contai
ner with bash access and Rust nightly installed can be found in the containers directory.

cd containers
docker compose build --pull
docker compose run leaktest
sh leak.sh

If no problems were detected, a single line of output will appear. When done, clean up the docker artifacts.

exit
docker compose down

References

• HATs: Hashed Array Trees (1996)
  • An archived version of the original article from Dr. Dobb's Journal.

Other Implementations

• Aca-S/hashed-array-tree (C++)