## Documentation ¶

### Overview ¶

Package htree implements the in-memory hash tree.

#### Abstract ¶

Hash-Tree is a key-value multi-tree with fast indexing performance and high space utilization.

Take 10 consecutive prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

And they can distinguish all uint32 numbers:

2*3*5*7*11*13*17*19*23*29 > ^uint32(0)

Key insertion steps:

- Suppose depth is d, its prime p = Primes[d]
- Get the remainder of key divided by p, r = key % p
- If r is already taken by another node, go to the next depth.
- Otherwise create a new child node and bind r to it.

Example htree:

ROOT | %2 +-- 0: A(12) 12%2=0: A | | %3 | +-- 0: C(6) 6%2=0 && 6%3=0: C | |-- 1: D(4) 4%2=0 && 4%3=1: D | +-- 2: E(8) 8%2=0 && 8%3=2: E +-- 1: B(3) 3%2=1: B | %3 +-- 0: F(9) 9%2=1 && 9%3=0: F |-- 1: G(7) 7%2=1 && 7%3=1: G +-- 2: H(11) 11%2=1 && 11%3=2: H

#### Complexity ¶

Child nodes are stored in an array orderly, and checked by binary-search but not indexed by remainders, array indexing will result redundancy entries, this is for less memory usage, with a bit performance loss. A node is created only when a new key is inserted. So the worst time complexity is O(Sum(lg2~lg29)), is constant level, and the entries utilization is 100%.

#### Compare To Map ¶

Although hashtable is very fast with O(1) time complexity, but there is always about ~25% table entries are unused, because the hash-table load factor is usually .75. And this htree is suitable for memory-bounded cases.

HTree is better for local locks if you want a safe container.

Map may need to rehash and resize on insertions.

#### Goroutine Safety ¶

No. Lock granularity depends on the use case.

### Index ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type HTree ¶

```
type HTree struct {
// contains filtered or unexported fields
}
```

HTree is the hash-tree.

#### func (*HTree) NewIterator ¶

NewIterator returns a new iterator on this htree.

#### type Item ¶

type Item interface { // Key returns an uint32 number to distinguish node with another. Key() uint32 }

Item is a single object in the tree.