[訳]C言語は簡単なHash tableを実現する(4)

前章では、Hash tableの中で最も重要なhash を説明し、偽コードとC言語で私たち自身のhash を実現しました.hash の中で は避けられません. が発生した場合、私たちはどのように有効な処理を変更しますか.この章では説明します.
衝突の処理hash 無限大の入力を有限の出力にマッピングし、異なる入力が同じ出力にマッピングされると が発生し、各hash は異なる方法で を処理する.
我々のハッシュテーブルは、競合を処理するために、オープンアドレスと呼ばれる二重ハッシュ技術を使用する.二重ハッシュは、2つのハッシュ関数を使用して、 が発生した後にレコードを格納するインデックスを計算する.
ダブルハッシュi発生 後、インデックスを取得するには、次の方法を使用します.

index = hash_a(string) + i * hash_b(string) % num_buckets

が発生しない場合、i=0であるため、インデックスはhash_aの値であり、 が発生した後、hash_aの結果はhash_bの処理を1回行う必要がある.hash_bは0に戻り、第2項を0に減少する可能性があります.これにより、hash は複数のレコードを同じbucketに挿入し、hash_bの結果に1を追加して処理することができます.これは、0にならないことを保証します.

index = (hash_a(string) + i * (hash_b(string) + 1)) % num_buckets

アルゴリズム実装

// hash_table.c
static int ht_get_hash(const char* s, const int num_buckets, const int attempt) {
    const int hash_a = ht_hash(s, HT_PRIME_1, num_buckets);
    const int hash_b = ht_hash(s, HT_PRIME_2, num_buckets);
    return (hash_a + (attempt * (hash_b + 1))) % num_buckets;
}

前章:hash関数次章:HashテーブルAPIの完了