首页 > 新闻中心> 广州校区 >正文

java培训中心哪家好?看粤嵌如何带你入门学习java

更新时间: 2018-09-20 16:32:19来源: 学习java

    现在来看下另外一种数据结构字典的实现原理,字典这种数据结构并不是 Redis 那几种基本数据结构,但是 hash , sets 和 sorted sets 这几种数据结构在底层都是使用字典来实现的(并不仅仅是字典),现在看下它的实现原理。
    结构
    Redis 字典的结构和 Java 中的 HashMap 有点类似,都是存放键值对,在底层都是使用数组加链表(称为一个哈希表)的形式来实现的,但与 HashMap 不同的是,在 Redis 中,它由两个哈希表组成,它的结构大致如下图所示:

java培训机构




    由上图可以看到,它使用两个 hashtable ,姑且称之为 0 号哈希表和 1 号哈希表,每次只会使用 0 号哈希表,那么 1 号哈希表有什么用呢?当哈希表的键值对很多或很少的话,就需要对哈希表进行扩展或缩小,比如哈希表中数组的大小默认为 4 ,如果哈希表中键值对很多,则数组中每项的链表就会很长,而链表查找速度很很慢,不像数组那样根据索引定位,所以为了让哈希表的负载因子(load factor)维持在一个合理的范围内,就需要对哈希表进行扩展或缩小,称为 rehash。
