7

メモリの浪費を最小限に抑えるために負荷係数が 1 に近い場合、どのハッシュマップ衝突処理スキームが優れていますか?

個人的には、衝突が発生した場合に追加のストレージ スペースを必要としないため、答えはリニア プロービングによるオープン アドレッシングだと思います。これは正しいです？

4

3 に答える 3

1

いっぱいになったハッシュマップは線形検索に劣化するため、90% 未満に保つ必要があります。

より少ないメモリを使用するオープン アドレス指定については正しいです。チェーンには、各ノードにポインタまたはオフセット フィールドが必要です。

大量の挿入を持たない非常に軽量なハッシュテーブルが必要な場合に備えて、ハッシュ配列データ構造を作成しました。メモリ使用量を低く抑えるために、すべてのデータが同じメモリ ブロックに埋め込まれます。最初に HashArray 構造があり、次にハッシュと値の 2 つの配列があります。ハッシュ配列は、ルックアップ キーが値に格納されている場合にのみ使用できます。

typedef uint16_t HashType;  /* this can be 32bits if needed. */
typedef uint16_t HashSize;  /* this can be made 32bits if large hasharrays are needed. */
struct HashArray {
  HashSize length;        /* hasharray length. */
  HashSize count;         /* number of hash/values pairs contained in the hasharray. */
  uint16_t value_size;    /* size of each value.  (maximum size of value 64Kbytes) */
  /* these last two fields are just for show, they are not defined in the HashArray struct. */
  uint16_t hashs[length]; /* array of hashs for each value, this helps with resolving bucket collision */
  uint8_t  values[length * value_size]; /* array holding all values. */
};
#define hasharray_get_hashs(array) (HashType *)(((uint8_t *)(array)) + sizeof(HashArray))
#define hasharray_get_values(array) ((uint8_t *)(array)) + sizeof(HashArray) + \
                                       ((array)->length * sizeof(HashType))
#define hasharray_get_value(array, idx) (hasharray_get_values(array) + ((idx) * (array)->value_size))

マクロ hasharray_get_hashs および hasharray_get_values は、'hashs' および 'values' 配列を取得するために使用されます。

これを使用して、配列に既に格納されている複雑なオブジェクトの高速検索を追加しました。オブジェクトには、ルックアップに使用される文字列「name」フィールドがあります。名前はハッシュされ、オブジェクト インデックスとともに hasharray に挿入されます。hasharray に格納される値は、インデックス/ポインター/オブジェクト全体にすることができます (私は小さな 16 ビットのインデックス値のみを使用します)。

ハッシュ配列がほぼいっぱいになるまでパックしたい場合は、上記で定義した 16 ビットのハッシュではなく、完全な 32 ビットのハッシュを使用する必要があります。より大きな 32 ビット ハッシュは、ハッシュ配列が 90% 以上埋まっている場合に検索を高速に保つのに役立ちます。

上で定義した hasharray は最大 65535 しか保持できませんが、数百以上の値を持つものには決して使用しないので問題ありません。それ以上のものが必要な場合は、通常のハッシュテーブルを使用する必要があります。ただし、メモリが本当に問題になる場合は、HashSize タイプを 32 ビットに変更できます。また、ハッシュ ルックアップを高速に保つために、2 のべき乗の長さを使用します。プライム バケット長を使用することを好む人もいますが、これはハッシュ関数の分布が悪い場合にのみ必要です。

#define hasharray_empty_hash 0xFFFF /* hash value to mark empty slots. */
void *hasharray_search(HashArray *array, HashType hash, uint32_t *next) {
  HashType *hashs = hasharray_get_hashs(array);
  uint32_t mask = array->length - 1;
  uint32_t start_idx;
  uint32_t idx;

  hash = (hash == hasharray_empty_hash) ? 0 : hash; /* need one hash value to mark empty slots. */
  start_hash_idx = (hash & mask);
  if(*next == 0) {
    idx = start_idx; /* new search. */
  } else {
    idx = *next & mask; /* continuing search to next slot. */
  }

  /* find hash in hash array. */
  do {
    /* check for hash match. */
    if(hashs[idx] == hash) goto found_hash;
    /* check for end of chain. */
    if(hashs[idx] == hasharray_empty_hash) break;
    idx++;
    idx &= mask;
  } while(idx != start_idx);
  /* maximum tries reached (i.e. did a linear search of whole array) or end of chain. */
  return NULL;

found_hash:
  *next = idx + 1; /* where to continue search at, if this is not the right value. */
  return hasharray_get_values(array) + (idx * array->value_size);
}

