之前的文章其实已经讲了大部分的哈希表的实现,但是这边还是想写一点个人认为比较重要的东西。
1. 哈希表中是使用单链表的方式来解决键的冲突的
2. 当哈希表作为字典的一种实现的时候,会有一个dictType类型的指针,这里面存放着一组用于操作特定类型键值对的函数,也是比较类似linux当中驱动的写法,具体如下
点击(此处)折叠或打开
- typedef struct dict {
- dictType *type;
- void *privdata;
- dictht ht[2];
- long rehashidx; /* rehashing not in progress if rehashidx == -1 */
- unsigned long iterators; /* number of iterators currently running */
- } dict;
- typedef struct dictType {
- uint64_t (*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;
4. 为了避免rehash对服务器的性能造成影响,服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1],而是分多次、渐进式的进行的,在此期间,rehashindex会保持>=0,如果完毕或不进行rehash,该值为-1.在rehash期间,任何对字典的操作都会在两个哈希表上执行,先从0表开始,之后1表。
字典的api如下所示
函数 | 作用 |
dictCreate | 创建一个新的字典 |
dictAdd | 将给定的键值对添加到字典里面 |
dictReplace | 将给定的键值对添加到字典里面,如果键已经存在于字典,那么用新值取代原有的值 |
dictFetchValue | 返回给定的键的值 |
dictGetRandomKey | 从字典中随机返回一个键值对 |
dictDelete | 从字典中删除给定键所对应的键值对 |
dictRelease | 释放给定字典,以及字典中包含的所有键值对 |