目錄
字典数据结构
字典的API函数
创建新字典
字典添加元素
字典Rehash解析
Rehash操作核心函数:
小结
首頁 資料庫 mysql教程 Redis内部数据结构详解之字典(dict)

Redis内部数据结构详解之字典(dict)

Jun 07, 2016 pm 03:22 PM
dict redis 內部 字典 資料結構 詳解

字典,简单说就是存储key-value键值数据,当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map,STL中的map是用red-black tree实现的,因为map不仅能够保证key不重复,而且key还是按照字典序存储的,而Redis中的字典并不要求有序,因此为了降低编

字典,简单说就是存储key-value键值数据,当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map,STL中的map是用red-black tree实现的,因为map不仅能够保证key不重复,而且key还是按照字典序存储的,而Redis中的字典并不要求有序,因此为了降低编码的难度使用哈希表作为字典的底层实现。Redis的字典是使用一个桶bucket,通过对key进行hash得到的索引值index,然后将key-value的数据存在桶的index位置,Redis处理hash碰撞的方式是链表,两个不同的key hash得到相同的索引值,那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候,字典不免会退化成多个链表,效率大大降低,Redis采用rehash的方式对桶进行扩容来解决这种退化。

Redis使用的hash算法有以下两种:

1. MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好,具体信息请参考 MurmurHash 的主页:http://code.google.com/p/smhasher/ 。
2. 基于djb算法实现的一个大小写无关散列算法:具体信息请参考
http://www.cse.yorku.ca/~oz/hash.html 。

字典数据结构

typedef struct dictEntry {//字典的节点
    void *key;
    union {//使用的联合体
        void *val;
        uint64_t u64;//这两个参数很有用
        int64_t s64;
    } v;
    struct dictEntry *next;//下一个节点指针
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key); //hash函数指针
    void *(*keyDup)(void *privdata, const void *key); //键复制函数指针
    void *(*valDup)(void *privdata, const void *obj); //值复制函数指针
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); //键比较函数指针
    void (*keyDestructor)(void *privdata, void *key); //键构造函数指针
    void (*valDestructor)(void *privdata, void *obj); //值构造函数指针
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht { //字典hash table
    dictEntry **table;//可以看做字典数组,俗称桶bucket
    unsigned long size; //指针数组的大小,即桶的层数
    unsigned long sizemask;
    unsigned long used; //字典中当前的节点数目
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata; //私有数据
    dictht ht[2];   //两个hash table
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引
    int iterators; /* number of iterators currently running */ //当前该字典迭代器个数
} dict;
登入後複製
dict数据结构中声明了两个字典hashtable结构dictht,ht[1]在rehash时候使用,后面具体分析。

下图给出整个字典结构,图片来自Redis设计与实现一书:

\

上图ht[1]为空,说明当然字典没在Rehash状态。

字典的API函数

函数名称

作用

复杂度

dictCreate

创建一个新字典

O(1)

dictResize

重新规划字典的大小

O(1)

dictExpand

扩展字典

O(1)

dictRehash

对字典进行N步渐进式Rehash

O(N)

_dictRehashStep

对字典进行1步尝试Rehash

O(N)

dictAdd

添加一个元素

O(1)

dictReplace

替换给定key的value值

O(1)

dictDelete

删除一个元素

O(N)

dictRelease

释放字典

O(1)

dictFind

查找一个元素

O(N)

dictFetchValue

通过key查找value

O(N)

dictGetRandomKey

随机返回字典中一个元素

O(1)

创建新字典

通过dictCreate函数创建一个新字典dict *dictCreate(dictType *type, void *privDataPtr),一个空字典的示意图如下(图片来自Redis设计与实现一书): \上面已经提起过,ht[1]只在Rehash时使用。

字典添加元素

根据字典当前的状态,将一个key-value元素添加到字典中可能会引起一系列复制的操作:

如果字典未初始化(即字典的0号哈希表ht[0]的table为空),那么需要调用dictExpand函数对它初始化;

如果插入的元素key已经存在,那么添加元素失败;

如果插入元素时,引起碰撞,需要使用链表来处理碰撞;

如果插入元素时,引起程序满足Rehash的条件时,先调用dictExpand函数扩展哈希表的size,然后准备渐进式Rehash操作。

