色五月婷婷丁香五月,男生和女生插视频免费看,996久久国产精品线观看软件介绍

redis 的散列表Dict 由數組 + 鏈表構成，數組的每個元素占用的槽位叫做哈希桶，當出現散列沖突的時候就會在這個桶下掛一個鏈表，用“拉鏈法”解決散列沖突的問題。

1、是什么

Redis Hash（散列表）是一種 field-value pAIrs（鍵值對）集合類型，類似于 Python/ target=_blank class=infotextkey>Python 中的字典、JAVA 中的 HashMap。一個 field 對應一個 value，你可以通過 field 在 O(1) 時間復雜度查 field 找關聯的 field，也可以通過 field 來更新或者刪除這個鍵值對。

Redis 的散列表 dict 由數組 + 鏈表構成，數組的每個元素占用的槽位叫做哈希桶，當出現散列沖突的時候就會在這個桶下掛一個鏈表，用“拉鏈法”解決散列沖突的問題。

簡單地說就是將一個 key 經過散列計算均勻的映射到散列表上。

圖 2-18

2、修煉心法

Hash 數據類型底層存儲數據結構實際上有兩種。

dict 結構。
在 7.0 版本之前使用 ziplist，之后被 listpack 代替。

通常情況下使用 dict 數據結構存儲數據，每個 field-value pairs 構成一個 dictEntry 節點來保存。

只有同時滿足以下兩個條件的時候，才會使用 listpack（7.0 版本之前使用 ziplist）數據結構來代替 dict 存儲，把 key-value 鍵值對按照 field 在前 value 在后，緊密相連的方式放到一次把每個鍵值對放到列表的表尾。

每個鍵值對中的 field 和 value 的字符串字節大小都小于hash-max-listpack-value 配置的值（默認 64）。
field-value pairs 鍵值對數量小于 hash-max-listpack-entries配置的值（默認 512）。

每次向散列表寫數據的時候，都會調用 t_hash.c 中的hashTypeConvertListpack()函數來判斷是否需要轉換底層數據結構。

當插入和修改的數據不滿足以上兩個條件時，就把散列表底層存儲結構轉換成 dict結構。需要注意的是，不能由 dict 退化成 listpack。

雖然使用了 listpack 就無法實現 O(1) 時間復雜度操作數據，但是使用 listpack 能大大減少內存占用，而且數據量比較小，性能并不是有太大差異。

為了對上層屏蔽散列表底層使用了不同數據結構存儲，所以抽象了一個 hashTypeIterator 迭代器來實現散列表的查詢。

Hashes 數據類型使用 listpack 作為存儲數據時的情況，如圖 2-19 所示。

圖 2-19

listpack 數據結構在之前的已經介紹過，接下來帶你揭秘 dict 到底長啥樣。

Redis 數據庫就是一個全局散列表。正常情況下，我只會使用 ht_table[0]散列表，圖 2-20 是一個沒有進行 rehash 狀態下的字典。

圖 2-20

dict 字典在源代碼 dict.h中使用 dict 結構體表示。

