Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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]]}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment