BucketizedCuckooHashing.go

package main

import (
	"crypto/md5"
	"encoding/hex"
	"fmt"
	"math/big"
)

const (
	N       int64 = 5 // テーブルの大きさ
	BCKSIZE int   = 2 // bucketのサイズ
	MAXLOOP int   = 100
)

func hash(key int64) (h1, h2 int64) {
	hasher := md5.New()

	b := make([]byte, 8)
	binary.LittleEndian.PutUint64(b, uint64(key))

	hasher.Write(b)

	h := hex.EncodeToString(hasher.Sum(nil))

	h1_t, _ := new(big.Int).SetString(h[:int(len(h)/2)], 16)
	h2_t, _ := new(big.Int).SetString(h[int(len(h)/2):], 16)
	h1 = h1_t.Rem(h1_t, big.NewInt(N)).Int64()
	h2 = h2_t.Rem(h2_t, big.NewInt(N)).Int64()

	return h1, h2
}

type BucketizedCuckoo struct {
	T1, T2 [N][BCKSIZE]int64
}

func NewBucketizedCuckoo() *BucketizedCuckoo {
	return new(BucketizedCuckoo)
}

func (c *BucketizedCuckoo) lookup(key int64) bool {
	h1, h2 := hash(key)

	for _, bucket := range c.T1[h1] {
		if bucket == key {
			return true
		}
	}

	for _, bucket := range c.T2[h2] {
		if bucket == key {
			return true
		}
	}

	return false
}

func (c *BucketizedCuckoo) insert(key int64, cnt int) {
	for cnt < MAXLOOP {
		h1, h2 := hash(key)
		switch cnt % 2 {
		case 0:
			for i, bucket := range c.T1[h1] {
				if bucket == 0 {
					c.T1[h1][i] = key
					return
				} else if i == BCKSIZE-1 {
					key, c.T1[h1][i] = c.T1[h1][i], key
				}
			}

		case 1:
			for i, bucket := range c.T2[h2] {
				if bucket == 0 {
					c.T2[h2][i] = key
					return
				} else if i == BCKSIZE-1 {
					key, c.T2[h2][i] = c.T2[h2][i], key
				}
			}
		}
		cnt++
	}
	panic("fail to insert. you must reconstruct the Table...")
}

func (c *BucketizedCuckoo) delete(key int64) {
	h1, h2 := hash(key)

	for i, bucket := range c.T1[h1] {
		if bucket == key {
			c.T1[h1][i] = 0
		}
	}

	for i, bucket := range c.T2[h2] {
		if bucket == key {
			c.T2[h2][i] = 0
		}
	}

	return
}

func main() {
	c := NewBucketizedCuckoo()

	// insert the keys.
	x := []int64{1, 2, 3, 4, 5, 6, 7, 8, 9}
	for _, key := range x {
		cnt := 0
		c.insert(key, cnt)
	}

	// look up for the key "1" and "10".
	fmt.Println("key:1  ", c.lookup(1))  // key:1   true
	fmt.Println("key:10 ", c.lookup(10)) // key:10  false

	// delete the key "3".
	fmt.Println("before: ", *c) // before:  {[[1 9] [4 0] [2 6] [8 0] [0 0]] [[0 0] [5 0] [3 0] [0 0] [7 0]]}
	c.delete(3)
  	fmt.Println("after:  ", *c) // after:   {[[1 9] [4 0] [2 6] [8 0] [0 0]] [[0 0] [5 0] [0 0] [0 0] [7 0]]}
}