struct dict {
    dictType *type;
  // 真正存儲數據的地方，分別存放兩個指針
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

dictType *type，存放函數的結構體，定義了一些函數指針，可以通過設置自定義函數，實現 dict 的 key 和 value 存放任何類型的數據。
重點看 dictEntry **ht_table[2]，存放了兩個 dictEntry 的二級指針，指針分別指向了一個 dictEntry 指針的數組。
ht_used[2]，記錄每個散列表使用了多少槽位（比如數組長度 32，使用了 12）。
rehashidx，用于標記是否正在執行 rehash 操作，-1 表示沒有進行 rehash。如果正在執行 rehash，那么其值表示當前 rehash 操作執行的 ht_table[0] 散列表 dictEntry 數組的索引。
pauserehash 表示 rehash 的狀態，大于 0 時表示 rehash 暫停了，小于 0 表示出錯了。

繼續看 dictEntry，數組中每個元素都是 dictEntry 類型，就是這玩意存放了鍵值對，表示字典的一個節點。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

*key指針指向鍵值對中的鍵，實際上指向一個 SDS 實例。
v是一個 union 聯合體，表示鍵值對中的值，同一時刻只有一個字段有值，用聯合體的目是節省內存。

*val 如果值是非數字類型，那就使用這個指針存儲。
uint64_t u64，值是無符號整數的時候使用這個字段存儲。
int64_t s64，值是有符號整數時，使用該字段存儲。
double d，值是浮點數是，使用該字段存儲。

*next指向下一個節點指針，當散列表數據增加，可能會出現不同的 key 得到的哈希值相等，也就是說多個 key 對應在一個哈希桶里面，這就是哈希沖突。Redis 使用拉鏈法，也就是用鏈表將數據串起來。

MySQL：“為啥 ht_table[2] 存放了兩個指向散列表的指針？用一個散列表不就夠了么。”

默認使用 ht_table [0] 進行讀寫數據，當散列表的數據越來越多的時候，哈希沖突嚴重會出現哈希桶的鏈表比較長，導致查詢性能下降。

我為了唯快不破想了一個法子，當散列表保存的鍵值對太多或者太少的時候，需要通過 rehash（重新散列）對散列表進行擴容或者縮容。

擴容和縮容

為了高性能，減少哈希沖突，我會創建一個大小等于 ht_used[0] * 2的散列表 ht_table[1]，也就是每次擴容時根據散列表 ht_table [0]已使用空間擴大一倍創建一個新散列表ht_table [1]。反之，如果是縮容操作，就根據ht_table [0]已使用空間縮小一倍創建一個新的散列表。
重新計算鍵值對的哈希值，得到這個鍵值對在新散列表 ht_table [1]的桶位置，將鍵值對遷移到新的散列表上。
所有鍵值對遷移完成后，修改指針，釋放空間。具體是把 ht_table[0]指針指向擴容后的散列表，回收原來小的散列表內存空間，ht_table[1]指針指向NULL，為下次擴容或者縮容做準備。

MySQL：“什么時候會觸發擴容？”

當前沒有執行 BGSAVE或者 BGREWRITEAOF命令，同時負載因子大于等于 1。也就是當前沒有 RDB 子進程和 AOF 重寫子進程在工作，畢竟這倆操作還是比較容易對性能造成影響的，就不擴容火上澆油了。
正在執行 BGSAVE或者 BGREWRITEAOF命令，負載因子大于等于 5。（這時候哈希沖突太嚴重了，再不觸發擴容，查詢效率太慢了）。

負載因子 = 散列表存儲 dictEntry 節點數量 / 散列表桶個數。完美情況下，每個哈希桶存儲一個 dictEntry 節點，這時候負載因子 = 1。

MySQL：“需要遷移數據量很大，rehash 操作豈不是會長時間阻塞主線程？”

為了防止阻塞主線程造成性能問題，我并不是一次性把全部的 key 遷移，而是分多次，將遷移操作分散到每次請求中，避免集中式 rehash 造成長時間阻塞，這個方式叫漸進式 rehash。

在執行漸進式 rehash 期間，dict 會同時使用 ht_table[0] 和 ht_table[1]兩個散列表，rehash 具體步驟如下。

將 rehashidx設置成 0，表示 rehash 開始執行。
在 rehash 期間，服務端每次處理客戶端對 dict 散列表執行添加、查找、刪除或者更新操作時，除了執行指定操作以外，還會檢查當前 dict 是否處于 rehash 狀態，是的話就把散列表ht_table[0]上索引位置為 rehashidx 的桶的鏈表的所有鍵值對 rehash 到散列表 ht_table[1]上，這個哈希桶的數據遷移完成，就把 rehashidx 的值加 1，表示下一次要遷移的桶所在位置。
當所有的鍵值對遷移完成后，將 rehashidx設置成 -1，表示 rehash 操作已完成。