2.9 跳表

1. 跳表是什么

• 跳表相当于普通的链表有两个区别
  • 有上、下、左、右四个指针
  • 多了层的概念

1.1. 举例

• 普通链表
  • 
• 有效层数为2的跳表
  • 
• 有效层数为4的跳表
  • 

1.2. 特点

• 随机的数据结构
• 最底层包含了整个跳表的所有元素
• 典型的空间换时间，增删查改效率为O（logN）

2. 为什么需要跳表

• 把有序数组通过二分查找的思想搬到了链表上
  • 有序数组可以通过二分查找实现O(logN)的效率，但是有序链表却只能实现O(N)的效率，这个不合理
• 红黑树实现太复杂，需要有一种替代红黑树的数据结构，这种数据结构就是跳表

3. 实现

3.1. 数据结构

• 虚拟头节点
  • key
  • value
  • node指针数组
• 有效层数

3.2. API

type ISkipList interface {
	//打印跳表
	String() string
	//跳表元素个数
	Length() int
	//跳表是否为空
	IsEmpty() bool
	//往跳表添加一个元素，O（logN）
	Put(key model.Comparable, value interface{})
	//跳表是否包含key，O（logN）
	Contains(key model.Comparable) bool
	//获取跳表中key对应的value，O（logN）
	Get(key model.Comparable) (interface{}, bool)
	//删除跳表中key对应的元素，O（logN）
	Remove(key model.Comparable)
}

3.3. 实现

const (
	//概率值
	P = 0.25
	//最高层数
	MaxLevel = 32
)

type node struct {
	key   model.Comparable
	value interface{}
	next  []*node
}

func (n *node) String() string {
	return fmt.Sprintf("[%v:%v]", n.key, n.value)
}

func NewNode(key model.Comparable, value interface{}, level int) *node {
	return &node{
		key:   key,
		value: value,
		next:  make([]*node, level, level)}
}

type SkipList struct {
	//虚拟头节点
	dummyHead *node
	//有效层数
	level int
	//节点数目
	length int
}

func NewSkipList() *SkipList {
	return &SkipList{
		dummyHead: NewNode(nil, nil, MaxLevel),
		level:     0,
		length:    0,
	}
}

func (s *SkipList) String() string {
	str := fmt.Sprintf("length=%v, level=%v, data={", s.length, s.level)
	for i := s.level - 1; i >= 0; i-- {
		current := s.dummyHead
		for current.next[i] != nil {
			str = fmt.Sprintf("%s%v ", str, current.next[i])
			current = current.next[i]
		}
		str = strings.TrimRight(str, " ")
		str += "\n"
	}
	str = strings.TrimRight(str, "\n")

	str += "}"
	return str
}

func (s *SkipList) Length() int {
	return s.length
}

func (s *SkipList) IsEmpty() bool {
	return s.length == 0
}

func (s *SkipList) Put(key model.Comparable, value interface{}) {
	current := s.dummyHead
	//新增链表中的某个节点，需要直到前一个节点
	prev := make([]*node, s.level, s.level)
	for i := s.level - 1; i >= 0; i-- {
		cmp := -1
		for current.next[i] != nil {
			cmp = key.CompareTo(current.next[i].key)
			if cmp <= 0 {
				break
			}
			current = current.next[i]
		}

		//找到了，修改value即可
		if cmp == 0 {
			current.next[i].value = value
			return
		}

		//这里是cmp<0，就是前一个节点，保存起来以便新增
		prev[i] = current
	}

	//新增一个节点
	newLevel := randomLevel()
	newNode := NewNode(key, value, newLevel)
	for i := 0; i < newLevel; i++ {
		//level比现有的大，创建一个新的链表
		if i >= s.level {
			s.dummyHead.next[i] = newNode
		} else {
			//链表中间插入一个节点
			newNode.next[i] = prev[i].next[i]
			prev[i].next[i] = newNode
		}
	}

	s.level = util.Max(s.level, newLevel)
	s.length++
}

func (s *SkipList) Contains(key model.Comparable) bool {
	_, ok := s.Get(key)
	return ok
}

func (s *SkipList) Get(key model.Comparable) (interface{}, bool) {
	current := s.dummyHead
	//1.从最高层开始，一步步往下层找
	for i := s.level - 1; i >= 0; i-- {
		cmp := -1
		//2.每层都是一个链表，一个个节点比较
		for current.next[i] != nil {
			//3.如果节点key比要找的key大，继续往右
			cmp = key.CompareTo(current.next[i].key)
			//4.找到了或者当前节点比要找的key小
			if cmp <= 0 {
				break
			}
			current = current.next[i]
		}
		//4.1 找到了就返回
		if cmp == 0 {
			return current.next[i].value, true
		}
		//4.2 往下一层找
	}

	return nil, false
}

func (s *SkipList) Remove(key model.Comparable) {
	current := s.dummyHead
	//删除链表中的某个节点，需要知道前一个节点
	prev := make([]*node, s.level, s.level)
	exists := false
	for i := s.level - 1; i >= 0; i-- {
		cmp := -1
		for current.next[i] != nil {
			cmp = key.CompareTo(current.next[i].key)
			if cmp <= 0 {
				break
			}
			current = current.next[i]
		}

		if cmp == 0 {
			exists = true
		}
		prev[i] = current
	}

	//不存在还删个鬼
	if !exists {
		return
	}

	//删除链表中的节点
	removedNode := current.next[0]
	for i := 0; i < len(removedNode.next); i++ {
		prev[i].next[i] = removedNode.next[i]
	}

	//删除一个节点后，层数可能会减少
	//怎么判断减少呢？next为空就是减少了
	newLevel := s.level - 1
	for newLevel > 0 && s.dummyHead.next[newLevel] == nil {
		s.level = newLevel
		newLevel--
	}

	s.length--
}

func randomLevel() int {
	level := 1
	//给level加一个随机值，但是level最终不能大于MaxLevel
	for rand.Float64() < P && level < MaxLevel {
		level++
	}
	return level
}

3.3.1. 测试

func TestSkipList(t *testing.T) {
	skipList := NewSkipList()
	e0 := model.NewElement(0)
	skipList.Put(e0, "e0")
	for i := 1; i < 100; i++ {
		e := model.NewElement(i)
		skipList.Put(e, fmt.Sprintf("e%v", i))

	}

	fmt.Println("添加元素后：", skipList)

	fmt.Println("是否包含e0：", skipList.Contains(e0))
	get, _ := skipList.Get(e0)
	fmt.Println("e0对应的数据：", get)

	skipList.Remove(e0)
	fmt.Println("删除e0后：", skipList)

	skipList.Remove(model.NewElement(6))
	fmt.Println("删除e6后：", skipList)

	skipList.Remove(model.NewElement(87))
	fmt.Println("删除e87后：", skipList)
}

4. 参考

• 【恋上数据结构】跳表（Skip List）原理及实现_Jerry House-CSDN博客
• 17-跳表:为什么Redis一定要用跳表来实现有序集合？ | H.’s Blog