skiplist

README

Skip List Implementation in Go

What is it ?

Skip list is a probabilistic data structure which keeps its elements in order. It behaves like sorted map. It provides O(log n) insertion, deletion and search time. For more look at Wikipedia

Simple Usage

package main

import (
	"fmt"
	"github.com/emin/skiplist"
)

func main(){
    // use string keys only
    list := skiplist.New(skiplist.StringComparator)
    list.Set("key-1", []byte("byte slice data"))
    list.Set("key-2", "string data")
    list.Set("key-3", 999)
    v := list.Get("key-2")
    fmt.Println(v)
    if list.Delete("key-2") {
        fmt.Println("key-2 is deleted")
    }
}

Iterating over skip list

package main

import (
	"fmt"
	"github.com/emin/skiplist"
)

func main(){
    // use int keys only
    list := skiplist.New(skiplist.IntComparator)
    list.Set(1, "data-1")
    list.Set(3, "data-3")
    list.Set(2, "data-2")
    
    it := list.Iterator()
    for it.Next() {
    	fmt.Printf("%v = %v \n", it.Key(), it.Value())
    }
}

For more examples, look at examples/ folder in the project.

Skiplist Interface

New(comparator func(interface{}, interface{}) int) *SkipList
Get(key interface{}) interface{}
Delete(key interface{}) bool
Set(key, value interface{})
KeyCount() int64
Iterator() Iterator

For more, look at

Benchmarks

Run on M1 Macbook Air 8GB model.

go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/emin/skiplist
BenchmarkSetString-8   	 1866468	       626.2 ns/op	     582 B/op	       5 allocs/op
BenchmarkSetInt-8      	 2842914	       438.2 ns/op	     559 B/op	       6 allocs/op
BenchmarkGetString-8   	 4044667	       277.7 ns/op	      16 B/op	       1 allocs/op
BenchmarkGetInt-8      	 8329945	       146.1 ns/op	       7 B/op	       0 allocs/op
BenchmarkGetHash-8     	24889994	        48.52 ns/op	       0 B/op	       0 allocs/op

At the last row BenchmarkGetHash-8 is map[string]string, I compared the numbers with hashtable performance while developing the code. Decided to left it as something to compare for you. Don't forget hashtable has O(1) access, skip list is O(log n).

License

MIT License

Documentation

Overview

This is a skip list implementation in Go. Skip list is a probabilistic data structure which stores elements in order. It provides O(log n) insert and search complexity. (For more: https://en.wikipedia.org/wiki/Skip_list )

Index

• type Iterator
• type SkipList
  • func New() *SkipList
  • func (list *SkipList) Delete(key []byte) bool
  • func (list *SkipList) Get(key []byte) []byte
  • func (list *SkipList) Iterator() Iterator
  • func (list *SkipList) KeyCount() int64
  • func (list *SkipList) RawSize() int64
  • func (list *SkipList) Set(key []byte, value []byte)

Types

type Iterator

type Iterator interface {
	Next() bool
	Key() []byte
	Value() []byte
}

A generic Iterator for going over values on specific point on SkipList.

Example usage;

for iter.Next() {
	fmt.Println(iter.Value());
}

type SkipList

type SkipList struct {
	// contains filtered or unexported fields
}

SkipList implementation

func New

func New() *SkipList

Returns a new SkipList

func (*SkipList) Delete

func (list *SkipList) Delete(key []byte) bool

Deletes key from SkipList

func (*SkipList) Get

func (list *SkipList) Get(key []byte) []byte

Return value for given key if key does not exists, it returns nil

func (*SkipList) Iterator

func (list *SkipList) Iterator() Iterator

Returns an iterator for SkipList

func (*SkipList) KeyCount

func (list *SkipList) KeyCount() int64

Returns how many keys currently in SkipList

func (*SkipList) RawSize

func (list *SkipList) RawSize() int64

func (*SkipList) Set

func (list *SkipList) Set(key []byte, value []byte)

Sets value for key in SkipList