ZBLOG

package main import ( "fmt" "math/bits" "math/rand" ) const bucketSize = 20 // 桶大小 type KBucket struct { buckets [160][]string selfID string size int // 桶大小 } func NewKBucket(selfID string, size int) *KBuck

下面是经过优化的代码:

package main

import (
	"fmt"
	"math/bits"
	"math/rand"
)

const bucketSize = 20 // 桶大小

type KBucket struct {
	buckets [160][]string
	selfID  string
	size    int // 桶大小
}

func NewKBucket(selfID string, size int) *KBucket {
	return &KBucket{
		selfID: selfID,
		size:   size,
	}
}

// 计算距离,返回每一位的异或值
func (kb *KBucket) distance(nodeID string) []byte {
	a := []byte(kb.selfID)
	b := []byte(nodeID)
	res := make([]byte, len(a))
	for i := range a {
		res[i] = a[i] ^ b[i]
	}
	return res
}

// 根据距离计算应该插入的桶的索引
func (kb *KBucket) getBucket(distance []byte) int {
	for i := range distance { // 遍历每一位
		if distance[i] != 0 { // 找到第一个不为0的位置,计算索引并返回
			return i*8 + bits.LeadingZeros8(uint8(distance[i]))
		}
	}
	return len(distance)*8 - 1 // 如果所有位都为0,则插入到最后一个桶中(按照从大到小排序)
}

// 插入节点
func (kb *KBucket) insertNode(nodeId string) {
	distance := kb.distance(nodeId)
	bucketIndex := kb.getBucket(distance)

	if len(kb.buckets[bucketIndex]) >= kb.size { // 桶已满,替换最老的节点
		if len(kb.buckets[bucketIndex]) == 0 { // 桶为空,直接插入新节点
			kb.buckets[bucketIndex] = append(kb.buckets[bucketIndex], nodeId)
			return
		}
		// 替换最老的节点
		kb.replaceOldest(bucketIndex, nodeId)
	} else { // 直接插入新节点
		kb.buckets[bucketIndex] = append(kb.buckets[bucketIndex], nodeId)
	}
}

// 替换最老的节点
func (kb *KBucket) replaceOldest(bucketIndex int, nodeID string) {
	if len(kb.buckets[bucketIndex]) <= 0 { // 桶为空,直接插入新节点
		kb.buckets[bucketIndex] = append(kb.buckets[bucketIndex], nodeID)
		return
	}

	var oldestIdx int // 最老节点的索引

	for i, id := range kb.buckets[bucketIndex] {
		if id == nodeID { // 新节点已存在,无需再次插入
			return
		}

        if i == 0 || len(kb.buckets[bucketIndex][oldestIdx]) == 0 {
            oldestIdx = i
            continue
        }

        // 比较距离,选择最老的节点(即距离最大的)
        dist1 := kb.distance(id)
        dist2 := kb.distance(kb.buckets[bucketIndex][oldestIdx])
        if dist1[len(dist1)-1] > dist2[len(dist2)-1] {
            oldestIdx = i
        }
    }

    // 替换最老的节点
    kb.buckets[bucketIndex][oldestIdx] = nodeID

    if len(kb.buckets[bucketIndex][0]) != 0 {
        // 将被替换的节点插入到相应桶中(可能需要递归)
        kb.insertNode(kb.buckets[bucketIndex][0])
    }
}

// 输出所有桶中的内容
func (kb *KBucket) printBucketContents() {
	for i := range kb.buckets {
		if len(kb.buckets[i]) > 0 {
			fmt.Printf("Bucket %d:", i)
			for j := range kb.buckets[i] {
				fmt.Printf("%s ", kb.buckets[i][j])
			}
			fmt.Println()
		}
	}
}

func main() {
	nodes := make([]string, 100)
	keys := make([]string, 200)
	values := make(map[string]string)

	// 随机生成100个节点,并为每个节点创建一个k桶,并将其他节点加入该桶中
	for i := 0; i < 100; i++ {
		nodeID := randomID()
		// 确保随机生成的节点ID不与之前已经生成的重复
		for contains(nodes, nodeID) {
			nodeID = randomID()
		}
		nodes[i] = nodeID

        // 创建当前节点的k桶,并将其他除自己外的所有节点加入到该桶中
        kb := NewKBucket(nodeID, bucketSize)
        for j := 0; j < bucketSize; j++ {
            if j != i { // 跳过自身
                kb.insertNode(nodes[j])
            }
        }
    }

    // 随机生成200个键值对
    for i := 0; i < 200; i++ {
        key, value := randomKVPair()
        // 确保键不重复
        for contains(keys, key) {
            key, value = randomKVPair()
        }
        keys[i] = key
        values[key] = value
    }

    // 随机选择100个节点,向其写入数据
    for _, key := range keys[:100] {
        nodeIndex := rand.Intn(100)
        nodeID := nodes[nodeIndex]
        fmt.Printf("SetValue(%s, %s) at Node %s\n", key, values[key], nodeID)
    }

    // 随机选择100个节点,从中读取之前写入的数据,并输出结果
    for _, key := range keys[100:] {
        nodeIndex := rand.Intn(100)
        nodeID := nodes[nodeIndex]
        value, ok := getValue(nodeID, key, values)
        if !ok { // 未找到指定键
            fmt.Printf("GetValue(%s) at Node %s: Key not found\n", key, nodeID)
            continue
        }
        fmt.Printf("GetValue(%s) at Node %s: %s\n", key, nodeID, value)
    }
}

// 判断切片中是否包含字符串
func contains(slice []string, s string) bool {
	for _, v := range slice {
		if v == s {
			return true
		}
	}
	return false
}

// 随机生成一个键值对(key和value均为长度为8的随机字符串)
func randomKVPair() (string, string) {
	key := randomString()
	value := randomString()
	return key, value
}

// 生成一个长度为10的随机字符串(16进制表示)
func randomString() string {
	b := make([]byte, 10)
	if _, err := rand.Read(b); err != nil {
		panic(err)
	}
	return fmt.Sprintf("%x", b)[:8]
}

// 生成一个长度为20的随机字符串(16进制表示)
func randomID() string {
	b := make([]byte, 20)
	if _, err := rand.Read(b); err != nil {
		panic(err)
	}
	return fmt.Sprintf("%x", b)
}

// 在指定节点中查找指定键对应的值
func getValue(nodeID string, key string, values map[string]string) (string, bool) {
	kb := NewKBucket(nodeID, bucketSize)
	bucketIndex := kb.getBucket(kb.distance(key)) // 计算应该在哪个桶中查找
	for _, id := range kb.buckets[bucketIndex] {
		if id == key { // 找到指定键,返回相应值
			return values[key], true
		}
	}
	return "", false // 未找到指定键
}

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=4186

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?