<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                Redis 的字典使用哈希表作為底層實現, 一個哈希表里面可以有多個哈希表節點, 而每個哈希表節點就保存了字典中的一個鍵值對。 接下來的三個小節將分別介紹 Redis 的哈希表、哈希表節點、以及字典的實現。 ## 哈希表 Redis 字典所使用的哈希表由?`dict.h/dictht`?結構定義: ~~~ typedef struct dictht { // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼,用于計算索引值 // 總是等于 size - 1 unsigned long sizemask; // 該哈希表已有節點的數量 unsigned long used; } dictht; ~~~ `table`?屬性是一個數組, 數組中的每個元素都是一個指向?`dict.h/dictEntry`?結構的指針, 每個?`dictEntry`?結構保存著一個鍵值對。 `size`?屬性記錄了哈希表的大小, 也即是?`table`?數組的大小, 而?`used`?屬性則記錄了哈希表目前已有節點(鍵值對)的數量。 `sizemask`?屬性的值總是等于?`size?-?1`?, 這個屬性和哈希值一起決定一個鍵應該被放到?`table`?數組的哪個索引上面。 圖 4-1 展示了一個大小為?`4`?的空哈希表 (沒有包含任何鍵值對)。 ![](https://box.kancloud.cn/2015-09-13_55f511fc9428c.png) ## 哈希表節點 哈希表節點使用?`dictEntry`?結構表示, 每個?`dictEntry`?結構都保存著一個鍵值對: ~~~ typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下個哈希表節點,形成鏈表 struct dictEntry *next; } dictEntry; ~~~ `key`?屬性保存著鍵值對中的鍵, 而?`v`?屬性則保存著鍵值對中的值, 其中鍵值對的值可以是一個指針, 或者是一個?`uint64_t`?整數, 又或者是一個?`int64_t`?整數。 `next`?屬性是指向另一個哈希表節點的指針, 這個指針可以將多個哈希值相同的鍵值對連接在一次, 以此來解決鍵沖突(collision)的問題。 舉個例子, 圖 4-2 就展示了如何通過?`next`?指針, 將兩個索引值相同的鍵?`k1`?和?`k0`?連接在一起。 ![](https://box.kancloud.cn/2015-09-13_55f51205335f9.png) ## 字典 Redis 中的字典由?`dict.h/dict`?結構表示: ~~~ typedef struct dict { // 類型特定函數 dictType *type; // 私有數據 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 當 rehash 不在進行時,值為 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; ~~~ `type`?屬性和?`privdata`?屬性是針對不同類型的鍵值對, 為創建多態字典而設置的: * `type`?屬性是一個指向?`dictType`?結構的指針, 每個?`dictType`?結構保存了一簇用于操作特定類型鍵值對的函數, Redis 會為用途不同的字典設置不同的類型特定函數。 * 而?`privdata`?屬性則保存了需要傳給那些類型特定函數的可選參數。 ~~~ typedef struct dictType { // 計算哈希值的函數 unsigned int (*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; ~~~ `ht`?屬性是一個包含兩個項的數組, 數組中的每個項都是一個?`dictht`?哈希表, 一般情況下, 字典只使用?`ht[0]`?哈希表,?`ht[1]`?哈希表只會在對?`ht[0]`?哈希表進行 rehash 時使用。 除了?`ht[1]`?之外, 另一個和 rehash 有關的屬性就是?`rehashidx`?: 它記錄了 rehash 目前的進度, 如果目前沒有在進行 rehash , 那么它的值為?`-1`?。 圖 4-3 展示了一個普通狀態下(沒有進行 rehash)的字典: ![](https://box.kancloud.cn/2015-09-13_55f5120772706.png)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看