字典添加元素的流程图,来自Redis设计与实现一书

\

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size); //得到需要扩展到的size

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    //准备渐进式rehash,rehash的字典table为0号
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空,那么将它扩展为初始大小
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /*如果哈希表的已用节点数 >= 哈希表的大小,并且以下条件任一个为真:
       1) dict_can_resize 为真
       2) 已用节点数除以哈希表大小之比大于 dict_force_resize_ratio
       那么调用 dictExpand 对哈希表进行扩展,扩展的体积至少为已使用节点数的两倍
    */
    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;
}

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    /* Compute the key hash value */
    h = dictHashKey(d, key);//通过hash函数得到key所在的bucket索引位置
    //查找在现有字典中是否出现了该key
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        //如果系统没在rehash则不需要查找ht[1]
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);// 尝试渐进式地 rehash 桶中一组元素

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 查找可容纳新元素的索引位置,如果元素已存在, index 为 -1
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 决定该把新元素放在那个哈希表
    entry = zmalloc(sizeof(*entry));
    //头插法,插入节点
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);//关联起key
    return entry;
}

/* Add an element to the target hash table */
//添加一个元素
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);//关联起value
    return DICT_OK;
}
登入後複製

字典Rehash解析

Rehash的触发机制:当每次添加新元素时,都会对工作哈希表ht[0]进行检查,如果used(哈希表中元素的数目)与size(桶的大小)比率ratio满足以下任一条件,将激活字典的Rehash机制:ratio=used / size, ratio >= 1并且dict_can_resize 为真;ratio 大 于 变 量 dict_force_resize_ratio 。
Rehash执行过程:创建一个比ht[0].used至少两倍的ht[1].table;将原ht[0].table中所有元素迁移到ht[1].table;清空原来ht[0],将ht[1]替换成ht[0] 渐进式Rehash主要由两个函数来进行: _dictRehashStep:当对字典进行添加、查找、删除、随机获取元素都会执行一次,其每次在开始Rehash后,将ht[0].table的第一个不为空的索引上的所有节点全部迁移到ht[1].table; dictRehashMilliseconds:由Redis服务器常规任务程序(serverCron)执行,以毫秒为单位,在一定时间内,以每次执行100步rehash操作。

