Elf32_Word オブジェクトまたは Elf64_Word オブジェクトのハッシュテーブルは、シンボルテーブルアクセスをサポートしています。ハッシュが関連付けられているシンボルテーブルは、ハッシュテーブルのセクションヘッダーの sh_link エントリに指定されます (表 7-15 を参照)。ハッシュテーブルの構造についての説明をわかりやすくするためにラベルを図 7-11 に示します。ただし、ラベルは仕様の一部ではありません。
bucket 配列には nbucket 個のエントリが存在し、chain 配列には nchain 個のエントリが存在します。インデックスは 0 から始まります。bucket と chain は、どちらもシンボルテーブルインデックスを保持します。連鎖テーブルエントリは、シンボルテーブルに対応しています。シンボルテーブルエントリ数は、nchain に等しくなければなりません。したがって、シンボルテーブルインデックスにより、連鎖テーブルエントリも選択されます。
ハッシュ関数はシンボル名を受け取り、bucket インデックスの計算に使用できる値を返します。したがって、ハッシュ関数が名前に対して値 x を返すと、bucket [x%nbucket] は、シンボルテーブルと連鎖テーブルの両方にインデックス y を与えます。シンボルテーブルエントリが、求めるシンボルテーブルエントリでなかった場合、chain[y] は、同じハッシュ値が存在する次のシンボルテーブルエントリを与えます。
選択したシンボルテーブルエントリが目的の名前を保持するか、chain エントリに値 STN_UNDEF が含まれるまで、chain リンクをたどることができます。
ハッシュ関数を次に示します。
unsigned long elf_Hash(const unsigned char *name) { unsigned long h = 0, g; while (*name) { h = (h << 4) + *name++; if (g = h & 0xf0000000) h ^= g>> 24; h &= ~g; } return h; }