0

この簡単な実装を見つけました:

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)のみを表示する方法はありますか?

4

1 に答える 1

1

各テーブル エントリには、ハッシュに一致する一連のキーと値のペアが含まれている必要があります。テーブル エントリを検索した後、要求されたキーのセットを検索する必要があります。

衝突がまれな場合は、ペアの単純なベクトルで十分です。検索が遅すぎるほど頻度が高く、テーブルを拡大したり、より優れた has 関数を使用しても頻度を減らすことができない場合は、ベクトルを並べ替えてバイナリ検索を使用するかstd::map、 、または別のハッシュ テーブルを使用することを検討してください (衝突する要素を格納します。

もちろん、これが学習演習でない限り、通常はそのまま使用しますstd::unordered_map(または、C++11 ライブラリを使用できない場合は、Boost、TR1、または STL の同等物)。

また、メモリやその他のリソースを管理するクラスを設計するときは、常に3 つのルールを覚えておいてください。誰かがそれをコピーしようとすると、あなたのクラスはひどくうまくいかないでしょう.

于 2013-07-15T16:20:23.457 に答える