ハッシュのELFHashと静的hash(シミュレーションリンク法)

私たちがよく知っているc++のmapも実はhashの思想です.
自分で1つのhashシステムを設計して、まず1つのマッピング配列を創立して、hash表、それから衝突処理...、個人はチェーン表法の効率が高いと思っています(もちろん1つの単一チェーン表で実現することができて、あるいは1つの配列でhashの下の標の位置を記録しても単一チェーン表をシミュレートすることができます)文字列hashはELFhashアルゴリズムを使うことを考えて、主にELFHashアルゴリズムを分析します.
ELFhash関数はUNIXシステムVバージョン4の「実行可能リンクフォーマット」(Executable and Linking Format、すなわちELF)で使用され、ELFファイルフォーマットは実行可能ファイルとターゲットファイルを格納するために使用される.ELFhash関数は、文字列に対するハッシュです.それは長い文字列と短い文字列に対してすべてとても有効で、文字列の中ですべての文字はすべて同じ作用があって、それは巧みに文字のASCII符号化値に対して計算を行って、ELFhash関数は比較的に均一に文字列をハッシュリストの中で分布することができます.
これらの関数はビット演算を使用して、各文字が最後の関数値に影響を与えます.
//ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;
while (*str)
{
hash = (hash << 4) + (*str++);//hashは4ビット左にシフトし、現在の文字ASCIIをhash下位4ビットに格納します.
if ((x = hash & 0xF0000000L) != 0)
{
//最大4桁が0でない場合は、文字が7文字余っていることを示し、現在8文字目を保存しています.処理しない場合、次の文字を追加すると、最初の文字が削除されますので、次の処理が必要です.
//この処理は、文字列(a-zまたはA-Z)に対して5-8ビットにのみ影響し、そうでなければ5-31ビットに影響します.C言語で使用される算数シフトのためです.
//1～4ビットに新規文字が格納されたばかりなので、できません>>28
hash ^= (x >> 24);
//上の行のコードはXに影響しません.自分のXとhashの高さ4桁は同じです.下の行のコード&~は28-31(高さ4桁)桁に対してゼロになります.
hash &= ~x;
}
}
//符号ビットが0の数を返します.すなわち、関数外に影響を及ぼさないように、最上位を捨てます.(文字のみでは符号ビットが負になることは考えられない)
return (hash & 0x7FFFFFFF);
}
静的hash実現に対する考え方は、

typedef struct Entity
{
    char e[11];
    char f[11];
    int next;
}Entity;
Entity entity[M];
int i = 1; //      
int hashIndex[M];

//      hash
hash = ELFHash(entity[i].f);
        entity[i].next = hashIndex[hash];//        ，  hashIndex[]     ，    0，     0
        hashIndex[hash] = i;//        hash ，    hashIndex[]  0；         hash       entity[]    
        i++;

//       ：
void find(char f[])
{
    int k;
    int hash = ELFHash(f);
    for(k=hashIndex[hash]; k!=0; k=entity[k].next)
    {
        if(strcmp(f,entity[k].f) == 0)
        {
            printf("%s
",entity[k].e);
            return;
        }
    }
    printf("eh
");
}