|
hashtable的是由dict这个结构来实现的, dict是一个字典，其中的指针dicht ht[2] 指向了两个哈希表
- typedef struct dict {
- dictType *type;
- void *privdata;
- dictht ht[2];
- long rehashidx; /* rehashing not in progress if rehashidx == -1 */
- int iterators; /* number of iterators currently running */
- } dict;
- typedef struct dictht {
- dictEntry **table;
- unsigned long size;
- unsigned long sizemask;
- unsigned long used;
- } dictht;
dicht[0] 是用于真正存放数据，dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。
dictht中的table用语真正存放元素了，每个key/value对用一个dictEntry表示，放在dictEntry数组中。
集合对象的编码可以是intset或者hashtable
intset是一个整数集合，里面存的为某种同一类型的整数，支持如下三种长度的整数：
- #define INTSET_ENC_INT16 (sizeof(int16_t))
- #define INTSET_ENC_INT32 (sizeof(int32_t))
- #define INTSET_ENC_INT64 (sizeof(int64_t))
intset是一个有序集合，查找元素的复杂度为O(logN)，但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数，这时要插入一个int32_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32_t类型，涉及到内存的重新分配，这时插入的复杂度就为O(N)了。
intset不支持降级操作。
有序集合的编码可能两种，一种是ziplist，另一种是skiplist与dict的结合。
ziplist作为集合和作为哈希对象是一样的，member和score顺序存放。按照score从小到大顺序排列
skiplist是一种跳跃表，它实现了有序集合中的快速查找，在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单，可以作为平衡树的替代品。它的结构比较特殊。下面分别是跳跃表skiplist和它内部的节点skiplistNode的结构体：
- /*
- * 跳跃表
- */
- typedef struct zskiplist {
- // 头节点，尾节点
- struct zskiplistNode *header, *tail;
- // 节点数量
- unsigned long length;
- // 目前表内节点的最大层数
- int level;
- } zskiplist;
- /* ZSETs use a specialized version of Skiplists */
- /*
- * 跳跃表节点
- */
- typedef struct zskiplistNode {
- // member 对象
- robj *obj;
- // 分值
- double score;
- // 后退指针
- struct zskiplistNode *backward;
- // 层
- struct zskiplistLevel {
- // 前进指针
- struct zskiplistNode *forward;
- // 这个层跨越的节点数量
- unsigned int span;
- } level[];
- } zskiplistNode;
head和tail分别指向头节点和尾节点，然后每个skiplistNode里面的结构又是分层的(即level数组)
用图表示，大概是下面这个样子：
总结 （编辑：成都站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