Rehash操作核心函数:

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {//已经完成
            zfree(d->ht[0].table);//释放ht[0].table
            d->ht[0] = d->ht[1]; //这里ht[0]与ht[1]都不是指针,直接赋值就替换了
            _dictReset(&d->ht[1]);//将ht[1].table设置为null
            d->rehashidx = -1;
            return 0;
        }

        /* Note that rehashidx can&#39;t overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned)d->rehashidx);
        //找到第一个不为空的数组
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        //指向该链表头
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {//遍历链表
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            //得到在ht[1]中的索引号,通过相应的hash函数
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 添加节点到 ht[1] ,调整指针,采用的是头插法
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;//设置为空
        d->rehashidx++;
    }
    return 1;
}
登入後複製

小结

Redis中的字典数据结构使用哈希表来实现,用来存储key-value键值元素;
字典使用两个哈希表,一般只使用ht[0],只有当Rehash时候才使用ht[0];
哈希表采用链表的方式解决键碰撞问题;
Redis的Rehash操作是渐进式的,服务器程序会主动Rehash,在查找、添加、删除元素等操作时也会在Rehash进行时执行一次rehash操作。

字典的内容实在太多,操作比较繁琐,应该是Redis中最复杂的底层数据结构了,本文分析的绝对不够深入,希望以后有时间再修改吧,暂时先这样。到目前为止,Redis六种内部数据结构,同时也是底层操作的实现讲解全部结束,后面的文章将进入五种基本数据类型指令的实现,字符串(String)、哈希表(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set)的各种指令的实现。

我自己对Redis2.8.2源码的注释,有时间找个机会放出来。


最后感谢黄健宏(huangz1990)的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

redis集群模式怎麼搭建 redis集群模式怎麼搭建 Apr 10, 2025 pm 10:15 PM

Redis集群模式通過分片將Redis實例部署到多個服務器,提高可擴展性和可用性。搭建步驟如下:創建奇數個Redis實例,端口不同;創建3個sentinel實例,監控Redis實例並進行故障轉移;配置sentinel配置文件,添加監控Redis實例信息和故障轉移設置;配置Redis實例配置文件,啟用集群模式並指定集群信息文件路徑;創建nodes.conf文件,包含各Redis實例的信息;啟動集群,執行create命令創建集群並指定副本數量;登錄集群執行CLUSTER INFO命令驗證集群狀態;使

redis怎麼讀取隊列 redis怎麼讀取隊列 Apr 10, 2025 pm 10:12 PM

要從 Redis 讀取隊列,需要獲取隊列名稱、使用 LPOP 命令讀取元素,並處理空隊列。具體步驟如下:獲取隊列名稱:以 "queue:" 前綴命名,如 "queue:my-queue"。使用 LPOP 命令:從隊列頭部彈出元素並返回其值,如 LPOP queue:my-queue。處理空隊列:如果隊列為空,LPOP 返回 nil,可先檢查隊列是否存在再讀取元素。

redis數據怎麼清空 redis數據怎麼清空 Apr 10, 2025 pm 10:06 PM

如何清空 Redis 數據:使用 FLUSHALL 命令清除所有鍵值。使用 FLUSHDB 命令清除當前選定數據庫的鍵值。使用 SELECT 切換數據庫,再使用 FLUSHDB 清除多個數據庫。使用 DEL 命令刪除特定鍵。使用 redis-cli 工具清空數據。

centos redis如何配置Lua腳本執行時間 centos redis如何配置Lua腳本執行時間 Apr 14, 2025 pm 02:12 PM

在CentOS系統上,您可以通過修改Redis配置文件或使用Redis命令來限制Lua腳本的執行時間,從而防止惡意腳本佔用過多資源。方法一:修改Redis配置文件定位Redis配置文件:Redis配置文件通常位於/etc/redis/redis.conf。編輯配置文件:使用文本編輯器(例如vi或nano)打開配置文件:sudovi/etc/redis/redis.conf設置Lua腳本執行時間限制:在配置文件中添加或修改以下行,設置Lua腳本的最大執行時間(單位:毫秒)

redis命令行怎麼用 redis命令行怎麼用 Apr 10, 2025 pm 10:18 PM

使用 Redis 命令行工具 (redis-cli) 可通過以下步驟管理和操作 Redis:連接到服務器,指定地址和端口。使用命令名稱和參數向服務器發送命令。使用 HELP 命令查看特定命令的幫助信息。使用 QUIT 命令退出命令行工具。

redis過期策略怎麼設置 redis過期策略怎麼設置 Apr 10, 2025 pm 10:03 PM

Redis數據過期策略有兩種:定期刪除:定期掃描刪除過期鍵,可通過 expired-time-cap-remove-count、expired-time-cap-remove-delay 參數設置。惰性刪除:僅在讀取或寫入鍵時檢查刪除過期鍵,可通過 lazyfree-lazy-eviction、lazyfree-lazy-expire、lazyfree-lazy-user-del 參數設置。

如何優化debian readdir的性能 如何優化debian readdir的性能 Apr 13, 2025 am 08:48 AM

在Debian系統中,readdir系統調用用於讀取目錄內容。如果其性能表現不佳,可嘗試以下優化策略:精簡目錄文件數量:盡可能將大型目錄拆分成多個小型目錄,降低每次readdir調用處理的項目數量。啟用目錄內容緩存:構建緩存機制,定期或在目錄內容變更時更新緩存,減少對readdir的頻繁調用。內存緩存(如Memcached或Redis)或本地緩存(如文件或數據庫)均可考慮。採用高效數據結構:如果自行實現目錄遍歷,選擇更高效的數據結構(例如哈希表而非線性搜索)存儲和訪問目錄信

redis計數器怎麼實現 redis計數器怎麼實現 Apr 10, 2025 pm 10:21 PM

Redis計數器是一種使用Redis鍵值對存儲來實現計數操作的機制,包含以下步驟:創建計數器鍵、增加計數、減少計數、重置計數和獲取計數。 Redis計數器的優勢包括速度快、高並發、持久性和簡單易用。它可用於用戶訪問計數、實時指標跟踪、遊戲分數和排名以及訂單處理計數等場景。

See all articles