48

VS2005 の標準ハッシュ関数は、高パフォーマンスのルックアップを実現しようとすると非常に遅いことがわかりました。ほとんどの衝突を無効にする高速で効率的なハッシュ アルゴリズムの良い例は何ですか?

4

11 に答える 11

64

私は Microsoft Research のPaul Larsonと協力して、いくつかのハッシュテーブルの実装を行いました。彼はさまざまなデータセットで多数の文字列ハッシュ関数を調査し、単純な 101 の乗算と加算のループが驚くほどうまく機能することを発見しました。

unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned int hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}
于 2008-09-20T08:46:37.293 に答える
19

私の古いコードから：

/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}

これは速い。本当にめちゃくちゃ速い。

于 2008-09-19T00:01:51.257 に答える
8

Boost には、ほとんどの一般的な型に対していくつかの基本的なハッシュ関数を提供できるboost::hashライブラリがあります。

于 2008-09-19T00:01:31.757 に答える
7

それは常にデータセットに依存します。

ひもにCRC32を使うことで、驚くほど良い結果が得られました。さまざまな入力セットで非常にうまく機能します。

多くの優れた CRC32 実装は、ネット上で簡単に見つけることができます。

編集：ほとんど忘れていました：このページには、パフォーマンス数値とテストデータを備えた素敵なハッシュ関数の銃撃戦があります：

http://smallcode.weblogs.us/ <-- ページのさらに下。

于 2008-09-18T23:59:19.903 に答える
6

私は Jenkins ハッシュを使用してブルーム フィルター ライブラリを作成しました。これは優れたパフォーマンスを発揮します。

詳細とコードはこちらから入手できます: http://burtleburtle.net/bob/c/lookup3.c

これは、Perl がハッシュ操作 fwiw に使用するものです。

于 2008-09-19T00:24:04.167 に答える
6

一定の単語セットをハッシュする場合、多くの場合、最適なハッシュ関数は完全なハッシュ関数です。ただし、通常、ハッシュしようとしている単語のセットがコンパイル時にわかっている必要があります。レクサーでのキーワードの検出(およびキーワードのトークンへの変換) は、 gperfなどのツールで生成された完全ハッシュ関数の一般的な使用法です。完全なハッシュを使用するhash_mapと、単純な配列またはvector.

固定された一連の単語をハッシュしていない場合、明らかにこれは当てはまりません。

于 2008-09-19T03:13:05.617 に答える
2

Python 3.4 には、 SipHashに基づく新しいハッシュ アルゴリズムが含まれています。PEP 456は非常に有益です。

于 2014-03-19T18:29:30.190 に答える
2

私は少し検索を行いましたが、面白いことに、ポール・ラーソンの小さなアルゴリズムがここに表示されました http://www.strchr.com/hash_functions は、多くの条件でテストされた中で最も衝突が少なく、非常に高速です。アンロールまたはテーブル駆動。

ラーソンは単純に 101 を掛けて上記のループを加算します。

于 2012-02-20T02:41:45.030 に答える
2

文字列ハッシュの古典的な提案の 1 つは、文字を 1 つずつステップ実行して、ASCII/Unicode 値をアキュムレータに追加し、そのたびにアキュムレータに素数を掛けることです。(ハッシュ値のオーバーフローを許可)

  template <> struct myhash{};

  template <> struct myhash<string>
    {
    size_t operator()(string &to_hash) const
      {
      const char * in = to_hash.c_str();
      size_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash_map<string, int, myhash<string> > my_hash_map;

データを捨てずにそれより速くするのは難しいです。文字列の内容全体ではなく、数文字だけで文字列を区別できることがわかっている場合は、より迅速に行うことができます。

値が頻繁に計算される場合は、ハッシュ値を記憶する basic_string の新しいサブクラスを作成して、ハッシュ値をより適切にキャッシュしてみてください。ただし、 hash_map は内部でそれを行う必要があります。

于 2008-09-19T00:18:57.487 に答える
0

文字列が平均して1つのキャッシュ行よりも長いが、長さ+プレフィックスがかなり一意である場合は、長さ+最初の8/16文字だけにすることを検討してください。（長さはstd :: stringオブジェクト自体に含まれているため、読みやすくなっています）

于 2008-09-19T11:14:21.263 に答える