この簡単な実装を見つけました:
http://www.onextrabit.com/view/502c152965e7d250c5000001
ただし、共謀の回避はありませんでした。そこで、次のように修正しました。
#include <iostream>
#include <sstream>
using namespace std;
template <typename ElemType>
class HashTable {
private:
// data
ElemType* hashData;
// hash table size
int tableSize;
// djb2 hash function
int hashing(string key) {
int hash = 5381;
for (int i = 0; i < key.length(); i++)
hash = ((hash << 5) + hash) + (int)key[i];
return hash % tableSize;
}
public:
HashTable(int size) {
tableSize = size;
// init hash table data given table size
hashData = new ElemType[tableSize];
}
~HashTable() {
delete[] hashData;
}
void set(string key, const ElemType& value) {
int index = hashing(key);
int i = 0;
for (;(hashData[index] != (ElemType)NULL) && (i <= tableSize); i++) {
index = (index + 1) % tableSize;
}
if (i > tableSize) {
cout << "No empty bucket!" << endl;
return ;
}
hashData[index] = value;
}
string get(string key) {
int index = hashing(key);
stringstream result;
result << hashData[index];
int i = 0;
for (;(hashData[++index] != (ElemType)NULL) && (i <= tableSize); i++) {
result << " or " << hashData[index];
index %= tableSize;
}
return result.str();
}
};
int main() {
HashTable<int> hash(50);
hash.set("Hello", 12);
hash.set("World", 22);
hash.set("Wofh", 25);
for (int i = 1; i < 10; i++) {
hash.set("Wofh", i);
}
cout << "Hello " << hash.get("Hello") << endl;
cout << "World " << hash.get("World") << endl;
cout << "Wofh " << hash.get("Wofh") << endl;
return 0;
}
ハッシュテーブルを実装するのはこれが初めてです。"World" と "Wofh" がhashing()
関数から同じ結果を取得するようになりました。明らかにこれは共謀を引き起こしています。ただし、「World」を取得したい場合、すべての共謀値が表示されます。私の質問は、線形プローブのみを使用して「世界」番号(22)のみを表示する方法はありますか?