1

私はハッシュテーブルがどのように機能するかをブラッシュアップしているので、ハッシュ関数が格納された値と一致する一意の (この質問の目的のために) ハッシュテーブル値を計算する方法を理解しています。したがって、格納された値が検索されると、ハッシュ関数コンピューターにハッシュ テーブルの値を与えます。

OK、これでハッシュ テーブルの値が得られましたが、これはどのように改善されるのでしょうか? 一致するハッシュ テーブルの値が見つかるまで反復処理を行う必要はありませんか?

4

3 に答える 3

2

ハッシュ関数は、配列内のインデックスに直接マップするために使用されます。したがって、検索や反復は行われません

于 2012-11-20T20:46:58.373 に答える
1

ハッシュテーブルは配列に格納されます。ハッシュ値は配列インデックスにマップされます。実装に応じて、ハッシュ値は配列インデックスであるか、配列のサイズを法として取得されるより広い範囲の数値です。

次に、配列内のその場所を確認したら、複数の値が同じハッシュ値を持つ可能性があるため、そこの値が一致することを確認する必要があります。通常、実際には、ハッシュテーブルの同じ場所にハッシュされたすべての値のリンクリストをナビゲートします。これは、完全なリストよりもはるかに短いリストです（特に、ハッシュテーブルのサイズがその中のデータの量に比例する場合）。

于 2012-11-20T20:49:49.430 に答える
0

多くの異なるハッシュ テーブルがあり、それぞれ実装に関する詳細が異なりますが、最も単純なハッシュ テーブルは、配列へのインデックスとしてハッシュ コードを使用します。

#define TABLESIZE 1000

char **gHashTable[TABLESIZE];

void clearHashTable() {
  memset(gHashTable, 0, sizeof(gHashTable));
}

int calculateHashCode(char *string) {
  int val = 0;
  for (int i = 0; string[i] != '\0'; ++i)
    val += string[i];
  return val;
}

void insertInHash(char *string) {
  int hashCode = calculateHashCode(string);
  gHashTable[hashCode % TABLESIZE] = string;
}

int isInHashTable(char *string) {
  int hashCode = calculateHashCode(string);
  return gHashTable[hashCode % TABLESIZE] != 0;
}

現在、この単純なハッシュは文字列の高速検索をサポートしています。衝突をうまく処理できず、ハッシュ関数はひどいもので、他にも多くの問題がありますが、うまくいきます。

于 2012-11-20T20:53:22.403 に答える