Golang实践----跳表

# 目录 - [跳表简介](#跳表简介) - [skipList](#skiplist) * [跳表示意图](#跳表示意图) * [跳表实现简要介绍](#跳表实现简要介绍) * [跳表使用介绍](#跳表使用介绍) * [github code](#github code) # 跳表简介 跳跃链表是对链表的改进，链表虽然节省空间，但是查找时间复杂度为O（n），效率比较低。 跳跃链表的查找、插入、删除等操作的期望时间复杂度为O(logn)，效率比链表提高了很多。 跳表的基本性质 1. 有很多层结构组成 2. 每一层都是一个有序的链表 3. 最底层(level 0)的链表包含所有元素 4. 如果一个元素出现在level i的链表中，则在level i之下的链表都会出现 5. 每个节点包含两个指针，一个指向同一链表的下一个元素，一个指向下面一层的元素 # skipList ## 跳表示意图 以int类型，最大4层的跳表示意图如下  ## 跳表实现简要介绍 skipList结构如下 ``` type Node struct { O SkipListObj forward []*Node curLevel int } type SkipList struct { head *Node length int maxLevel int lockType int lock sync.Locker } ``` 目前只实现了针对int类型数据的接口，若使用其他类型，需要实现下面这个接口 ``` type SkipListObj interface { Compare(obj SkipListObj) bool PrintObj() } ``` 其中Compare()表示数据大小比较， 一开始本想用Compare(obj interface{}) bool作为接口，但是编译报错，提示type interface {} is interface with no methods，于是改用了上面的接口 由于Go内置类型用户不能新建接口（会编译失败，对于int类型提示cannot define new methods on non-local type int），可以通过type给int取个别名来实现接口 ``` type myInt int func (a *myInt) Compare(b skipList.SkipListObj) bool { return *a < *b.(*myInt) } ``` PrintObj()用于打印数据的，主要是用于遍历显示跳表的Traverse()，对于int类型如下 ``` func (a *myInt) PrintObj() { fmt.Print(*a) } ``` CreateSkipList用于创建一个skip list，需要传入一个对任意其他对象Compare()函数都返回false的对象（例如对于example的实现就是传入最小的int整数）， 还需要传入一个表示skip list最大层数以及一个可选的参数mode表示创建的skip list的锁类型，若 mode = 1, 则为互斥锁 mode = 2, 则为读写锁 其他为无锁 func CreateSkipList(minObj SkipListObj, args ...int) (*SkipList, error) lockList主要用于在操作skip list前上锁，可根据配置来决定使用： 1. 无锁 2. 互斥锁 3. 读写锁 ``` func (s *SkipList) lockList(mode int) { if s.lockType == 0 { return } switch mode { case 1: s.lock.Lock() case 2: if s.lockType == 1 { s.lock.Lock() } else if s.lockType == 2 { s.lock.(*sync.RWMutex).RLock() } default: return } } ``` unLockList相应地解锁 func (s *SkipList) unLockList(mode int) Search()用于在skip list中查找指定的对象 func (s *SkipList) Search(o SkipListObj) (SkipListObj, error) SearchRange()用于在skip list中按照指定范围查找对象 func (s *SkipList) SearchRange(minObj, maxObj SkipListObj) ([]SkipListObj, error) Insert()用于在skip list中插入一个对象 思路是从最高层开始遍历直到不满足Compare()条件，对于example即是找到最后一个小于目标的节点，然后将新节点插入这个节点的后面 func (s *SkipList) Insert(obj SkipListObj) (bool, error) ``` func (s *SkipList) Insert(obj SkipListObj) (bool, error) { v, err := checkSkipListValid(s) if v == false { return false, err } var p *Node = s.head newNode := new(Node) newNode.O = obj newNode.forward = make([]*Node, s.maxLevel) level := s.createNewNodeLevel() s.lockList(1) defer s.unLockList(1) for i := s.maxLevel - 1; i >= 0; i-- { for { if p.forward[i] != nil && p.forward[i].O.Compare(obj) { p = p.forward[i] } else { break } } //find the last Node which match user defined Compare() condition in i level //insert new Node after the node if i <= level { newNode.forward[i] = p.forward[i] p.forward[i] = newNode } } newNode.curLevel = level s.length++ return true, nil } ``` createNewNodeLevel()用于Insert()方法中，为新对象产生其所在的层级 ``` func (s *SkipList) createNewNodeLevel() int { var level int = 0 rand.Seed(time.Now().UnixNano()) for { if rand.Intn(2) == 1 || level >= s.maxLevel-1 { break } level++ } return level } ``` Traverse()用于遍历打印skip list func (s *SkipList) Traverse() ``` func (s *SkipList) Traverse() { v, _ := checkSkipListValid(s) if v == false { return } var p *Node = s.head s.lockList(2) defer s.unLockList(2) for i := s.maxLevel - 1; i >= 0; i-- { for { if p != nil { p.O.PrintObj() if p.forward[i] != nil { fmt.Print("-->") } p = p.forward[i] } else { break } } fmt.Println() p = s.head } } ``` ## 跳表使用介绍 首先必须调用CreateSkipList()创建一个skip list 创建一个最大10层无锁skip list s, err := skipList.CreateSkipList(minObj, 10） 创建一个最大10层使用互斥锁的skip list s, err := skipList.CreateSkipList(minObj, 10, 1) 创建一个最大10层使用读写锁的skip list s, err := skipList.CreateSkipList(minObj, 10, 2) 插入一个对象(以myInt为例) ``` insertObj := new(myInt) *insertObj = myInt(30) t, err := s.Insert(insertObj) if t == true { fmt.Println("insert obj ", *insertObj, " success") } else { fmt.Printf("insert obj %d failed: ", *insertObj, err) } ``` 范围搜索skip list示例(以myInt为例) ``` func searchRangeExample(s *skipList.SkipList) { var minObj, maxObj myInt minObj = 0 maxObj = 30 sliceObj, err := s.SearchRange(&minObj, &maxObj) if err != nil { fmt.Print(err) return } fmt.Println("search range result:") for _, sobj := range sliceObj { fmt.Printf("%d ", *sobj.(*myInt)) } fmt.Println() } ``` 使用LiteIDE（一个轻量级的Go IDE）运行example结果如下：  ## github code - [github code链接](https://github.com/GrassInWind2019/skipList) - `[github code链接](https://github.com/GrassInWind2019/skipList)`