结构定义
接下来看下上述结构图的定义,
首先看下字典结构的定义:
    typedef struct dict {
        dictType *type; //字典类型
        void *privdata; //私有数据
        dictht ht[2]; // 哈希表,有两个,实现渐进式rehash
        long rehashidx; // rehash 索引,当不进行rehash的时候,值为-1
        unsigned long iterators; // 当前正在运行的迭代器的数量
    } dict;

    其中,dictht ht[2] 对应的是上图中的ht[0]和[1]。

    之后,看下哈希表的定义:


    /*
     * 哈希表
     */
    typedef struct dictht {
        // 哈希表数组
        dictEntry **table;
        // 哈希表大小
        unsigned long size;
        unsigned long sizemask;
        // 该哈希表已有节点的数量
        unsigned long used;
    } dictht;

  对应的上图中的哈希表数组,数组中的每一项是链表,链表节点使用 dictEntry 表示,接下来看下 dictEntry 的定义:

    //哈希表节点
    typedef struct dictEntry {
        // 键
        void *key;
        // 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        // 指向下个哈希表节点,形成链表
        struct dictEntry *next;
    } dictEntry;
    以上的定义就表示的字典的数据结构,上述的定义代码是在 dict.h 文件中,该文件中,除了上述代码外,还有一些其他的API定义,如迭代器等。

    接下来看下字典的操作,如添加元素,删除元素,查找元素,rehash 等,这个操作代码主要是在  dict.c 文件中
    字典操作
    首先看下几个公共的方法;
    _dictInit
    初始化哈希表

    int _dictInit(dict *d, dictType *type, void *privDataPtr)
    {
        // 初始化两个哈希表的各项属性值
        // 但暂时还不分配内存给哈希表数组
        _dictReset(&d->ht[0]);
        _dictReset(&d->ht[1]);
        d->type = type; // 设置类型
        d->privdata = privDataPtr; // 设置私有数据
        d->rehashidx = -1; // 设置 rehash的状态,表示不正在rehash
        d->iterators = 0; // 设置安全迭代器数量
        return DICT_OK;
    }

    _dictKeyIndex

    根据 key 来获取添加的这个键值对应该存放在哈希表中的索引。
    //如果 key 已经存在于哈希表,那么返回 -1

    //如果字典正在进行 rehash ,那么总是返回 1 号哈希表的索引。因为在字典进行 rehash 时,新节点总是插入到 1 号哈希表。


    static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
    {
        unsigned long idx, table;
        dictEntry *he;
        if (existing) *existing = NULL;

        // 哈希表是否需要扩展
        if (_dictExpandIfNeeded(d) == DICT_ERR)
            return -1;
        // 遍历 0 号哈希表和 1 号哈希表
        for (table = 0; table <= 1; table++) {
            // 获取哈希表中的每一项
            idx = hash & d->ht[table].sizemask;
            //获取每一项的链表
            he = d->ht[table].table[idx];
            // 遍历链表
            while(he) {
                // 如果key 存在,则放回 -1 
                if (key==he->key || dictCompareKeys(d, key, he->key)) {
                    if (existing) *existing = he;
                    return -1;
                }
                he = he->next;
            }
            // 如果哈希表没有正在进行rehash操作,则表示只有 0 号哈希表中有数据,就不要在 1 号哈希表中进行查找
            // 否则的话,就还需要遍历 1 号哈希表进行查找
            if (!dictIsRehashing(d)) break;
        }
        // 返回索引
        return idx;
    }
    _dictExpandIfNeeded

    哈希表是否需要扩展

    static int _dictExpandIfNeeded(dict *d)
    {
        // 如果正在进行 rehash,则表示正在进行扩展,直接返回 OK
        if (dictIsRehashing(d)) return DICT_OK;

        // 如果 0 号哈希表为空,则需要对哈希表进行初始化,初始化哈希表数组的大小为DICT_HT_INITIAL_SIZE
        // #define DICT_HT_INITIAL_SIZE 4 
        // 可以看到,哈希表数组的初始大小为 4 
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

        // 以下两个条件之一为真时,对字典进行扩展
        // 1)字典已使用节点数和字典大小之间的比率接近 1:1 并且 dict_can_resize 为真
        // 2)已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
        // static unsigned int dict_force_resize_ratio = 5;
        if (d->ht[0].used >= d->ht[0].size && (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
        {
            // 新哈希表的大小至少是目前已使用节点数的两倍
            return dictExpand(d, d->ht[0].used*2);
        }
        return DICT_OK;
    }

    上述代码中,如果哈希表为空,即是第一次添加元素的时候,需要初始化哈希表,哈希表的大小为 4 ,如下所示:

java培训班
    还有一种情况是,如果哈希表的已有的节点和哈希表的大小的比例超过阈值 dict_force_resize_ratio 即 5 的时候,需要对哈希表进行扩展,
    扩展的哈希表大小为已使用节点的2倍,如果哈希表的大小为 4 ,已使用节点数量为24, 则 24/4 > 5 ,就需要对哈希表进行扩展,此时哈希表的大小为 24*2 = 48。
    扩展哈希表的过程
 
如下图所示:
学习java




    删除节点

    // 删除成功,返回 OK , 如果找不到对应的键,则删除失败
    int dictDelete(dict *ht, const void *key) {
        return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
    }
    // 查找并删除包含给定键的节点
    // 参数 nofree 决定是否调用键和值的释放函数, 0 表示调用,1 表示不调用
    static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
        uint64_t h, idx;
        dictEntry *he, *prevHe;
        int table;

        // 0 号哈希表和 1 号哈希表中使用节点的数量都为0,表示哈希表为空
        if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

        if (dictIsRehashing(d)) _dictRehashStep(d);

        //计算key的哈希值
        h = dictHashKey(d, key);

        //两个哈希表,表示需要在两个哈希表中查找
        for (table = 0; table <= 1; table++) {
            //计算索引值
            idx = h & d->ht[table].sizemask;
            //指向该索引上的链表
            he = d->ht[table].table[idx];
            // 当前节点的上一个节点
            prevHe = NULL;
            //遍历该链表上的所有节点
            while(he) {
                 // 找到要删除的key
                if (key==he->key || dictCompareKeys(d, key, he->key)) {
                
                    //从链表上删除该节点
                    if (prevHe) // 如果要删除的节点的前一个节点不为空,表示删除节点不是第一个节点
                        prevHe->next = he->next;
                    else // 如果要删除的节点是第一个节点,则直接把该节点的下一个节点设置为该链表的头节点
                        d->ht[table].table[idx] = he->next;
                    //释放键和值
                    if (!nofree) {
                        dictFreeKey(d, he);
                        dictFreeVal(d, he);
                     zfree(he);
                    }
                    //使用节点减1
                    d->ht[table].used--;
                    //返回删除的节点
                    return he;
                }
                // 把当前节点设置为前一个节点
                prevHe = he;
                //查找下一个节点
                he = he->next;
            }
            // 如果字典不正在进行 rehash,表示只有 0 号哈希表中有数据,不需要在 1 号哈希表中进行查找
            // 否则,如果 rehash 正在进行,则还需要在 1 号哈希表中进行查找删除
            if (!dictIsRehashing(d)) break;
        }
        return NULL; /* not found */
    }

    删除节点的过程如下:

    if (prevHe) // 如果要删除的节点的前一个节点不为空,则删除该节点
        prevHe->next = he->next;
    else // 如果要删除的节点是第一个节点,则直接把该节点的下一个节点设置为该链表的头节点
        d->ht[table].table[idx] = he->next;
    前一个节点不为空:prevHe->next = he->next

Java工程师培训




    要删除的是第一个节点:d->ht[table].table[idx] = he->next

java培训机构

    dictFetchValue

    查找对应键的值,

    //返回对应键的值
    void *dictFetchValue(dict *d, const void *key) {
        dictEntry *he;

        he = dictFind(d,key);
        return he ? dictGetVal(he) : NULL;
    }
    //查找key对应的节点
    dictEntry *dictFind(dict *d, const void *key)
    {
        dictEntry *he;
        uint64_t h, idx, table;
        //哈希表为空
        if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
        // 正在rehash
        if (dictIsRehashing(d)) _dictRehashStep(d);
 
       // 计算键的哈希值
        h = dictHashKey(d, key);

        //在 0 号哈希表和 1 号哈希表中查找
        for (table = 0; table <= 1; table++) {
            // 索引值
            idx = h & d->ht[table].sizemask;
            // 索引值对应的链表
            he = d->ht[table].table[idx];
            // 遍历链表
            while(he) {
                // 找到就返回
                if (key==he->key || dictCompareKeys(d, key, he->key))
                    return he;
                he = he->next;
            }
            // 如果正在进行rehash,1号哈希表中可能也有数据,则需要再在1号哈希表中进行查找,
            // 如果rehash完毕了,表示只有0号哈希表中有数据,就不需要在1号哈希表中查找了,直接返回null
            if (!dictIsRehashing(d)) return NULL;
        }
        return NULL;
    }
    命令操作字典

    接下来看下 hash, sets 和 sorted sets 命令是如何操作字典的。

    hash 操作字典

    添加操作:

    // hash 底层存放数据不仅仅是字典这种数据结构,还有压缩列表等结构
    int hashTypeSet(robj *o, sds field, sds value, int flags) {
        int update = 0;

        if (o->encoding == OBJ_ENCODING_ZIPLIST) {
          ........................

          // 如果该对象的编码方式是字典的方式,则需要在字典中添加该键值对 
        } else if (o->encoding == OBJ_ENCODING_HT) {
            dictEntry *de = dictFind(o->ptr,field);
            // 如果已存在,则更新
            if (de) {
                sdsfree(dictGetVal(de));
                if (flags & HASH_SET_TAKE_VALUE) {
                    dictGetVal(de) = value;
                    value = NULL;
                } else {
                    dictGetVal(de) = sdsdup(value);
                }
                update = 1;
            } else {
                sds f,v;
                if (flags & HASH_SET_TAKE_FIELD) {
                    f = field;
                    field = NULL;
                } else {
                    f = sdsdup(field);
                }
                if (flags & HASH_SET_TAKE_VALUE) {
                    v = value;
                    value = NULL;
                } else {
                    v = sdsdup(value);
               }
                // 向字典中添加元素 
                dictAdd(o->ptr,f,v);
            }
        } 
    ......................
        return update;
    }
    查找操作:

    sds hashTypeGetFromHashTable(robj *o, sds field) {
        dictEntry *de;

        // 编码格式为哈希表
        serverAssert(o->encoding == OBJ_ENCODING_HT);

        // 在哈希表中查找
        de = dictFind(o->ptr, field);
        if (de == NULL) return NULL;
        // 返回对应的值
        return dictGetVal(de);
    }
    删除操作:

    int hashTypeDelete(robj *o, sds field) {
        int deleted = 0;

        if (o->encoding == OBJ_ENCODING_ZIPLIST) {
         ......................
         // 编码方式为哈希表
        } else if (o->encoding == OBJ_ENCODING_HT) {
            // 从哈希表中删除元素
            if (dictDelete((dict*)o->ptr, field) == C_OK) {
                deleted = 1;

                if (htNeedsResize(o->ptr)) dictResize(o->ptr);
            }

        } else {
            serverPanic("Unknown hash encoding");
        }
        return deleted;
    }
    sets 操作字典

    添加操作:

    int setTypeAdd(robj *subject, sds value) {
        long long llval;
        // 如果编码方式为哈希表
        if (subject->encoding == OBJ_ENCODING_HT) {
            dict *ht = subject->ptr;
            // 在哈希表中添加元素
            dictEntry *de = dictAddRaw(ht,value,NULL);
            if (de) {
                dictSetKey(ht,de,sdsdup(value));
                    dictSetVal(ht,de,NULL);
            return 1;
            }
        } else if (subject->encoding == OBJ_ENCODING_INTSET) {
             ....................
        } else {
            serverPanic("Unknown set encoding");
        }
        return 0;
    }
    删除操作:

    int setTypeRemove(robj *setobj, sds value) {
        long long llval;
        // 编码方式为哈希表
        if (setobj->encoding == OBJ_ENCODING_HT) {
            // 在哈希表中删除元素
            if (dictDelete(setobj->ptr,value) == DICT_OK) {
                if (htNeedsResize(setobj->ptr)) dictResize(setobj->ptr);
                return 1;
            }
        } else if (setobj->encoding == OBJ_ENCODING_INTSET) {
           ..............
        } else {
            serverPanic("Unknown set encoding");
        }
        return 0;
    }
 
    以上就是 Redis 中字典的实现原理




免费预约试听课

推荐阅读