C++の文字列のハッシュテーブル

Question

これまで、ハッシュテーブルに関する小さな練習を行ってきましたが、ユーザーは配列サイズを与えていましたが、構造体もこのようになっていました（ユーザーは入力するたびに数字と単語を入力していました）

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

だから、私は、配列のサイズを知っていたし、また、ユーザは、彼が入力として与えることでしょうどのように多くのアイテムと言っていたので、非常に簡単でした。私がやった方法は、それは、ユーザが、私がそこに データを置く空だった場合は、配列

に[（キー）ハッシュ化]位置配列を見つける

私

を与えたキーをハッシュ

• ました
• もしそれが私が見つけた次の自由な位置に入れていないならば。

私は逆インデックスを作成しなければならないので、私はそれをハッシュテーブルにすることができますreasearchingです。その言葉は約30回分の集まりから集められ、それはとても多くなります。 この場合、配列の長さはどのくらいですか？どのように私は単語をハッシュできますか？私は開いた住所や連鎖でhasingを使うべきですか？私たちがオンラインで見つけた場合、ハッシュテーブルをそのまま使用することができます。私は自分のことを理解してそれを作成することを好む。任意の手がかりは私を助ける:)

この実践では（逆インデックスハッシュテーブルを使用して）構造体はこのように見えます。 データタイプは、作成するハッシュテーブルのタイプです。

struct posting 
{ 
    string word; 
    posting *next 
} 

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

Answer 1

とにかく選択できます。文字列がABCであるとします。 A = 1、B = 2、C = 3、ハッシュ= 1 + 2 + 3 /（長さ= 3）= 2のハッシングを使用できます。

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

一方、単純な演習の場合は、MD5ハッシュも使用できます。その虹のテーブルが容易に入手できるように私は実用的な目的でそれを使用してお勧めしません:)

を--------- EDIT -------

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

その後

#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（ファイル名）関数を実行し、ファイル名の内容を取得したいいつでも達成するために。配列のインデックスを直接返します。

Answer 2

ハッシュテーブルは単純な2次元配列として実装できます。問題は、格納するアイテムごとに一意のキーを計算する方法です。データにはキーが組み込まれているものもあれば、他のものについては、あなたが計算しなければならないものがあります。

解決する必要がある次の問題は、ハッシュテーブルをレイアウトするか、サイズを変更する方法です。それは、あなたが最終的にいくつかのテストを通して自分のニーズに合わせる必要があることです。 MD5ハッシュの最初の2桁の組み合わせごとに1つ、255個のエントリを持つ配列の1次次元を設定することから始めることができます。コリジョンが発生すると、配列の2番目のディメンションにその1次ディメンションのインデックスに別のエントリを追加します。つまり、1次元配列を静的に定義し、必要に応じて2次元の項目を動的に割り当てることになります。うまくいけば、それは私にとってそうであるようにあなたに多くの意味があります。

ルックアップを実行すると、MD5ハッシュの最初の2桁を使用して、適切な1次次元インデックスをすぐに見つけることができます。次に、2次元に沿った相対線形の短い線形検索によって、求めるアイテムにすばやく移動します。

データセットが十分に大きい場合は、より大きな第1次元（MD5ハッシュの3桁の数字を使用）を使用する方が効率的であることがわかります。関係するテキストのサイズとレキシコンの使用の分布に応じて、あなたの結果はおそらくあなたのアーキテクチャのいくつかを指示します。

一方、小さくしてインテリジェンスを構築して、テーブルのサイズやレイアウトを自動的に変更することもできます。テーブルがいずれの方向にも長すぎると、パフォーマンスが低下します。