htree

README

HTree

Package htree implements the in-memory hash tree.

https://pkg.go.dev/github.com/hit9/htree

Example

package main

import (
	"fmt"
	"github.com/hit9/htree"
)

// Item implements htree.Item.
type Item struct {
	key   uint32
	value string
}

// Key returns the item key.
func (item Item) Key() uint32 {
	return item.key
}

func main() {
	t := htree.New()
	// Add an item.
	item := t.Put(Item{123, "data1"})
	// Get an item.
	item = t.Get(Item{key: 123})
	fmt.Println(item)
}

License

BSD.

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:

1. Suppose depth is d, its prime p = Primes[d]
2. Get the remainder of key divided by p, r = key % p
3. If r is already taken by another node, go to the next depth.
4. 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

• type HTree
  • func New() *HTree
  • func (t *HTree) Conflicts() int
  • func (t *HTree) Delete(item Item) Item
  • func (t *HTree) Get(item Item) Item
  • func (t *HTree) Len() int
  • func (t *HTree) NewIterator() *Iterator
  • func (t *HTree) Put(item Item) Item
• type Item
• type Iterator
  • func (iter *Iterator) Item() Item
  • func (iter *Iterator) Next() bool
• type Uint32
  • func (i Uint32) Key() uint32

Types

type HTree

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

HTree is the hash-tree.

func New

func New() *HTree

New creates a new htree.

func (*HTree) Conflicts

func (t *HTree) Conflicts() int

Conflicts returns the number of conflicts in the tree.

func (*HTree) Delete

func (t *HTree) Delete(item Item) Item

Delete item from htree and returns the item, nil on not found.

func (*HTree) Get

func (t *HTree) Get(item Item) Item

Get item from htree, nil if not found.

func (*HTree) Len

func (t *HTree) Len() int

Len returns the number of nodes in the tree.

func (*HTree) NewIterator

func (t *HTree) NewIterator() *Iterator

NewIterator returns a new iterator on this htree.

func (*HTree) Put

func (t *HTree) Put(item Item) Item

Put item into htree and returns the item. If the item already in the / tree, return it, else new a node with the given item and return this item. If the depth overflows, nil is returned.

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.

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator is an iterator on the htree.

func (*Iterator) Item

func (iter *Iterator) Item() Item

Item returns the current item.

func (*Iterator) Next

func (iter *Iterator) Next() bool

Next seeks the iterator to next. Iteration order sample:

    root
   /    \
  0      1     %2
 / \    / \
4   2  3   5   %3

Order: 0 -> 4 -> 2 -> 1 -> 3 -> 5

type Uint32

type Uint32 uint32

Uint32 implements the Item interface.

func (Uint32) Key

func (i Uint32) Key() uint32

Key returns the htree node key.