文章 212
评论 0
浏览 119887
golang实现BST和AVL

golang实现BST和AVL

AVL树得名于它的发明者 G. M. Adelson-Velsky和 E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它,它是最早的自平衡二分搜索树。

golang实现跳表(SkipList)

golang实现跳表(SkipList)

跳表的理解 如果要维护一组有序的整数序列,支持高效的插入删除和搜索,并且能维护序列的有序性。可以选择的数据结构是有限的,哈希表虽然支持常数时间复杂度的增删查,但是hashmap不能维护有序性。红黑树可以维持有序性,并且增加删除修改的性能也很好,但是红黑树不能支持范围搜索。跳表这种数据结构利用空间换时间,性能和红黑树比肩,还能支持区间搜索,在redis和leveldb等开源项目中都用被应用。 跳表的结构如图所示: 在最底层包含了所有的数据节点,每一层链表都有一个指向下一层和自己相同的节点,向后的指针指向随机的同一层比自己大的数据。 时间复杂度分析 不难理解,对于一个有n个节点的链表,如果每两个节点会提取出一个节点作为索引节点,那么第一层的节点个数为n/2,再往上一层,节点数变成n/4,以此类推,第k层的索引个数为n/(2^k),假设层数有x层,并且第x层的节点个数为2,也就是n/(2^x) = 2,所以x = (logn - 1),而第0层是链表本身,所以整个跳表的高度就是logn,如果每一层都需要遍历m个节点,那么在跳表中查询某个数的时间复杂度就是O(m * log(n))。 简单的....

一致性哈希的golang实现

一致性哈希的golang实现

一致性hash算法在1997年由麻省理工学院 karger等人在解决分布式Cache中提出。一个好的hash算法应该满足四个条件:均衡性(Balance)、单调性(Monotonicity)、分散性(Spread)和负载(Load)。

go语言的原生map引发的一个坑

go语言的原生map引发的一个坑

go语言原生map引发的一个坑 总所周知,go语言原生的map并不是并发安全的,所以为了保证map的并发安全,最简单的方式就是给map加一个锁。 年初写项目的时候,刚接触go语言,冒冒失失的就写出了类似下面这样的代码: package problem import (     "fmt"     "sync" ) type dict struct {     m    map[int]string     lock sync.RWMutex } func NewDict() *dict {     return &dict{m: map[int]string{}} } func (d dict) Set(....

常见的负载均衡算法

常见的负载均衡算法

在分布式系统中,多台服务器同时提供一个服务,往往就需要一个负载均衡算法,来分发流量。 常见的有:随机、加权随机、轮询、加权轮询、平滑加权轮询、源地址hash、最小连接数法。

Nothing just happens, it's all part of a plan.