以下是对代码的优化建议:
添加必要的包引用:在代码中需要使用
math/bits
包,因此需要将其添加到代码中。将常量值作为参数传递:可以将桶大小(bucketSize)作为 NewKBucket 方法的参数,这样就可以在创建 KBucket 对象时指定桶大小,而不是使用固定的常量值。
改善 insertNode 方法:在插入节点时,如果目标桶已经满了,则先删除最旧的节点再插入新节点。但是这种方法可能会导致多次递归调用 insertNode 方法,影响性能。一种更好的方法是,在向桶中插入新节点之前检查该桶是否已满,并计算出应该删除哪个节点。然后直接替换相应位置的元素即可。
改善 getValue 方法:在获取键值对时,可以直接返回找到的键值对,并且不必遍历整个桶以查找指定键。只需根据距离计算出目标桶索引,并在该桶内查找指定键即可。
下面是针对以上问题进行的代码修改建议:
package main
import (
"crypto/rand"
"fmt"
"math/bits"
)
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 {
return i*8 + bits.LeadingZeros8(uint8(distance[i]))
}
}
return len(distance)*8 - 1
}
func (kb *KBucket) insertNode(nodeId string) {
distance := kb.distance(nodeId)
bucketIndex := kb.getBucket(distance)
if len(kb.buckets[bucketIndex]) >= kb.size { // 桶已满,替换最老的节点
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 {
oldestIdx = i
continue
}
if kb.distance(id)[bucketIndex/8] > kb.distance(kb.buckets[bucketIndex][oldestIdx])[bucketIndex/8] { // 比较距离,选择最老的节点
oldestIdx = i
}
}
kb.buckets[bucketIndex][oldestIdx] = nodeID // 替换最老的节点
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)
for i := 0; i < 100; i++ {
nodeID := randomID()
nodes[i] = nodeID
kb := NewKBucket(nodeID, bucketSize)
for j := 0; j < bucketSize; j++ {
if j != i {
kb.insertNode(nodes[j])
}
}
}
for i := 0; i < 200; i++ {
key, value := randomKVPair()
keys[i] = key
values[key] = value
}
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)
}
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)
} else {
fmt.Printf("GetValue(%s) at Node %s: %s\n", key, nodeID, value)
}
}
}
func randomKVPair() (string, string) {
key := randomString()
value := randomString()
return key, value
}
func randomString() string {
b := make([]byte, 10)
if _, err := rand.Read(b); err != nil {
panic(err)
}
return fmt.Sprintf("%x", b)[:8]
}
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 // 未找到指定键
}