神刀安全网

In-memory hash tree implementation

package htree

import "github.com/hit9/htree"

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:

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

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

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

    • 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
    • func (iter *Iterator) Item() Item
    • func (iter *Iterator) Next() bool
    • func (i Uint32) Key() uint32

Package Files

htree.go

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.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » In-memory hash tree implementation

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