なぜLinuxカーネルで単一のハッシュバケットハッシュテーブルを使用するのですか

Question

私はLinuxカーネルのハッシュテーブルの実装を理解しようとしています。私が理解できないことは、ハッシュテーブルを1つのハッシュバケットだけで初期化するコードが見つかることです。なぜコーディングがそれをしているのか分かりません。

void __init pidhash_init(void) 
{ 
    unsigned int i, pidhash_size; 

    pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18, 
         HASH_EARLY | HASH_SMALL, 
         &pidhash_shift, NULL, 
         0, 4096); 
    pidhash_size = 1U << pidhash_shift; 

    for (i = 0; i < pidhash_size; i++) 
     INIT_HLIST_HEAD(&pid_hash[i]); 
} 

pid_hashがstruct hlist_headのリストなので、リストの各エントリは、ハッシュバケットを表します

kernel/pid.cで：

このハッシュテーブルの使用は、私には意味があります。

しかし、この使用法は私には意味がありません：金魚ブランチのdrivers/android/binder.cで

：

static HLIST_HEAD(binder_dead_nodes); 

それは基本的に、それはハッシュテーブルである

struct hlist_head name = { .first = NULL } 

に展開ただ1つのhlist_head、すなわち1つのハッシュバケットしか持たないハッシュテーブルである。実際には二重リンクリストです。なぜ人々はこのような単一のハッシュバケットを持つハッシュテーブルを作成したいのですか？

Answer 1

hlistは単なる通常のダブルリンクリストです。

listとhlistの違いは、空リストの50％のメモリ削減のためにリストの末尾にO（1）アクセスすることです。これは、多くの空のリストを持ち、逆順または後ろからリストにアクセスする必要がないハッシュテーブルに最適です。

ただし、通常のリンクリストにも適しています。

hlistを使用すると、listに数バイトの保存が行われ、不明な数のアイテムを収集するために使用されることがわかります。