一、底層結構剖析
我們來自頂向下來分析redis內部字典的資料結構
dict
typedef struct dict {
dictType *type; //型別函式指標 這個結構體包含了一組處理特定型別的函式
void *privdata; //私有資料 傳給特定型別的函式
dictht ht[2]; //哈希表
long rehashidx; //rehash的進度 -1則為沒有進行rehash
unsigned long iterators; /* number of iterators currently running */
} dict;
dictht
哈希表，只使用 ht[0] ht[1] 用于 rehash的臨時空間
typedef struct dictht {
dictEntry **table; //哈希表陣列 這是個陣列 陣列元素為 dictEntry指標 dictEntry保存了鍵值對
unsigned long size;//table陣列的大小
unsigned long sizemask;//用于計算索引 size-1
unsigned long used; //已經分配的鍵值對數量
} dictht;
計算索引
h = dictHashKey(key) & n.sizemask;
dictEntry
存放鍵值對的結構體
typedef struct dictEntry {
void *key; //鍵
//值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; //下一個節點 因為哈希表用拉鏈法解決hash碰撞
} dictEntry;
dictType
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);//計算哈希值
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;
二、拉鏈法解決hash碰撞
可以參考 https://www.cnblogs.com/biningooginind/p/12522333.html
redis在發生碰撞后，將節點采用 頭插法 鏈接到鏈表后面，這樣就將插入節點的時間復雜度降低到 O(1)
三、關于rehash
為什么要rehash？
鍵的數量可能會不斷改變，增加鍵值對的話碰撞太多，造成查找效率的底下，如果鍵值對減少太多，那么空間可能會太大，造成陣列空間的浪費，所以應該適當的 rehash ，從新分配空間
何時進行
-
redis會根據 used的值進行rehash，一旦達到了閥值，那么就開始rehash，借助ht[1]來進行
-
在redis創建子行程進行RDB、AOF備份的時候，不會進行rehash
漸進式rehash
為了避免影響主行程處理請求，redis采用 漸進式rehash策略，即在插入或者洗掉鍵的時候進行rehash，因此需要rehashidx來表示rehash的進度，
但是這里帶來一個問題，漸進式rehash那么如果需要插入或者洗掉鍵這么安排呢？
redis在插入的時候不會在舊的ht[0]上操作，并且在洗掉鍵的時候需要在ht[0]、ht[1]中都尋找鍵，這樣就保證了ht[0]只減少不增加，直到ht[0]全部rehash到ht[1]
四、重要函式決議
dictAdd
給字典添加鍵值對
static int dictAdd(dict *ht, void *key, void *val) {
int index;
dictEntry *entry;
/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(ht, key)) == -1) //獲取鍵的hashIndex
return DICT_ERR;
/* Allocates the memory and stores key */
entry = malloc(sizeof(*entry)); //分配鍵值對空間
entry->next = ht->table[index]; //頭插法
ht->table[index] = entry;
/* Set the hash entry fields. */
dictSetHashKey(ht, entry, key);
dictSetHashVal(ht, entry, val);
ht->used++;
return DICT_OK;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21207.html
標籤：其他
上一篇：mysql相關面試題（一）