下面是经过优化的代码:
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 // 未找到指定键
}




