哈希表的实现

• 哈希表可以认为是redis最为重要的一个数据结构
• 实现了key,value的查找，保存所有的key等

1.基本数据结构

typedef struct dictEntry {
    void *key;// 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值(可以有几种不同类型)
    struct dictEntry *next;// 指向下一个哈希节点(形成链表)
} dictEntry;

• 这个数据结构可以认为是hash表的一个元素，包含键值对。用于链接法散列。是链接法散列中的链表部分。具体的第一个key,value 可以是联合体里面的几种类型
  最后一个是指向具有相同hash值的元素。

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);//key的析构函数
        void (*valDestructor)(void *privdata, void *obj);//val的析构函数
} dictType;

• 这个数据结构定义了一些在hash表上的一系列操作，结构体里面都是函数指针，每个hash表里面都会有这个数据结构，对每个hash表进行操作。

typedef struct dictht {
        dictEntry **table;//字典实体，使用的是数组形式，方便查找key
        unsigned long size;//字典大小
        unsigned long sizemask;//字典掩码，为size-1
        unsigned long used;//这个字典表中（数组中），被使用的个数
} dictht;

• 定义了hash表的形式，使用一个保存hash表元素地址的一个数组，还有存储hash表的大小，大小掩码，使用个数。可以认为是一个数组的扩展。方便管理的数组。

typedef struct dict {
        dictType *type;//定义了对于hash表操作的一些列函数
        void *privdata;//私有的数据
        dictht ht[2];//两个hash表，一个新的一个旧的，可以在必要的时候进行hash表的扩张，和hash表的rehash。
        long rehashidx; /* rehashing not in progress if rehashidx == -1 *///rehash的标志-1表示没在rehash，可以根据这个值来取得两张hash表哪个可以使用。
        int iterators; /* number of iterators currently running *///这个hash表上迭代器的个数
} dict;

• 对于两个hash表的管理数据结构，所有的操作都是通过这个数据结构来进行的。包含hash元素的添加，删除，查找，扩张，rehash。

typedef struct dictIterator {
        dict *d;//管理hash表的数据机构
        long index;//索引
        int table, safe;//表和安全性标志
        dictEntry *entry, *nextEntry;//当前元素和下一个元素
        /* unsafe iterator fingerprint for misuse detection. */
        long long fingerprint;//指纹
} dictIterator;

• hash表上面的迭代器，可以通过迭代器来访问hash表中的元素。当safe=1时候是安全的，可以对于hash表进行删除插入操作。否则只能读取hash表

static void _dictReset(dictht *ht)

• 对于hash表进行空的初始化，把hash表中的组数，大小都设置为默认值。

dict *dictCreate(dictType *type, void *privDataPtr)

• 创建一个管理hash表的数据结构，首先分配内存，设置管理hash表数据结构的hash类型，私有数据，迭代器，最为主要的是初始化两张hash表。
  这样两张hash表就创建成功了，但是现在里面并没有任何元素，也可以说这两张表（两个数组）内容是hash元素指针，两个数组里面并没有开始分配内存，只有数组名。
• 正真进行分配内存的时候（给dictht的table分配内存）是在dict的扩张时候。见下面的函数int dictExpand(dict *d, unsigned long size)

int _dictInit(dict *d, dictType *type,void *privDataPtr)

-根据参数对于管理两个hash表的数据结构进行初始化，设置

int dictExpand(dict *d, unsigned long size)

• 创建或者扩张hash表，其中size为hash表的大小，也就是dictht中table的大小，动态分配内存。
• 创建hash表：table存储的是hash元素值的指针，在这个时候会给table分配内存，分配内存的大小是大于size的2的指数倍。给的size大小需要检查，不能超过long_max值。同时这个值还不能和当前hash表的大小一致，这样没什么意义。
• 分配好table的大小之后，就可以把它赋值给管理hash表的数据结构了。管理数据结构dict通过ht[2]来对这两个hash表进行管理。
• 这样就给两个hash表分配的内存，其实这两个hash表的指针是指向同一快内存的。这只是在创建的时候两张hash表是同一块内存。ht[0]=ht[1] if (ht[0].table=null)
• Expend过程：上面的创建过程给两张表指针指向同一块内存，其实如果两个hash表已经初始化了之后，就可以达到扩展的过程。ht[0].table=ht[1].table if (ht[0].table=null)
• 这语句的意思就是在扩张的时候一个hash表已经分配内存了，就会给另一张表分配内存。并不会覆盖原来有值的hash表。

int dictRehash(dict *d, int n)

• 重新hash，就是把hashtable[0]（ht[0]）里面的所有的键重新hash一下，然后把键值存储在hashtable1里面，并且hashtable[0]还指向重新hash后的hash表。

• 整个表都rehash完成后返回0，部分rehash返回1。

• 具体的过程是这样的：

• 首先在hashtable[0]里面找到所有非空的键值对（数组中查找到链表头节点（头指针）），然后对这个查找到的链表进行遍历，链表中的每一个元素都是键值对。根据链表节点中的键key，找到在hashtable[1]数组中的索引位置，然后插入到这个索引所在的链表的表头。

• 这样就可以完成一个字典实体的转换，一只把整个链表遍历完毕。然后在把hashtable[0]数组中的所有非空元素都遍历完毕。
  最后实现了，hashtable[0]里面的所有元素，转换为hashtable[1]中的所有元素。- 实现rehash的过程。注意每次最多遍历n*10个元素。

• 结束了上面的两重遍历之后，就可以检查是否完成整个rehash的过程是否完成。会进行一些列的释放资源的操作，比如释放hashtable[0]的内存，使得hashtable[1]和hashtable[0]指针互换。重置hashtable[1]

