あまりメモリを使用しないハッシュテーブルを設計するにはどうすればよいですか？

Question

C言語を学ぶために、おそらくForthのような意味での単純なオブジェクトシステムを設計しています。私が設計したデータ構造の1つはハッシュテーブル、つまりhash_tです。私はPython 3.6's dictionariesのこの説明の私の理解の下でそれを実装しました

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; 

：

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バイト、または私のラップトップよりも多くのRAMである必要があります。また、より多くのRAMをより1つハッシュテーブルが必要になります。

私がPythonで作成する各辞書は、何百万バイトものRAMも必要としませんが、C言語でこのように実装されているようです。何が欠けていますか？

Answer 1

ハッシュに含めるアイテムの数に基づいてハッシュ数を決定し、ハッシュ範囲をその範囲に減らします。

バケツごとに約10個のアイテムを含む約100,000個のアイテムを保持するには、約10,000個のバケットが必要です。したがって、ハッシュを計算した後、10,000を法とするハッシュを取って、アイテムを入れるバケットを決定してください。

一般的に、バケットカウントの素数を使うと最も効果的です。