sdbm を試してください:
hashAddress = 0;
for (counter = 0; word[counter]!='\0'; counter++){
hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress;
}
または djb2:
hashAddress = 5381;
for (counter = 0; word[counter]!='\0'; counter++){
hashAddress = ((hashAddress << 5) + hashAddress) + word[counter];
}
または Adler32:
uint32_t adler32(const void *buf, size_t buflength) {
const uint8_t *buffer = (const uint8_t*)buf;
uint32_t s1 = 1;
uint32_t s2 = 0;
for (size_t n = 0; n < buflength; n++) {
s1 = (s1 + buffer[n]) % 65521;
s2 = (s2 + s1) % 65521;
}
return (s2 << 16) | s1;
}
// ...
hashAddress = adler32(word, strlen(word));
ただし、これらはどれも本当に素晴らしいものではありません。本当に良いハッシュが必要な場合は、たとえばlookup3のようなもっと複雑なものが必要です。
ハッシュテーブルが70-80% を超えていっぱいになるとすぐに、多くの衝突が発生することが予想されることに注意してください。これは完全に正常であり、非常に優れたハッシュ アルゴリズムを使用している場合でも発生します。そのため、ほとんどのハッシュテーブルの実装では、ハッシュテーブルと比率に何かを追加するとすぐに、ハッシュテーブルの容量 (capacity * 1.5または) が増加します。capacity * 2size / capacityすでに 0.7 から 0.8 を超えています。容量を増やすと、新しいハッシュテーブルがより高い容量で作成され、現在の値のすべての値が新しい値に追加されます (ほとんどの場合、新しいインデックスは異なるため、すべての値を再ハッシュする必要があります)、新しい hastable 配列古いものを置き換え、古いものは解放/解放されます。1000 ワードのハッシュを計画している場合は、ハッシュテーブルの容量を 1250 にすることをお勧めします。
ハッシュテーブルは、少なくとも高速で効率的でなければなりません (したがって、常に予備の容量が必要です)。これはハッシュテーブルの縮小サイズです。高速です ( O(1)) が、通常、同じデータを別の構造に格納するために必要なスペースよりも多くのスペースを浪費します (ソートされた配列として格納する場合、必要な容量は 1000 だけです)。 1000 ワード; ダウンサイズは、ルックアップがその場合よりも速くならないことですO(log n))。ほとんどの場合、どちらの方法でも衝突のないハッシュテーブルは不可能です。ほぼすべてのハッシュテーブルの実装は、衝突が発生することを想定しており、通常は衝突に対処するための何らかの方法を備えています (通常、衝突によりルックアップが多少遅くなりますが、ハッシュテーブルは引き続き機能し、多くの場合、他のデータ構造を打ち負かします)。
また、非常に優れたハッシュ関数を使用している場合、最後に modulo ( %) を使用してハッシュ値を切り取る場合、ハッシュテーブルの容量が 2 のべき乗であれば要件はなく、利点すらありません。多くのハッシュテーブルの実装が常に 2 のべき乗容量を使用する理由は、それらが modulo を使用せず、代わりに AND ( &) をクロッピングに使用するためです。これは、AND 操作がほとんどの CPU で見られる最速の操作の 1 つであるためです (modulo は AND よりも決して高速ではありません)。 、最良の場合は同等に高速ですが、ほとんどの場合ははるかに遅くなります)。ハッシュテーブルが 2 の累乗のサイズを使用している場合、任意のモジュールを AND 演算に置き換えることができます。
x % 4 == x & 3
x % 8 == x & 7
x % 16 == x & 15
x % 32 == x & 31
...
ただし、これは 2 の累乗サイズでのみ機能します。モジュロを使用する場合、ハッシュが非常に悪い「ビット分布」を持つ非常に悪いハッシュである場合、2 のべき乗サイズは何かを購入することしかできません。>>通常、不正なビット分布は、ビット シフト (または)を使用しないハッシュや<<、ビット シフトと同様の効果を持つその他の操作が原因で発生します。
簡素化された lookup3 実装を作成しました。
#include <stdint.h>
#include <stdlib.h>
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
#define mix(a,b,c) \
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
#define final(a,b,c) \
{ \
c ^= b; c -= rot(b,14); \
a ^= c; a -= rot(c,11); \
b ^= a; b -= rot(a,25); \
c ^= b; c -= rot(b,16); \
a ^= c; a -= rot(c,4); \
b ^= a; b -= rot(a,14); \
c ^= b; c -= rot(b,24); \
}
uint32_t lookup3 (
const void *key,
size_t length,
uint32_t initval
) {
uint32_t a,b,c;
const uint8_t *k;
const uint32_t *data32Bit;
data32Bit = key;
a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
while (length > 12) {
a += *(data32Bit++);
b += *(data32Bit++);
c += *(data32Bit++);
mix(a,b,c);
length -= 12;
}
k = (const uint8_t *)data32Bit;
switch (length) {
case 12: c += ((uint32_t)k[11])<<24;
case 11: c += ((uint32_t)k[10])<<16;
case 10: c += ((uint32_t)k[9])<<8;
case 9 : c += k[8];
case 8 : b += ((uint32_t)k[7])<<24;
case 7 : b += ((uint32_t)k[6])<<16;
case 6 : b += ((uint32_t)k[5])<<8;
case 5 : b += k[4];
case 4 : a += ((uint32_t)k[3])<<24;
case 3 : a += ((uint32_t)k[2])<<16;
case 2 : a += ((uint32_t)k[1])<<8;
case 1 : a += k[0];
break;
case 0 : return c;
}
final(a,b,c);
return c;
}
このコードは、元のコードほどパフォーマンスが最適化されていないため、はるかに単純です。また、元のコードほど移植性はありませんが、現在使用されているすべての主要な消費者向けプラットフォームに移植できます。また、CPU エンディアンを完全に無視していますが、それは実際には問題ではありません。ビッグ エンディアンとリトル エンディアンの CPU で動作します。ビッグ エンディアンとリトル エンディアンの CPU では同じデータに対して同じハッシュが計算されないことに注意してください。ただし、これは必須ではありません。両方の種類の CPU で適切なハッシュを計算します。唯一重要なのは、単一のマシンで同じ入力データに対して常に同じハッシュを計算することです。
この関数は次のように使用します。
unsigned int stringToHash(char *word, unsigned int hashTableSize){
unsigned int initval;
unsigned int hashAddress;
initval = 12345;
hashAddress = lookup3(word, strlen(word), initval);
return (hashAddress%hashTableSize);
// If hashtable is guaranteed to always have a size that is a power of 2,
// replace the line above with the following more effective line:
// return (hashAddress & (hashTableSize - 1));
}
あなたは何だろうと思いinitvalます。まあ、それはあなたが望むものです。塩と言ってもいい。これはハッシュ値に影響を与えますが、ハッシュ値の品質が良くなったり悪くなったりすることはありません。たとえばinitval、同じデータを 2 回ハッシュしたい場合は異なる値を使用できますが、毎回異なるハッシュ値を生成する必要があります (そうなるという保証はありませんが、initval異なる可能性はかなり高いです。同じ値を作成する場合、これはそれを一種の衝突として扱わなければならないという非常に不運な偶然でしょう)。異なるものを使用することはお勧めできませんinitval同じハッシュテーブルのデータをハッシュするときの値 (これにより、平均してより多くの衝突が発生します)。initval のもう 1 つの用途は、ハッシュを他のデータと組み合わせたい場合です。この場合、既存のハッシュinitvalは他のデータをハッシュするときに使用されます (したがって、他のデータと前のハッシュの両方がハッシュ関数の結果に影響します)。 ）。initvalハッシュテーブルの作成時に任意の値を設定したり、ランダム値を選択したりすることも0できます (ハッシュテーブルのこのインスタンスには常にこのランダム値を使用しますが、各ハッシュテーブルには独自のランダム値があります)。
衝突に関する注意:
通常、衝突は実際にはそれほど大きな問題ではありません。通常、衝突を回避するためだけに大量のメモリを浪費することは報われません。問題はむしろ、効率的な方法でそれらに対処する方法です。
あなたは現在9000語を扱っていると言いました。ソートされていない配列を使用していた場合、配列内の単語を見つけるには、平均で 4500 回の比較が必要になります。私のシステムでは、4500 回の文字列比較 (単語の長さが 3 ～ 20 文字であると仮定) には 38 マイクロ秒 (0.000038 秒) かかります。そのため、このような単純で効果のないアルゴリズムでも、ほとんどの目的には十分に高速です。単語リストを並べ替えてバイナリ検索を使用すると仮定すると、配列内の単語を見つけるのに必要な比較は平均で 13 回だけです。13 回の比較は、時間的にはほぼゼロに近く、確実にベンチマークするには少なすぎます。したがって、ハッシュ テーブル内の単語を見つけるのに 2 ～ 4 回の比較が必要な場合、それがパフォーマンスに大きな問題をもたらす可能性があるかどうかという質問に 1 秒も無駄にすることはありません。
あなたの場合、バイナリ検索を使用したソート済みリストは、ハッシュテーブルをはるかに上回る可能性さえあります。確かに、13 回の比較は 2 ～ 4 回の比較よりも時間がかかりますが、ハッシュテーブルの場合は、最初に入力データをハッシュしてルックアップを実行する必要があります。ハッシュだけでも、すでに 13 回以上の比較が必要になる場合があります。ハッシュが優れているほど、同じ量のデータをハッシュするのに時間がかかります。したがって、ハッシュテーブルは、非常に大量のデータがある場合、またはデータを頻繁に更新する必要がある場合 (たとえば、テーブルに単語を常に追加/削除する必要がある場合) にのみパフォーマンスが向上します。はソートされたリスト用です)。ハッシュブルであるという事実O(1)は、それがどれほど大きいかに関係なく、ルックアップが約になることを意味するだけです。必要な時間は常に同じです。O(log n)検索が単語数に応じて対数的に増加することを意味するだけです。つまり、単語が増えると、検索が遅くなります。しかし、Big-O 記法は絶対速度については何も言いません! これは大きな誤解です。O(1)アルゴリズムが常にアルゴリズムよりも高速に実行されるとは言いませんO(log n)。Big-O 表記は、O(log n)アルゴリズムが特定の数の値に対して高速であり、値の数を増やし続ける場合、アルゴリズムはある時点でO(1)アルゴリズムを確実に追い越すことを示しているだけですが、現在の単語数ははるかに多い可能性がありますO(log n)その点より下。両方のアプローチをベンチマークしないと、Big-O 表記を見ただけではどちらが速いかはわかりません。
衝突に戻る。衝突したらどうする？衝突の数が少ない場合、ここでは衝突の全体数 (ハッシュテーブルで衝突している単語の数) ではなく、インデックスあたりの数 (同じハッシュテーブル インデックスに格納されている単語の数) を意味します。あなたの場合はおそらく 2-4)、最も簡単な方法は、それらをリンクされたリストとして保存することです。このテーブル インデックスにこれまで衝突がなかった場合、キーと値のペアは 1 つだけです。衝突があった場合、キーと値のペアのリンク リストがあります。その場合、コードはリンクされたリストを繰り返し処理し、各キーを検証して、一致する場合は値を返す必要があります。あなたの数字では、このリンクされたリストには 4 つ以上のエントリがなく、4 つの比較を行うことはパフォーマンスの点で重要ではありません。したがって、インデックスを見つけることはO(1)、値を見つけること (またはこのキーがテーブルにないことを検出すること) は ですO(n)が、ここでnは連結リスト エントリの数のみです (つまり、最大で 4 です)。
衝突の数が増えると、リンクされたリストが遅くなる可能性があり、動的にサイズ変更され、並べ替えられたキーと値のペアの配列を格納することもできますO(log n)。nhastable 内のすべてのキーではなく、その配列内のキーの数のみです。1 つのインデックスで 100 回の衝突があったとしても、正しいキーと値のペアを見つけるには、多くても 7 回の比較が必要です。それはまだ何もないに近いです。1 つのインデックスで実際に 100 の衝突がある場合、ハッシュ アルゴリズムがキー データに適していないか、ハッシュ テーブルの容量が小さすぎるかのいずれかです。動的にサイズ変更され、並べ替えられた配列の欠点は、キーの追加/削除が、リンクされたリストの場合よりもいくらか手間がかかることです (コード的に、必ずしもパフォーマンス的にではありません)。そのため、衝突の数を十分に低く抑える場合は通常、連結リストを使用するだけで十分であり、そのような連結リストを C で自分で実装し、それを既存のハッシュテーブル実装に追加することはほとんど簡単です。
私が持っているほとんどのハッシュテーブルの実装は、衝突に対処するためにそのような「代替データ構造へのフォールバック」を使用しているようです。欠点は、代替データ構造を格納するために少し余分なメモリが必要であり、その構造内のキーを検索するためにもう少し多くのコードが必要になることです。衝突をハッシュテーブル自体に保存し、追加のメモリを必要としないソリューションもあります。ただし、これらのソリューションにはいくつかの欠点があります。最初の欠点は、すべての衝突が、より多くのデータが追加されるにつれて、さらに多くの衝突の可能性を増加させることです。2 つ目の欠点は、これまでの衝突の数に比例してキーのルックアップ時間が減少する一方で (前に述べたように、すべての衝突はデータが追加されるにつれてさらに多くの衝突につながります)、ハッシュテーブルにないキーのルックアップ時間はさらに悪化し、最終的に、ハッシュテーブルにないキーのルックアップを実行すると (ただし、ルックアップを実行しないとわかりません)、ルックアップに線形時間と同じくらいの時間がかかる場合があります。ハッシュテーブル全体を検索します (YUCK!!!)。したがって、余分なメモリを節約できる場合は、衝突を処理する別の構造を使用してください。