• 从这里也可以看出来，主要的hash表还是hashtable[0],hashtable[1]只是起到了中间作用。还有一点就是可能会存在部分rehash的过程。可以把部分rehash的内容，存放在另一个临时的hash表中。

• 回过头来看看，rehash的过程是把一个hash表中所有元素拿出来之后，按着某种方式对key进行重新hash然后存放在其他的表中。

long long timeInMilliseconds(void)

• 获取当前时间的毫秒数，使用到了gettimeofday函数

int dictRehashMilliseconds(dict *d, int ms)

• 在ms毫秒之间进行hash,也就是说控制rehash的时间超过ms毫秒。只要rehash时间没有超过ms毫秒，那么增加rehash的参数n大小，每次增加100，知道所有rehash时间超过ms毫秒.
• 这是一种怎样的控制啊，强制要求rehash超过一定的时间，我觉着可能是为了控制rehash的大小。移动元素的个数。考虑到rehash执行的时间对于其他请求的影响。

static void _dictRehashStep(dict *d)

• 当没有迭代器的时候会每次rehash10个元素(调用dictRehash(dict, 1) )，逐渐的把hashtable[0]里面的元素迁移到hashtable[1]中。什么时候能够知道完全rehash完毕呢？ 根据dictRehash函数的返回值。

static int _dictKeyIndex(dict *d, const void *key)

• 查找key所在hashtable（[0],[1]）中的index，key存在返回所在数组的index，否则返回-1。
• 先根据key和整个hash表的hash计算方法，计算出key的hash码，也就是在hashtable中的索引，其实是这个key应该在哪个位置上。肯定会有一个index，其次如果这个index指向的链表中
• 如果链表为空，那么返回hash码，否则需要遍历这个链表查看是否存在与key对应的元素。最后如果正在rehash,或者rehash 并没有完成(部分rehash)，那么就需要，把两个表都遍历，否则只查找一个表（hashtable[0]）

dictEntry *dictAddRaw(dict *d, void *key)

• 添加只有key的字典元素到hashtable中，并返回可以设置value的字典元素指针。后来需要调用setvalue函数来进行value的设置。
  这个函数会首先调用_dictKeyIndex查找到应该在的index，当然也可能会key已经存在了。然后根据是否部分rehash,来决定index是在哪一个表中。hashtable[0] or hashtable[1]
• 然后创建字典元素实体，并设置key值，放在hashtable中。

int dictAdd(dict *d, void *key, void *val)

• 添加对key,value对到hashtable中，向字典中添加元素。
• 会调用dictAddRaw添加元素的key
• 然后调用dictSetVal设置key在hashtable中的实体的value值。

dictEntry *dictFind(dict *d, const void *key)

• 查找key所在的字典实体，返回字典实体的指针
• 这个查找的过程和_dictKeyIndex类似，只是这里面要查找到具体的字典实体所在的内存地址
• 首先遍历两个hashtable(数组)，找到头节点，接着遍历链表，找到和key相同的字典实体，并返回地址。找不到就会返回NULL

int dictReplace(dict *d, void *key, void *val)

• 调用dictFind找到字典实体，调用dictSetVal设置字典的新值，然后释放原来字典元素的内容。

dictEntry *dictReplaceRaw(dict *d, void *key)

• 查找key,如果存在则添加key，不存在怎返回NULL

static int dictGenericDelete(dict *d, const void *key, int nofree)

• 查找并删除一个key元素，
• 根据两张hashtable来进行查找，找到一个头节点之后，进行遍历，知道找到key的值所在的字典，如果没有找到返回error，找到了之后进行删除并释放内存，返回ok

int dictDeleteNoFree(dict *ht, const void *key)

• 调用dictGenericDelete（ht,key,1）删除值，但是并不释放内存。

int dictDelete(dict *ht, const void *key)

• 调用dictGenericDelete（ht,key,0）删除值，并释放内存。

int _dictClear(dict *d, dictht *ht, void(callback)(void *))

• 清除指定的ht整个字典内容并，释放内存。

void dictRelease(dict *d)

• 调用_dictClear(d,&d->ht[0],NULL)调用_dictClear(d,&d->ht[1],NULL),分别释放两个hashtable

void *dictFetchValue(dict *d, const void *key)

• 首先调用dictFind,然后获得这个键对于的字典实体，进而获得字典值。

dictIterator *dictGetIterator(dict *d)

• 创建dictIterator实体，并把内容迭代的指针指向dict d。获得的是不安全的迭代器，只能通过这个迭代器读取字典，不能写操作。

dictIterator *dictGetSafeIterator(dict *d)

• 获得安全的迭代器版本，可以对整个字典进行读写操作。

dictEntry *dictNext(dictIterator *iter)

• 获得下一个字典元素指针。
• 具体的操作：
• 1.next不为空的时候直接返回next的内容，这个时候迭代器里面保存了当前hashtable的索引值，所以可以，等到把这个链表遍历完了，就可增加索引index的值，按着往数组后面开始遍历另一个链表
• 2.next为空的时候，这个时候需要判断,是否为安全的迭代器，如果是增加指纹信息（我猜测可能是为了后面进行通过迭代器进行修改字典进行的验证），并且需要增加迭代器的引用个数。
• 判断一个表是否遍历完了。如果这个表遍历完了（通过index和桶的大小），并且正在进行rehash那么就需要切换到另一个hashtable中进行依次从数组的开始0进行遍历。

void dictReleaseIterator(dictIterator *iter)

• 释放迭代器
• 如果为安全版本的迭代器，需要减少字典迭代器上面的引用，否则需要验证是否为当前字典的指纹信息。

dictEntry *dictGetRandomKey(dict *d)

• 随机获得字典中的一个键值对。
• 随机找到一个索引，并且随机获得这个索引指向的链表中的一个元素。