package module
Version: v1.0.0 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Jan 16, 2023 License: BSD-3-Clause Imports: 0 Imported by: 0



Package htree implements the in-memory hash tree.


package main

import (

// 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})





Package htree implements the in-memory hash tree.


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:

  | %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


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.



This section is empty.


This section is empty.


This section is empty.


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:

   /    \
  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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL