3

私のCプログラムでは、4つの8ビット（char）変数が構造体に割り当てられています。配列にインデックスを付けるキー（構造全体を表す）を作成するためにこれらの数値をハッシュしたい場合は、どうすればよいですか？（プログラムにはこれらの構造の多くがあります。シンボルテーブルを検索してそれらが存在するかどうかを確認する必要があるため、他の構造を作成したくない場合は、使用するハッシュアルゴリズムがわかりません。キーインデックス検索を実行したい）。

私は、4つの数値を取り、それらを16進数に変換し、それらを連続して配置し、出てきた数値を10進数に変換する一種のハッシュについて考えました。

しかし、私はもっと「重い」ものが必要です...この方法は無駄すぎるようで、配列インデックスの作成にはあまり適切ではないと思います。

それは...ですか？可能であれば、32ビットよりも少ないメモリを使用する別の種類のハッシュ関数はありますか？

4

4 に答える 4

2

1つの可能性（OPが説明しているとは思わない）は、4つのchar値を単一の32ビット整数に結合し、それをハッシュテーブルのサイズ（おそらく素数）で変更することです。

unsigned int combined = (c1 << 24 ) | (c2 << 16 ) | (c3 << 8 ) | (c4);
unsigned int hashval = combined % hashtablesize;

もちろん、4つの個別のバイトの実際の期待値に依存しますが、このタイプのハッシュはかなり効率的であり、通常は良好な分布を持っています。結果のハッシュ値を期待されるデータセットでテストして、分布がある程度均一であることを確認するとよいでしょう。

于 2012-05-16T17:29:33.713 に答える
2

このハッシュ関数のリストをご覧になることをお勧めします。

ハッシュテーブルを実装するには（これがあなたの目標だと思います）、同様の入力値に対してあまりにも多くのハッシュ衝突を避けるために、雪崩効果のあるハッシュ関数が必要です。

もちろん、任意の関数を使用して文字を任意の整数表現に変換することもできますが、この表現が入力ごとに変化しない場合は、効果的に連結リストのパフォーマンスが得られます (テーブル サイズが256 であり、バイト 4 で変化する構造体はありません)。32 ビット ハッシュについてどのような懸念がありますか? もちろんhash%tablesize、インデックス作成に使用しますか？

通常、暗号化ハッシュ関数 (md5、sha-1 など) も使用しません。非暗号化ハッシュ関数 (Pearson/Jenkins ハッシュなど) のいずれかを選択するだけです。

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
  uint32_t hash, i;
  for(hash = i = 0; i < len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

補足: ハッシュ値の分布が良好な場合は、ハッシュ テーブルのサイズが十分に大きいことも確認してください。アレイの占有率 (負荷係数) が 1 に近づくと、パフォーマンスが低下することがわかります。これは、ハッシュの衝突の可能性が高くなるためです。

于 2012-05-16T19:11:07.367 に答える
0

可能であれば、32ビットよりも少ないメモリを使用する別の種類のハッシュ関数はありますか？

これは幻想的な問題です。キーは配列インデックスです。どこにも保存されず、ルックアップで計算されます。Cの配列は連続したブロックであり、配列の先頭と型のサイズにインデックスを掛けたものに基づいて個々の要素にアクセスします。

キーの場合は、値を符号なし32ビットタイプにキャストするだけです（使用するだけintでunsigned intなく、サイズが必ずしも32ビットであるとは限らないため）。

#include <inttypes.h>
char x[4] = { 'A', 'B', 'C', 'D' };
uint32_t *key = (uint32_t*)&x;

次に、テーブルサイズに基づいてモジュラスを実行します。

于 2012-05-16T17:54:45.297 に答える
0

構造体を配列に入れてみませんか?

#include <stdio.h>

typedef struct {
  char a,b,c,d;
} item;
item items[20];

int main(int argc, char *argv[])
{
  items[0].a = 4;
  items[0].b = 6;
  items[0].c = 1;
  items[0].d = 3;
  // ...
  items[4].a = 12;
  // ...
  printf("%d %d %d %d\n", items[0].a, items[0].b, items[0].c, items[0].d);
  return 0;
}

明らかに、これはメモリ フットプリントが少ないソリューションです。データはメイン配列に直接格納されるため、ハッシュ インデックスは必要ありません。配列のインデックスがメモリを消費せずにジョブを実行するからです。

もちろん、ポインターや一部の C++ ベクトル機能などを使用することもできますが、これが最も単純で効率的な方法です。

唯一の注意点は、配列のサイズ (アイテムの数) を知っている必要があること、または XXX を超えることはないということです...

于 2012-05-16T17:36:21.657 に答える