Redis 源码--字典P3 查找，删除和修改。

Redis的查找dictAdd通过一个底层的dictAddRaw方法来实现。

int dictAdd(dict *d, void *key, void *val)
{
    // 尝试添加键到字典，并返回包含了这个键的新哈希节点
    // T = O(N)
    dictEntry *entry = dictAddRaw(d,key);

    // 键已存在，添加失败
    if (!entry) return DICT_ERR;

    // 键不存在，设置节点的值
    // T = O(1)
    dictSetVal(d, entry, val);

    // 添加成功
    return DICT_OK;
}

前面提到，如果在rehash过程中且不存在安全迭代器，插入和更新方法都会调用单步rehash 所以dictAddRaw()调用了它。dictAddRaw()方法并不直接将key插入到table中，而是返回需要的Entry给add方法，如果已经存在这个key，那么他会返回null，如果不存在这个key，会返回入口，为了性能，对于桶内新加入的key，我们总是把它插入到头部。

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

    // 如果条件允许的话，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 计算键在哈希表中的索引值
    // 如果值为 -1 ，那么表示键已经存在
    // T = O(N)
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    // T = O(1)
    /* Allocate the memory and store the new entry */
    // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
    // 否则，将新键添加到 0 号哈希表
    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. */
    // 设置新节点的键
    // T = O(1)
    dictSetKey(d, entry, key);

    return entry;
}

回到add方法，它会对raw方法返回的entry进行判断来觉得是否进行add。
综上，add方法是不可以插入已经存在的key进行操作的。
如果需要改变已经存在的key的VAL，我们需要使用replace方法。
类似的，replace方法也有一个raw方法，使用情况和add类似。

dictEntry *dictReplaceRaw(dict *d, void *key) {
    
    // 使用 key 在字典中查找节点
    // T = O(1)
    dictEntry *entry = dictFind(d,key);

    // 如果节点找到了直接返回节点，否则添加并返回一个新节点
    // T = O(N)
    return entry ? entry : dictAddRaw(d,key);
}

最后是删除操作，由于删除操作要涉及到内存的清除工作，需要手动释放内存，所以写起来比其他两个操作要复杂一些。删除方法的通用方法是dictGenericDelete，其他方法大多调用了他。如果此时是rehash过程，那么明显的，需要查找TABLE[0]和TABLE[1]；否则只需要查找TABLE[0];

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

    // 字典（的哈希表）为空
    if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */

    // 进行单步 rehash ，T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 计算哈希值
    h = dictHashKey(d, key);

    // 遍历哈希表
    // T = O(1)
    for (table = 0; table <= 1; table++) {

        // 计算索引值 
        idx = h & d->ht[table].sizemask;
        // 指向该索引上的链表
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 遍历链表上的所有节点
        // T = O(1)
        while(he) {
        
            if (dictCompareKeys(d, key, he->key)) {
                // 查找目标节点

                /* Unlink the element from the list */
                // 从链表中删除
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;

                // 释放调用键和值的释放函数？
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                
                // 释放节点本身
                zfree(he);

                // 更新已使用节点数量
                d->ht[table].used--;

                // 返回已找到信号
                return DICT_OK;
            }

            prevHe = he;
            he = he->next;
        }

        // 如果执行到这里，说明在 0 号哈希表中找不到给定键
        // 那么根据字典是否正在进行 rehash ，决定要不要查找 1 号哈希表
        if (!dictIsRehashing(d)) break;
    }

    // 没找到
    return DICT_ERR; /* not found */
}