gocache/skiptable.go

package gocache

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

// 定义跳表节点结构
type SkipListNode struct {
	key   string // 键
	value interface{} // 值
	forward []*SkipListNode // 指向下一节点的指针数组
}

// 定义跳表结构
type SkipList struct {
	head *SkipListNode // 头节点
	level int          // 当前跳表的最大层数
	maxLevel int       // 跳表允许的最大层数
}

// 创建一个新的跳表
func NewSkipList(maxLevel int) *SkipList {
	return &SkipList{
		head:     &SkipListNode{forward: make([]*SkipListNode, maxLevel)},
		level:    0,
		maxLevel: maxLevel,
	}
}

// 随机生成层数
func randomLevel() int {
	rand.Seed(time.Now().UnixNano())
	level := 1
	for rand.Float64() < 0.5 && level < 16 { // 最大层数限制为16
		level++
	}
	return level
}

// 插入键值对
func (sl *SkipList) Insert(key string, value interface{}) {
	update := make([]*SkipListNode, sl.maxLevel)
	current := sl.head

	// 找到每一层需要更新的节点
	for i := sl.level - 1; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].key < key {
			current = current.forward[i]
		}
		update[i] = current
	}

	// 如果键已经存在，则更新其值
	if current.forward[0] != nil && current.forward[0].key == key {
		current.forward[0].value = value
		return
	}

	// 确定新节点的层数
	newLevel := randomLevel()
	if newLevel > sl.level {
		for i := sl.level; i < newLevel; i++ {
			update[i] = sl.head
		}
		sl.level = newLevel
	}

	// 创建新节点并更新指针
	newNode := &SkipListNode{key: key, value: value, forward: make([]*SkipListNode, newLevel)}
	for i := 0; i < newLevel; i++ {
		newNode.forward[i] = update[i].forward[i]
		update[i].forward[i] = newNode
	}
}

// 查找键对应的值
func (sl *SkipList) Search(key string) (interface{}, bool) {
	current := sl.head

	// 找到目标节点
	for i := sl.level - 1; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].key < key {
			current = current.forward[i]
		}
	}

	current = current.forward[0]
	if current != nil && current.key == key {
		return current.value, true
	}
	return nil, false
}

// 删除键值对
func (sl *SkipList) Delete(key string) bool {
	update := make([]*SkipListNode, sl.maxLevel)
	current := sl.head

	// 找到每一层需要更新的节点
	for i := sl.level - 1; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].key < key {
			current = current.forward[i]
		}
		update[i] = current
	}

	current = current.forward[0]
	if current != nil && current.key == key {
		for i := 0; i < sl.level; i++ {
			if update[i].forward[i] != current {
				break
			}
			update[i].forward[i] = current.forward[i]
		}

		// 更新当前跳表的层数
		for sl.level > 1 && sl.head.forward[sl.level-1] == nil {
			sl.level--
		}
		return true
	}
	return false
}

// 打印跳表（仅用于调试）
func (sl *SkipList) Print() {
	for i := sl.level - 1; i >= 0; i-- {
		fmt.Printf("Level %d: ", i)
		current := sl.head.forward[i]
		for current != nil {
			fmt.Printf("(%s:%v) -> ", current.key, current.value)
			current = current.forward[i]
		}
		fmt.Println("nil")
	}
}

func main() {
	skipList := NewSkipList(16)

	// 插入一些键值对
	skipList.Insert("apple", 3)
	skipList.Insert("banana", 5)
	skipList.Insert("cherry", 7)
	skipList.Insert("date", 9)

	// 打印跳表
	skipList.Print()

	// 查找键对应的值
	if val, found := skipList.Search("banana"); found {
		fmt.Printf("Search 'banana': %v\n", val)
	} else {
		fmt.Println("Search 'banana': not found")
	}

	// 删除键值对
	if skipList.Delete("banana") {
		fmt.Println("Deleted 'banana'")
	} else {
		fmt.Println("Delete 'banana': not found")
	}

	// 再次打印跳表
	skipList.Print()
}