72

私は使っている

unordered_map<string, int>

と

unordered_map<int, int>

それぞれの場合に使用されるハッシュ関数と、それぞれの場合の衝突の可能性は? それぞれの場合に、一意の文字列と一意の int をキーとして挿入します。

string キーと int キーの場合のハッシュ関数のアルゴリズムとそれらの衝突統計に興味があります。

4

2 に答える 2

16

GCC C++1 は、Austin Appleby による「MurmurHashUnaligned2」を使用します

ハッシュ アルゴリズムはコンパイラに依存しますが、GCC C++11 用に提示します。@Avidan Borisovは、文字列に使用される GCC ハッシュ アルゴリズムが Austin Appleby による「MurmurHashUnaligned2」であることを鋭敏に発見しました。いくつかの検索を行ったところ、Github でミラー化された GCC のコピーが見つかりました。したがって：

unordered_map(ハッシュ テーブル テンプレート) およびunordered_set(ハッシュ セット テンプレート) に使用される GCC C++11 ハッシュ関数は次のようになります。

コード：

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

Austin Appleby のハッシュ関数の最新バージョンは「MurmurHash3」で、パブリック ドメインにリリースされています。

オースティンは彼の readme で次のように述べています。

SMHasher スイートには、一連の MurmurHash 関数の最新バージョンであるMurmurHash3も含まれています。新しいバージョンはより高速で堅牢であり、そのバリアントは x86 と x64 の両方のプラットフォームで 32 ビットと 128 ビットのハッシュ値を効率的に生成できます。

MurmurHash3 のソース コードについては、こちらを参照してください。

  1. MurmHash3.h
  2. MurmurHash3.cpp

そしてすごいのは!? パブリックドメインのソフトウェアです。それは正しい！ファイルの先頭には次のように記載されています。

// MurmurHash3 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.

したがって、C で独自のハッシュ テーブルを実装する場合を含め、オープン ソース ソフトウェア、個人プロジェクト、またはプロプライエタリ ソフトウェアで MurmurHash3 を使用する場合は、それを実行してください。

彼の MurmurHash3 コードをビルドしてテストするためのビルド手順が必要な場合は、https ://github.com/ElectricRCAaircraftGuy/smhasher/blob/add_build_instructions/build/README.md にいくつか書きました。うまくいけば、私が開いたこの PRが受け入れられ、最終的に彼のメイン リポジトリに届くことを願っています。ただし、それまでは、私のフォークのビルド手順を参照してください。

djb2、および K&R ハッシュ関数の 2 つのバージョンを含む追加のハッシュ関数については...

...（明らかにひどいもの、かなり良いもの）、ここで私の他の答えを参照してください：string のハッシュ関数。

以下も参照してください。

  1. https://en.wikipedia.org/wiki/MurmurHash
  2. さらなる研究: これらのハッシュ関数速度ベンチマークを見てください: https://github.com/fredrikwidlund/hash-function-benchmark (これを指摘してくれた @lfmunoz に感謝します)
于 2017-08-11T18:48:29.823 に答える