redisノート:辞書

私のブログは同时に発表して、レイアウトはもっと良いです
ディクショナリの実装
ハッシュ表

/*
 *    
 *
 *             ，        rehash 。
 */
typedef struct dictht {
    
    //      
    dictEntry **table;

    //      
    unsigned long size;
    
    //        ，       
    //      size - 1
    unsigned long sizemask;

    //            
    unsigned long used;

} dictht;

ハッシュテーブルノード

/*
 *      
 */
typedef struct dictEntry {
    
    //  
    void *key;

    //  
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    //          ，    
    struct dictEntry *next;

} dictEntry;

辞書

/*
 *   
 */
typedef struct dict {

    //       
    dictType *type;

    //     
    void *privdata;

    //    
    dictht ht[2];

    // rehash   
    //   rehash      ，   -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    //                
    int iterators; /* number of iterators currently running */

} dict;

ディクショナリタイプ固有関数
redisは、用途の異なる辞書に異なるタイプのフィーチャー関数を設定します.

/*
 *         
 */
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;

ハッシュアルゴリズム

#            ，  key    
hash = dict->type->hashFunction(key);

#       sizemask      ，      
index = hash & dict->ht[x].sizemask;

コンフリクトの作成
redisはチェーンアドレス法を用いて競合を解決し,新しいノードをチェーンテーブルのヘッダ位置に追加する.
rehash

拡張:ht[1]の大きさはht[0]以上である.used*2の2のn次方べき乗;

収縮:ht[1]の大きさはht[0]以上である.used*2の2^n;

ht[0]上のすべてのキー値をht[1]上の

にrehashする
拡張と収縮の条件:

BGSAVEまたはBGREWRITEAOFコマンドはなく、負荷係数が1以上である.

BGSAVEまたはBGREWRITEAOFコマンドがある場合、負荷係数は5以上である.

負荷因子=ht[0]である.used/ht[0].size

プログレッシブrehash
漸進的なrehash期間中、削除、検索、更新などの操作は2つのハッシュテーブルで実行されるが、ht[1]で追加操作が実行される.プログレッシブrehashは、転送操作を辞書の追加、削除、検索、更新操作ごとに平均し、集中操作を回避します.