ハッシュの衝突が発生するため、hasharray_search() を呼び出すコードは、検索キーと値オブジェクトに格納されているキーを比較する必要があります。それらが一致しない場合、 hasharray_search() が再度呼び出されます。また、1 つのキーに一致するすべての値を見つけるために「NULL」が返されるまで検索を続行できるため、一意でないキーが存在する可能性もあります。検索機能は、線形プロービングを使用して、キャッシュしやすいようにします。

typedef struct {
  char *name;   /* this is the lookup key. */
  char *type;
  /* other field info... */
} Field;

typedef struct {
  Field *list;          /* array of Field objects. */
  HashArray *lookup;    /* hasharray for fast lookup of Field objects by name.  The values stored in this hasharray are 16bit indices. */
  uint32_t field_count; /* number of Field objects in 'list'. */
} Fields;

extern Fields *fields_new(uint16_t count) {
  Fields *fields;
  fields = calloc(1, sizeof(Fields));
  fields->list = calloc(count, sizeof(Field));
  /* allocate hasharray to hold at most 'count' uint16_t values.
   * The hasharray will round 'count' up to the next power-of-2.
   * That power-of-2 length must be atleast (count+1), so that there will always be one empty slot.
   */
  fields->lookup = hasharray_new(count, sizeof(uint16_t));
  fields->field_count = count;
}

extern Field *fields_lookup_by_name(Fields *fields, const char *name) {
  HashType hash = str_to_hash(name);
  Field *field;
  uint32_t next = 0;
  uint16_t *rc;
  uint16_t idx;

  do {
    rc = hasharray_search(fields->lookup, hash, &next);
    if(rc == NULL) break; /* field not found. */
    /* found a possible match. */
    idx = *rc;
    assert(idx < fields->field_count);
    field = &(fields->list[idx]);
    /* compare lookup name with field's name. */
    if(strcmp(name, field->name) == 0) {
      /* found match. */
      return field;
    }
    /* field didn't match continue search to next field. */
  } while(1);
  return NULL;
}

配列が 99% 埋まり、キーが存在しない場合、検索は最悪の場合、配列全体の線形検索に低下します。キーが整数の場合、線形検索は悪くないはずです。また、同じハッシュ値を持つキーのみを比較する必要があります。値が 16 ビット値のみの場合、空のスロットで浪費されるスペースはそれほど多くないように、hasharray のサイズを維持しようとします。この設計では、16 ビットのハッシュと 16 ビットのインデックス値を使用すると、空のスロットごとに 4 バイトしか無駄になりません。オブジェクトの配列 (上記の例では Field 構造体) には空のスポットがありません。

また、私が見たほとんどのハッシュテーブル実装は、計算されたハッシュを保存せず、バケットの衝突を解決するために完全なキー比較を必要とします。バケットの検索にはハッシュ値のごく一部しか使用されないため、ハッシュを比較すると非常に役立ちます。

于 2010-11-01T09:22:45.203 に答える
1

質問への回答:負荷係数が 1 に近い場合、メモリの浪費を最小限に抑えるには、どのハッシュマップ衝突処理スキームが適していますか?

ハイ フィルを可能にするオープン アドレッシング/プロービング。あなたがそう言ったように、衝突に必要な余分なスペースがないためです（ちょうど、まあ、おそらく時間です-もちろん、これはハッシュ関数が完全ではないと仮定しています）。

「1 に近い負荷係数」を指定しなかった場合、または質問に「コスト」メトリックを含めなかった場合は、まったく異なります。

ハッピーコーディング。

于 2010-11-02T06:47:59.793 に答える
0

他の人が言ったように、線形プロービングでは、負荷係数が 1 に近づくと、時間の複雑さが線形探索に近づきます。(いっぱいになると、無限になります。) ここでは、メモリ効率のトレードオフがあります。分離連鎖は常に理論的に一定の時間を与えてくれますが、

通常、リニアプロービングでは、負荷率を 1/8 ～ 1/2 に保つことをお勧めします。配列が 1/2 いっぱいになったら、サイズを変更して元の配列のサイズを 2 倍にします。(参照: アルゴリズム。Robert Sedgewick著。Kevin Wayne。)。削除すると、配列のサイズも元のサイズの 1/2 に変更されます。もしあなたが本当に興味があるなら、私が上で述べた本から始めるのは良いことです. 実際には、0.72 は私たちが通常使用する経験値であると言われています。

于 2016-06-21T06:24:05.253 に答える