数据结构

dictht

  1. typedef struct dictht {
  3.     // 哈希表数组
  4.     dictEntry **table;
  6.     // 哈希表大小
  7.     unsigned long size;
  9.     // 哈希表大小掩码，用于计算索引值
  10.     // 总是等于 size - 1
  11.     unsigned long sizemask;
  13.     // 该哈希表已有节点的数量
  14.     unsigned long used;
  16. } dictht;
  1. +--------+
  2. |dictht  |
  3. |--------|      +-------------+
  4. |table   |----->|dictEntry*[4]|
  5. |--------|      |-------------|
  6. |size    |      | 0           |--> NULL
  7. |--------|      |-------------|
  8. |sizemask|      | 1           |--> NULL
  9. |--------|      |-------------|
  10. |used    |      | 2           |--> NULL
  11. +--------+      |-------------|
  12.                 | 3           |--> NULL
  13.                 +-------------+

dictEntry

  1. typedef struct dictEntry {
  3.     // 键
  4.     void *key;
  6.     // 值
  7.     union {
  8.         void *val;
  9.         uint64_t u64;
  10.         int64_t s64;
  11.     } v;
  13.     // 指向下个哈希表节点，形成链表
  14.     struct dictEntry *next;
  16. } dictEntry;
  1. +--------+
  2. |dictht  |
  3. |--------|      +-------------+
  4. |table   |----->|dictEntry*[4]|
  5. |--------|      |-------------|
  6. |size    |      | 0           |--> NULL
  7. |--------|      |-------------|
  8. |sizemask|      | 1           |--> NULL
  9. |--------|      |-------------|           +---------+   +---------+
  10. |used    |      | 2           |---------->|dictEntry|-->|dictEntry|--> NULL
  11. +--------+      |-------------|           |---------|   |---------| 
  12.                 | 3           |--> NULL   | k1 | v1 |   | k1 | v1 |
  13.                 +-------------+           +---------+   +---------+

dict

  1. typedef struct dict {
  3.     // 类型特定函数
  4.     dictType *type;
  6.     // 私有数据
  7.     void *privdata;
  9.     // 哈希表
  10.     dictht ht[2];
  12.     // rehash 索引
  13.     // 当 rehash 不在进行时，值为 -1
  14.     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
  16. } dict;
  1. typedef struct dictType {
  3.     // 计算哈希值的函数
  4.     unsigned int (*hashFunction)(const void *key);
  6.     // 复制键的函数
  7.     void *(*keyDup)(void *privdata, const void *key);
  9.     // 复制值的函数
  10.     void *(*valDup)(void *privdata, const void *obj);
  12.     // 对比键的函数
  13.     int (*keyCompare)(void *privdata, const void *key1, const void *key2);
  15.     // 销毁键的函数
  16.     void (*keyDestructor)(void *privdata, void *key);
  18.     // 销毁值的函数
  19.     void (*valDestructor)(void *privdata, void *obj);
  21. } dictType;
  1. +---------+
  2. |dict     |
  3. |---------|           +--------+
  4. |type     |           |dictht  |     +-------------+
  5. |---------|     +---->|--------|     |dictEntry*[4]|
  6. |privdata |     |     |table   |---->|-------------|
  7. |---------|     |     |--------|     | 0           |
  8. |ht       |-----+     |size    |     |-------------|     +---------+
  9. |---------|     |     |--------|     | 1           |---->|dictEntry|----> NULL
  10. |rehashidx|     |     |sizemask|     |-------------|     |---------|
  11. +---------+     |     |--------|     | 2           |     | k1 | v1 |
  12.                 |     |used    |     |-------------|     +---------+
  13.                 |     +--------+     | 3           |
  14.                 |                    +-------------+
  15.                 |       +--------+
  16.                 +------>|dictht  |
  17.                         |--------|
  18.                         |table   |
  19.                         |--------|
  20.                         |size    |
  21.                         |--------|
  22.                         |sizemask|
  23.                         |--------|
  24.                         |used    |
  25.                         +--------+

PS：和 java.util.HashMap 相似