4

Symbolルビーと同じように実装したいです。

std::hashこのために、対応するのを返すユーザー定義リテラルを作成しましたstd::basic_string<T>。

コードは素晴らしかったですが、どこかで読んだように、同じプログラムの複数の実行でハッシュ関数が一貫していない可能性があります。さらに、コンパイル時にこの計算を行いたいと思っていました。これは、1）でサポートされておらず、2）戻り値が変更されたstd::hash場合にコードが破損するというものでした。std::hash

そこで、 java.lang.String.hashCodeの実装に基づいて、次の実装を作成しました。

typedef size_t symbol;

template<typename CharT>
constexpr size_t constant_hash(const CharT* p, size_t h = 0) noexcept
{
    return (*p == 0) ? h : constant_hash(p + 1, h * 31 + static_cast<size_t>(*p));
}

constexpr symbol operator "" _sym (const char* p, size_t n) noexcept
{
    return constant_hash(p);
}

私の質問は：この実装に問題はありますか？

GCC 4.7.1でしかテストできません。標準に準拠していて、他のコンパイラでも動作するかどうかを知りたいのですが。

以前の実装はGCCで機能していましたが、バイナリがclang ++でコンパイルされた場合にセグメンテーション違反が発生したためです（インクリメント演算子による未定義動作の問題だと思います）。

前もって感謝します

編集

clang ++での作業（KennyTMに感謝）

4

3 に答える 3

2

'\0'UBはありません。文字列に終端がある限り、正常に機能します。constexpr評価ではUBを呼び出すことができないことに注意してください。定数式のコンテキストでコンパイルエラーを生成するには、実行時にUBを発生させる算術演算またはポインタ演算が必要です。

static_castは不要であることに注意してください。オペランドはcharにプロモートされsize_tます。

h * 31また、一見したところ、ハッシュ関数はであるため、あまり見栄えがよくありません( h << 5 ) - h。1がバイナリ値全体にランダムに分散している、より大きな数値を選択する場合があります。しかし一方で、ASCIIの下位5ビットが最もエントロピーを持ち、これにより長さの異なる短い文字列間の衝突の可能性が排除されるため、彼らは賢くしようとしている可能性があります。

于 2012-06-22T08:53:00.837 に答える
2

注：n3333はC++17の提案です。ハッシュが複数の実行で同じ結果を生成するというC++11の要件はないと思いますが、実際には、現在のすべての実装で同じ結果が得られると思います。

于 2012-06-22T14:27:33.527 に答える
1

現在のアクティブなC++標準では、ハッシュ関数の定義は一般に、特定の方法でハッシュを実行する必要があるのではなく、ドメイン固有の実装の可能性を高めるためにそのように記述されています。たとえば、プールされた文字列を実行し、プールインスタンスのメモリ位置をハッシュ値として使用する可能性があります（ちなみに、これはrubyが文字列とハッシュを行う方法であり、いくつかの興味深い問題が発生しています）。参照ではなくデータでハッシュを計算している場合、定数式がない数学の形式を発見しない限り、値は安定します。

基本的に、この場合、「できない」とは、何が起こるかを述べるのではなく、特定の方法で動作することを許可することです。

とはいえ、を使用している場合std::hash、実行間で値が常に同じになることを保証することはできません（将来、n3333が採用された場合、それに依存するコードはすべて壊れます）。したがって、独自の値を定義することをお勧めします。安定したハッシュが必要な場合は、安定したハッシュ関数。

于 2012-06-22T16:13:43.383 に答える