跳表
golang数据结构篇之跳表
关于跳表先吃透inset代码即可
sortedset
redis中的sortedset的类型就是跳表,其中的element有member和score,在跳表的基础上对其封装命令对应的api即可
代码
border.go
package sortedset import ( "errors" "strconv" ) const ( negativeInf int8 = -1 //负无穷 positiveInf int8 = 1 //正无穷 ) type ScoreBorder struct { Inf int8 Value float64 Exclude bool //不包括 } var positiveInfBorder = &ScoreBorder{ Inf: positiveInf, } var negativeInfBorder = &ScoreBorder{ Inf: negativeInf, } //max.greater(score) 返回true说明在最大范围内 func (border *ScoreBorder) greater(value float64) bool { if border.Inf == negativeInf { return false } else if border.Inf == positiveInf { return true } if border.Exclude { return border.Value > value } return border.Value >= value } //min.less(score) 返回true说明在最小范围内 func (border *ScoreBorder) less(value float64) bool { if border.Inf == negativeInf { return true } else if border.Inf == positiveInf { return false } if border.Exclude { return border.Value < value } return border.Value <= value } // ParseScoreBorder 从reids-cli发来的命令中解析args创建ScoreBorder func ParseScoreBorder(s string) (*ScoreBorder, error) { if s == "inf" || s == "+inf" { return positiveInfBorder, nil } if s == "-inf" { return negativeInfBorder, nil } if s[0] == '(' { //不包括value value, err := strconv.ParseFloat(s[1:], 64) if err != nil { return nil, errors.New("ERR min or max is not a float") } return &ScoreBorder{ Inf: 0, Value: value, Exclude: true, }, nil } value, err := strconv.ParseFloat(s, 64) if err != nil { return nil, errors.New("ERR min or max is not a float") } return &ScoreBorder{ Inf: 0, Value: value, Exclude: false, }, nil }
skiplist.go
package sortedset import ( "fmt" "math/rand" "time" ) const ( maxLevel = 16 ) // Element 对外的元素抽象 type Element struct { Member string Score float64 } // Level 节点Node中每一层的抽象 type Level struct { forward *Node span int64 } // Node 节点Node type Node struct { Element backward *Node level []*Level } //跳表 type skipList struct { header *Node tail *Node length int64 level int16 } func makeNode(level int16, score float64, member string) *Node { n := &Node{ Element: Element{ Score: score, Member: member, }, level: make([]*Level, level), } for i := range n.level { n.level[i] = new(Level) } return n } func makeSkipList() *skipList { return &skipList{ level: 1, header: makeNode(maxLevel, 0, ""), } } //在跳表中插入节点 func (skiplist *skipList) insertElement(member string, score float64) *Node { //既然要插入一个节点,那么就要找到新节点插入位置的前驱节点,这个前驱节点的forward会指向新节点 //因为插入一个新节点会影响很多层,所以每层都会有一个对应的前驱节点 updatePre := make([]*Node, maxLevel) //保存各层前驱节点的排名(前驱节点是第几个),用于计算span,span是与下一个节点的距离 rankPre := make([]int64, maxLevel) //刚开始从header节点开始查找 node := skiplist.header for i := skiplist.level - 1; i >= 0; i-- { if i != skiplist.level-1 { //下一层的rank肯定从上一层的rank开始记录的 rankPre[i] = rankPre[i+1] } if node.level[i] != nil { //遍历搜素,找到第i层的前驱节点,然后记录第i层的rank for (node.level[i].forward != nil && node.level[i].forward.Score < score) || (node.level[i].forward != nil && node.level[i].forward.Score == score && node.level[i].forward.Member < member) { rankPre[i] += node.level[i].span node = node.level[i].forward } } //记录第i层的前驱节点是哪个Node updatePre[i] = node } // 随机决定新节点的层数 level := randLevel() //可能新层数超过了最高层,那么此时要创建新的层 if level > skiplist.level { for i := skiplist.level; i < level; i++ { updatePre[i] = skiplist.header updatePre[i].level[i].span = skiplist.length } //更新最高层 skiplist.level = level } //创建新节点 node = makeNode(level, score, member) //前驱节点找到了,排名也统计了,该插入到跳表中了 for i := int16(0); i < level; i++ { //新节点的forward指向前驱节点的forward node.level[i].forward = updatePre[i].level[i].forward //前驱节点的forward指向新的节点 updatePre[i].level[i].forward = node //至此,当前层(level--> i)插入成功 //接下来更新前驱节点的span和新节点的span node.level[i].span = updatePre[i].level[i].span - (rankPre[0] - rankPre[i]) updatePre[i].level[i].span = rankPre[0] - rankPre[i] + 1 } //因为新的节点可能不会包含所有的层,所以对于没有的层 //上面的前驱节点的span要加1,因为新插入了一个节点 for i := level; i < skiplist.level; i++ { updatePre[i].level[i].span++ } //更新前向指针 if updatePre[0] == skiplist.header { node.backward = nil //这种情况发生于插入的位置就在header的后面 } else { node.backward = updatePre[0] //最近的前驱节点Node } if node.level[0].forward != nil { node.level[0].forward.backward = node //后一个的前向指针指自己,这种情况发生于插入位置在中间 } else { skiplist.tail = node //这种情况插入位置在最后 } skiplist.length++ return node } func randLevel() int16 { //level := int16(1) //for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) { // level++ //} //if level < maxLevel { // return level //} //return maxLevel level := int16(1) for rand.Intn(2) != 1 { level++ } if level < maxLevel { return level } return maxLevel } func (skiplist *skipList) PrintShipList() { fmt.Println("start") for i := int(skiplist.level) - 1; i >= 0; i-- { node := skiplist.header if node.level[i].forward == nil { continue } for j := 0; j <= int(skiplist.length); j++ { if node == skiplist.header { fmt.Printf("level:%d-head---", i+1) } else { fmt.Printf("[%d]", int(node.Score)) } cnt := int(node.level[i].span - 1) for x := 1; x <= cnt; x++ { fmt.Printf("----") } j += cnt if node.level[i].forward == nil { break } else { node = node.level[i].forward } } fmt.Printf("\n") } fmt.Println("end") } //寻找排名为rank的节点,rank是从1开始的 func (skiplist *skipList) getNodeByRank(rank1 int64) *Node { var rank int64 node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { //从高层往底层搜索 //若当前层的下一个节点已经超过目标--->rank+node.level[level].span>rank for node.level[level].forward != nil && (rank+node.level[level].span) <= rank1 { rank += node.level[level].span node = node.level[level].forward } if rank == rank1 { return node } } return node } //传入需要删除的节点和删除后的前驱节点 //批量删除的时候updatePre是相同的 func (skiplist *skipList) removeNodeByNode(node *Node, updatePre []*Node) { for i := int16(0); i < skiplist.level; i++ { //如果先去节点的forward指针指向了删除节点,则需要修改前驱节点的forward,同时更新前驱节点的span if updatePre[i].level[i].forward == node { updatePre[i].level[i].forward = node.level[i].forward updatePre[i].level[i].span += node.level[i].span - 1 } else { updatePre[i].level[i].span-- } } //修改删除节点的前向指针 if node.level[0].forward != nil { node.level[0].forward.backward = node.backward } else { skiplist.tail = node.backward } //跳表节点数量减一 skiplist.length-- //删除空白的层 for skiplist.level > 1 && skiplist.header.level[skiplist.level-1].forward == nil { skiplist.level-- } } // removeRangeByRank 删除操作一次删除多个节点 func (skiplist *skipList) removeRangeByRank(start int64, stop int64) (removed []*Element) { var rank int64 updatePre := make([]*Node, maxLevel) removed = make([]*Element, 0) //从高层往底层搜索 node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { for node.level[level].forward != nil && (rank+node.level[level].span) < start { rank += node.level[level].span node = node.level[level].forward } updatePre[level] = node } rank++ //rank就是start node = node.level[0].forward //node就是范围内第一个节点 //删除范围内所有的节点 for node != nil && rank < stop { next := node.level[0].forward removedElement := node.Element removed = append(removed, &removedElement) skiplist.removeNodeByNode(node, updatePre) node = next rank++ } return removed } func (skiplist *skipList) removeByElement(member string, score float64) bool { updatePre := make([]*Node, maxLevel) node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { for node.level[level].forward != nil && (node.level[level].forward.Score < score || node.level[level].forward.Score == score && node.level[level].forward.Member < member) { node = node.level[level].forward } updatePre[level] = node } node = node.level[0].forward //Node for Element if node != nil && node.Score == score && member == node.Member { skiplist.removeNodeByNode(node, updatePre) return true } return false } //return 0表示没有该元素 func (skiplist *skipList) getRankByElement(member string, score float64) int64 { var rank int64 node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { for node.level[level].forward != nil && (node.level[level].forward.Score < score || node.level[level].forward.Score == score && node.level[level].forward.Member <= member) { rank += node.level[level].span node = node.level[level].forward } } if node.Member == member { return rank } return 0 } //是否在范围内 func (skiplist *skipList) hasInRange(min *ScoreBorder, max *ScoreBorder) bool { //min>=max本身就出错了 min & max = empty if min.Value > max.Value || (min.Value == max.Value) && (min.Exclude || max.Exclude) { return false } // min > tail node := skiplist.tail if node == nil || !min.less(node.Score) { return false } // max < head node = skiplist.header.level[0].forward if node == nil || !max.greater(node.Score) { return false } return true } //获得在score范围内的第一个Node func (skiplist *skipList) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *Node { if !skiplist.hasInRange(min, max) { return nil } node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { //如果不在less之上则切换到下一个Node for node.level[level].forward != nil && !min.less(node.level[level].forward.Score) { node = node.level[level].forward } } node = node.level[0].forward //第一个在(min,+INF)中的Node if !max.greater(node.Score) { return nil } return node } //获得在score范围内的最后一个Node func (skiplist *skipList) getLastInScoreRange(min *ScoreBorder, max *ScoreBorder) *Node { if !skiplist.hasInRange(min, max) { return nil } node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { //如果不在less之上则切换到下一个Node for node.level[level].forward != nil && !max.greater(node.level[level].forward.Score) { node = node.level[level].forward } } node = node.level[0].forward //第一个在(min,+INF)中的Node if !min.less(node.Score) { return nil } return node } //删除在score范围内的节点,范围删除元素的集合 func (skiplist *skipList) RemoveRangeByScore(min *ScoreBorder, max *ScoreBorder) (removed []*Element) { updataPre := make([]*Node, maxLevel) removed = make([]*Element, 0) node := skiplist.header for level := skiplist.level - 1; level >= 0; level-- { for node.level[level].forward != nil { if min.less(node.level[level].forward.Score) { break //已经在范围内了 } node = node.level[level].forward } updataPre[level] = node } node = node.level[0].forward //范围内的第一个Node for node != nil { if !max.greater(node.Score) { break //不在范围内了 } next := node.level[0].forward removedElement := node.Element removed = append(removed, &removedElement) skiplist.removeNodeByNode(node, updataPre) node = next } return removed } func main() { sl := makeSkipList() rand.Seed(time.Now().UnixNano()) mp := make(map[int]int) for i := 0; i < 50; i++ { cnt := 0 for !(cnt >= 10 && cnt <= 99) { cnt = (rand.Intn(10000) + 100) % 100 mp[cnt]++ if mp[cnt] > 1 { cnt = 0 } } sl.insertElement("", float64(cnt)) } sl.getNodeByRank(1) sl.PrintShipList() sl.removeRangeByRank(1, 5) sl.PrintShipList() }
sortedset.go
package sortedset import "strconv" type SortedSet struct { skiplist *skipList dict map[string]*Element } func MakeSortedSet() *SortedSet { return &SortedSet{ skiplist: makeSkipList(), dict: make(map[string]*Element), } } // AddElement 将成员放入集合中,并返回是否已插入新节点 func (sortedSet *SortedSet) AddElement(member string, score float64) bool { element, ok := sortedSet.dict[member] sortedSet.dict[member] = &Element{ Member: member, Score: score, } if ok { if score != element.Score { sortedSet.skiplist.removeByElement(member, element.Score) sortedSet.skiplist.insertElement(member, score) //相同member更新score } return false } sortedSet.skiplist.insertElement(member, score) return true } // ElementLen Len 返回集合中的成员数 func (sortedSet *SortedSet) ElementLen() int64 { return int64(len(sortedSet.dict)) } // GetElement Get 通过member返回元素 func (sortedSet *SortedSet) GetElement(member string) (element *Element, ok bool) { element, ok = sortedSet.dict[member] if !ok { return nil, false } return element, true } // RemoveElement Remove 移除从集合中移除member func (sortedSet *SortedSet) RemoveElement(member string) bool { element, ok := sortedSet.dict[member] if ok { sortedSet.skiplist.removeByElement(element.Member, element.Score) delete(sortedSet.dict, member) return true } return false } // GetRank 返回给定member的排名,按desc排序,排名从0开始 func (sortedSet *SortedSet) GetRank(member string, desc bool) (rank int64) { element, ok := sortedSet.dict[member] if !ok { return -1 } rank = sortedSet.skiplist.getRankByElement(element.Member, element.Score) if desc { rank = sortedSet.skiplist.length - rank } else { rank-- } return rank } // ForEach 访问[start,stop]中排名的每个元素,按desc排序,排名从0开始 func (sortedSet *SortedSet) ForEach(start int64, stop int64, desc bool, consumer func(element *Element) bool) { elementLen := sortedSet.ElementLen() if start < 0 || start >= elementLen { panic("illegal start " + strconv.FormatInt(start, 10)) } if stop < start || stop > elementLen { panic("illegal end " + strconv.FormatInt(stop, 10)) } var node *Node if desc { node = sortedSet.skiplist.tail if start > 0 { node = sortedSet.skiplist.getNodeByRank(elementLen - start) } } else { node = sortedSet.skiplist.header.level[0].forward if start > 0 { node = sortedSet.skiplist.getNodeByRank(start + 1) } } sliceSize := stop - start for i := 0; i < int(sliceSize); i++ { if consumer(&node.Element) == false { break } if desc { node = node.backward } else { node = node.level[0].forward } } } // Range 返回排名在[start,stop]内的元素,按desc排序,排名从0开始 func (sortedSet *SortedSet) Range(start int64, stop int64, desc bool) []*Element { elementSlice := make([]*Element, stop-start) i := 0 sortedSet.ForEach(start, stop, desc, func(element *Element) bool { elementSlice[i] = element i++ return true }) return elementSlice } // Count 返回在给定边界内得分的元素数量 func (sortedSet *SortedSet) Count(min *ScoreBorder, max *ScoreBorder) int64 { i := 0 sortedSet.ForEach(0, sortedSet.ElementLen(), false, func(element *Element) bool { if !min.less(element.Score) { return true //还没进入到最小边界,接着下一个 } if !max.greater(element.Score) { return false //超过了最大范围,停止计数 } i++ return true }) return int64(i) } // ForEachByScore 访问在给定边界内得分的元素 func (sortedSet *SortedSet) ForEachByScore(min *ScoreBorder, max *ScoreBorder, offset int64, limit int64, desc bool, consumer func(element *Element) bool) { // 找到第一个node var node *Node if desc { node = sortedSet.skiplist.getLastInScoreRange(min, max) } else { node = sortedSet.skiplist.getFirstInScoreRange(min, max) } //偏移到第一个node for node != nil && offset > 0 { if desc { node = node.backward } else { node = node.level[0].forward } offset-- } for i := 0; (i < int(limit) || limit < 0) && node != nil; i++ { if consumer(&node.Element) == false { break } if desc { node = node.backward } else { node = node.level[0].forward } if node == nil { break } if !min.less(node.Element.Score) || !max.greater(node.Element.Score) { break //不在范围内了,也退出 } } } // RangeByScore 返回在给定边界内得分的元素 参数限制:limit<0表示没有限制 func (sortedSet *SortedSet) RangeByScore(min *ScoreBorder, max *ScoreBorder, offset int64, limit int64, desc bool) []*Element { if limit == 0 || offset < 0 { return make([]*Element, 0) } elementSlice := make([]*Element, 0) sortedSet.ForEachByScore(min, max, offset, limit, desc, func(element *Element) bool { elementSlice = append(elementSlice, element) return true }) return elementSlice } // RemoveByScore 删除在给定边界内得分的元素 func (sortedSet *SortedSet) RemoveByScore(min *ScoreBorder, max *ScoreBorder) int64 { removed := sortedSet.skiplist.RemoveRangeByScore(min, max) for _, element := range removed { delete(sortedSet.dict, element.Member) } return int64(len(removed)) } // RemoveByRank RemoveByRank删除[开始,停止)中的成员排名 ,排名从0开始 func (sortedSet *SortedSet) RemoveByRank(start int64, stop int64) int64 { removed := sortedSet.skiplist.removeRangeByRank(start+1, stop+1) for _, element := range removed { delete(sortedSet.dict, element.Member) } return int64(len(removed)) }