如何设计一个不需要太多内存的哈希表？

Question

为了学习C，我正在设计一个简单的对象系统，可能是为了一个类似于第四语言的语言。我设计的数据结构之一是哈希表，即hash_t。

typedef struct {
  array_t* keys;     // intelligent array object
  assoc_t* vals;     // array<pair>

  ssize_t* idxs;     // raw C array
  size_t   idxs_len; // and its length

} hash_t;

我根据对Python 3.6's dictionaries的描述实现了它

a hashtable consists of:
    non-sparse array_t of keys
    non-sparse associative array of pairs of values and their key's hashes
    sparse raw array of which values map to which actual entries.

  { 1: 'a', 2: 'b', 3: 'c' }

  is represented in this structure as:

  hash->keys = array{ 1, 2, 3 }
  hash->vals = assoc{
    pair{ 'a' 5 }
    pair{ 'b' 7 }
    pair{ 'c' 9 }
  }
  hash->idxs = array{ -1 -1 -1 -1 -1  0 -1  1 -1  2  -1 }
                                      ^     ^     ^ 
                                      5     7     9

  where 5, 7, and 9 are the hashes of 1, 2, and 3.

-1代替Python中的None来表示不存在的值。

当我的密钥1 (字符串化)散列到0x340ca71c或873,244,444时，问题就出现了。因此，键指示符(hash->idxs)数组需要是sizeof (ssize_t) * (873,244,444 + 1)，或8 * 873,244,444 = 6,985,955,552字节，或~7GB，这比我的笔记本电脑拥有的内存还要多，而且比我想要的一个哈希表占用的内存还要多。

当然，我用Python创建的每个字典都不会占用数百万甚至几十万字节的RAM，但它似乎是以这种方式实现的。在C中，我遗漏了什么？

Answer 1

根据哈希将拥有的项目数来决定您希望哈希拥有多少个桶，然后将哈希范围缩小到该范围。

因此，如果您想要一个哈希值来容纳大约100,000项，每桶约有10项，那么您需要大约10,000个桶。因此，在计算散列之后，使用散列模块10,000来决定将项放入哪个桶中。

一般说来，使用质数来计算桶数的效果最好，所以可能有9,973次。