1

2

3

4

5

6

typedef struct dictht {

    dictEntry **table;  // 哈希表数组

    unsigned long size; // 哈希表大小

    unsigned long sizemask; // 哈希表大小掩码，用于计算索引

    unsigned long used; // 已使用的哈希表节点数量

} dictht;

1

2

3

4

5

6

7

8

9

10

typedef struct dictEntry {

    void *key; // 键

    union {

        void *val; // 值

        uint64_t u64;

        int64_t s64;

        double d;

    } v;

    struct dictEntry *next; // 指向下一个哈希表节点，形成链表

} dictEntry;

1

2

3

4

5

6

7

8

function dictAdd(dict, key, value):

    index = hashFunction(key) & dict.sizemask

    if dict.table[index] == NULL:

        dict.table[index] = new dictEntry(key, value)

    else:

        newEntry = new dictEntry(key, value)

        newEntry.next = dict.table[index]

        dict.table[index] = newEntry

1

2

3

4

5

6

7

8

function dictFind(dict, key):

    index = hashFunction(key) & dict.sizemask

    entry = dict.table[index]

    while entry != NULL:

        if entry.key == key:

            return entry.value

        entry = entry.next

    return NULL

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

function rehashStep(dict):

    if dict.rehashidx == -1:

        return

    for i = 0 to REHASH_BATCH_SIZE:

        if dict.rehashidx >= dict.size:

            dict.rehashidx = -1

            break

        while dict.table[dict.rehashidx] == NULL:

            dict.rehashidx += 1

        entry = dict.table[dict.rehashidx]

        while entry != NULL:

            nextEntry = entry.next

            index = hashFunction(entry.key) & dict.new_ht.sizemask

            entry.next = dict.new_ht.table[index]

            dict.new_ht.table[index] = entry

            entry = nextEntry

        dict.table[dict.rehashidx] = NULL

        dict.rehashidx += 1