17

独自のハッシュ関数を作成する必要があります。文字列内の各文字を数値 (つまり、a=1、b=2、c=3、...) にマップする単純なハッシュ関数を作成したいだけの場合、このハッシュを実行できる方法はありますか?個々の文字を調べるために最初に文字列を c-string に変換する必要のない文字列ですか? 文字列をハッシュするより効率的な方法はありますか?

4

10 に答える 10

9

個人的な経験から、私はこれが機能し、良いディストリビューションを生成することを知っています. ( http://www.cse.yorku.ca/~oz/hash.htmlからの盗作):

DJB2

このアルゴリズム (k=33) は、何年も前に dan bernstein によって comp.lang.c で最初に報告されました。このアルゴリズムの別のバージョン (現在は bernstein が支持) は xor を使用します: hash(i) = hash(i - 1) * 33 ^ str[i]; 数 33 の魔法 (素数であるかどうかにかかわらず、他の多くの定数よりもうまく機能する理由) が十分に説明されたことはありません。

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}
于 2012-11-21T05:52:28.833 に答える
7

最初の質問については、確かに、たとえば次のようなものです。

int hash = 0;
int offset = 'a' - 1;
for(string::const_iterator it=s.begin(); it!=s.end(); ++it) {
  hash = hash << 1 | (*it - offset);
}

2 つ目に関しては、文字列をハッシュするより良い方法がたくさんあります。たとえば、いくつかの C の例については、こちらを参照してください (上記のスニペットの行に沿って C++ に簡単に変換できます)。

于 2010-03-29T01:12:11.580 に答える
5

以下は、Stroustrup の本で見つけた C (++) ハッシュ関数です。

int hash(const char *str)
{
    int h = 0;
    while (*str)
       h = h << 1 ^ *str++;
    return h;
}

ハッシュ テーブルに使用している場合 (Stroustrup はこれを行っています)、代わりに素数を法とするハッシュの abs を返すことができます。だから代わりに

    return (h > 0 ? h : -h) % N_BUCKETS;

最後の行に。

于 2012-08-05T19:38:45.640 に答える
5

[]演算子を使用して、std::string から個々の文字を調べることができます。ただし、 Boost::Functional/Hashを参照して、より優れたハッシュ スキームに関するガイダンスを確認できます。c のハッシュ関数のリストもここにあります。

于 2010-03-29T01:09:14.380 に答える
0

小さな文字列の別の方法:

int hash(const char* str) {
    int hash = 0;
    int c = 0;

    while (c < std::strlen(str)) {
        hash += (int)str[c] << (int)str[c+1];
        c++;
    }
    return hash;
}
于 2015-12-07T08:04:55.580 に答える
0 
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// a variation on dan bernstein's algorithm
// [http://www.cse.yorku.ca/~oz/hash.html]
template<typename Int>
struct hash {
    hash() : acc(5381) { }
    template<typename Ch>
    void operator()(Ch ch) { acc = ((acc << 5) + acc) ^ ch; }
    operator Int() const { return acc; }
    Int acc;
};

int main(int argc, char* argv[])
{
    string s("Hellp, world");
    cout << hex << showbase
        << for_each(s.begin(), s.end(), hash<unsigned long long>()) << '\n';
    return 0;
}
于 2010-04-14T08:30:20.023 に答える
0

文字を一度に 4 つずつ xor します。

于 2010-03-29T01:10:12.100 に答える
-2

文字列クラスまたは反復子のメンバー関数operator[]またはatを使用して、文字列オブジェクトの個々の char にアクセスし、それを c スタイルの char 配列に変換する必要はありません。

文字列オブジェクトを整数にハッシュするには、次のように実行できる文字列オブジェクトの個々の文字にアクセスする必要があります。

for (i=0; i < str.length(); i++) {
    // use str[i] or str.at(i) to access ith element.
}
于 2010-03-29T01:10:08.777 に答える