5

私は過去にハッシュテーブルに関する小さな演習を行いましたが、ユーザーは配列のサイズを指定していましたが、構造体もこのようでした (したがって、ユーザーは入力として毎回数値と単語を指定していました)

struct data
{
   int key;
   char c[20];
};

私は配列のサイズを知っていたので、それは非常に簡単でした. 私がやった方法は

  • ユーザーから渡されたキーをハッシュする
  • 配列内の位置配列[ハッシュ（キー）]を見つけます
  • 空の場合は、そこにデータを配置します
  • そうでない場合は、次の空いている位置に配置します。

しかし、今は逆インデックスを作成する必要があり、ハッシュテーブルを作成できるように再検索しています。そのため、単語は約 30 の txt から収集され、非常に多くなります。この場合、配列の長さはどのくらいですか? 単語をハッシュするにはどうすればよいですか? オープン アドレッシングまたはチェーンで hasing を使用する必要があります。この演習では、ハッシュ テーブルをオンラインで見つければそのまま使用できると述べています。しかし、私はそれを理解し、自分で作成することを好みます。手がかりは私を助けます:)

この演習 (ハッシュ テーブルを使用した逆インデックス) では、構造体は次のようになります。データ型は、作成するハッシュ テーブルの型です。

struct posting
{
    string word;
    posting *next
}

struct data
{
    string word;
    posting *ptrpostings;
    data *next
};
4

2 に答える 2

4

ハッシュは、任意の方法で実行できます。文字列が ABC であるとします。A=1、B=2、C=3、ハッシュ = 1+2+3/(長さ = 3) = 2 としてハッシュを使用できます。ただし、これは非常に原始的です。

配列のサイズは、デプロイするハッシュ アルゴリズムによって異なりますが、文字列ごとに明確な長さのハッシュを返すアルゴリズムを選択することをお勧めします。たとえば、SHA1 を使用することを選択した場合、ハッシュごとに 40 バイトを安全に割り当てることができます。Storeing SHA1 hash values in MySQLを参照してください。アルゴリズムについてはhttp://en.wikipedia.org/wiki/SHA-1を参照してください。安心して使えると思います。

一方、単純な演習用であれば、MD5 ハッシュを使用することもできます。レインボーテーブルは簡単に利用できるので、実用的な目的で使用することはお勧めしません:)

- - - - -編集 - - - -

あなたはこのように実装しようとすることができます::

#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#define MAX_LEN 30
using namespace std;

typedef struct
{
    string name; // for the filename
    ... change this to your specification
}hashd;

hashd hashArray[MAX_LEN]; // tentative

int returnHash(string s)
{
    // A simple hashing, no collision handled
    int sum=0,index=0;
    for(string::size_type i=0; i < s.length(); i++)
    {
        sum += s[i];
    }
    index = sum % MAX_LEN;
    return index;
}

int main()
{
    string fileName;
    int index;
    cout << "Enter filename        ::\t" ;
    cin >> fileName;
    cout << "Enter filename is     ::\t" + fileName << "\n";
    index = returnHash(fileName);
    cout << "Generated index is ::\t" << index << "\n";
    hashArray[index].name = fileName;
    cout << "Filename in array    ::\t" <<hashArray[index].name ;
    return 0;
}

次に、O(1) を実現するために、ファイル名の内容を取得したいときはいつでも、returnHash(filename) 関数を実行するだけです。配列のインデックスを直接返します:)

于 2013-04-15T13:44:20.897 に答える
1

ハッシュ テーブルは、単純な 2 次元配列として実装できます。問題は、格納する各アイテムの一意のキーを計算する方法です。データにキーが組み込まれているものもあれば、キーを計算する必要があるものもあります。上記で提案した MD5 は、おそらくニーズに適しています。

次に解決しなければならない問題は、ハッシュ テーブルをどのようにレイアウトまたはサイズ設定するかです。これは、いくつかのテストを通じて、最終的には独自のニーズに合わせて調整する必要があるものです。MD5 ハッシュの最初の 2 桁の組み合わせごとに 1 つずつ、255 エントリで配列の 1 番目の次元を設定することから始めることができます。衝突が発生するたびに、その 1 次元インデックスで配列の 2 次元に沿って別のエントリを追加します。これは、必要に応じて 2 次元のエントリを動的に割り当てながら、1 次元の配列を静的に定義することを意味します。うまくいけば、それは私と同じくらいあなたにとっても意味があります.

ルックアップを行うと、MD5 ハッシュの最初の 2 桁を使用して、正しい 1 次元インデックスをすぐに見つけることができます。次に、2 番目の次元に沿った比較的短い線形検索により、探しているアイテムにすばやく到達できます。

データセットが十分に大きい場合は、より大きな 1 次元 (MD5 ハッシュの最初の 3 桁を使用) を使用する方が効率的であることが実験からわかる場合があります。関連するテキストのサイズと辞書の使用の分布に応じて、結果によってアーキテクチャの一部が決まる可能性があります。

一方、テーブルのサイズ変更とレイアウトを自動的に行うために、小さく始めてインテリジェンスを組み込むこともできます。テーブルがいずれかの方向に長くなりすぎると、パフォーマンスが低下します。

于 2013-04-15T17:22:30.743 に答える