跳表(skiplist)学习笔记
这段时间公司做了个项目,在项目里面用到了redis,爱学习的我又一次翻出了redis的源代码,从头开始看了起来(没看完,哈哈~~),在这一次阅读中把redis的五大数据结构的代码给看了一遍,对于我这么一个菜鸟来说收获颇多,比如他的hash,list结构都没有使用我们平常使用的双向链表,而是使用一种非常节省内存的方式来实现了链表(zipmap和ziplist),还有zset就使用了跳表,其实levelDB也有使用跳表。
Skip List是在有序List(链表)数据结构的基础上的扩展,解决了有序链表结构查找特定值困难的问题,使用Skip List,可以使得在一个有序链表里查找特定值的时间复杂度为O(logn),他是一种可以代替平衡树的数据结构。Skip lists应用概率保证平衡,平衡树采用严格的旋转(比如平衡二叉树有左旋右旋)来保证平衡,因此Skip list比较容易实现,而且相比平衡树有着较高的运行效率。 其实现原理是链表中每一个元素都有N层(N为随机数,并且1<=N [c] #include #include #include typedef int key_t; typedef int value_t; typedef struct node_t { key_t key; value_t value; struct node_t *forward[]; } node_t; typedef struct skiplist { int level; int length; node_t *header; } list_t; #define MAX_LEVEL 16 #define SKIPLIST_P 0.25 node_t* slCreateNode(int level, key_t key, value_t value) { node_t *n = (node_t *)malloc(sizeof(node_t) + level * sizeof(node_t*)); if(n == NULL) return NULL; n->key = key; n->value = value; return n; } list_t* slCreate(void) { list_t *l = (list_t *)malloc(sizeof(list_t)); int i = 0; if(l == NULL) return NULL; l->length = 0; l->level = 0; l->header = slCreateNode(MAX_LEVEL - 1, 0, 0); for(i = 0; i < MAX_LEVEL; i++) { l->header->forward[i] = NULL; } return l; } int randomLevel(void) { int level = 1; while ((rand()&0xFFFF) < (SKIPLIST_P * 0xFFFF)) level += 1; return (levelheader; int i; for(i = list->level - 1; i >= 0; i-) { while(p->forward[i] && (p->forward[i]->key forward[i]->key == key){ return &p->forward[i]->value; } p = p->forward[i]; } } return NULL; } int slDelete(list_t *list, key_t key) { node_t *update[MAX_LEVEL]; node_t *p = list->header; node_t *last = NULL; int i = 0; for(i = list->level - 1; i >= 0; i-){ while((last = p->forward[i]) && (last->key < key)){ p = last; } update[i] = p; } if(last && last->key == key){ for(i = 0; i < list->level; i++){ if(update[i]->forward[i] == last){ update[i]->forward[i] = last->forward[i]; } } free(last); for(i = list->level - 1; i >= 0; i-){ if(list->header->forward[i] == NULL){ list->level-; } } list->length-; }else{ return -1; } return 0; } int slInsert(list_t *list, key_t key, value_t value) { node_t *update[MAX_LEVEL]; node_t *p, *node = NULL; int level, i; p = list->header; for(i = list->level - 1; i >= 0; i-){ while((node = p->forward[i]) && (node->key < key)){ p = node; } update[i] = p; } if(node && node->key == key){ node->value = value; return 0; } level = randomLevel(); if (level > list->level) { for(i = list->level; i < level; i++){ update[i] = list->header; } list->level = level; } node = slCreateNode(level, key, value); for(i = 0; i < level; i++){ node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = node; } list->length++; return 0; } int main(int argc, char **argv) { list_t *list = slCreate(); node_t *p = NULL; value_t *val = NULL; //插入 for(int i = 1; i header->forward[0]; for(int i = 0; i < list->length; i++){ printf(“%d,%d\\n”, p->key, p->value); p = p->forward[0]; } getchar(); return 0; } [/c]建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:IM鑫爷 来源: IM鑫爷
- 标签: skiplist 跳表
- 发布时间:2011-09-21 13:41:20
- [67] Oracle MTS模式下 进程地址与会话信
- [66] Go Reflect 性能
- [65] 如何拿下简短的域名
- [61] android 开发入门
- [61] 【社会化设计】自我(self)部分――欢迎区
- [60] 图书馆的世界纪录
- [60] IOS安全–浅谈关于IOS加固的几种方法
- [54] 视觉调整-设计师 vs. 逻辑
- [49] 读书笔记-壹百度:百度十年千倍的29条法则
- [48] 界面设计速成