私は言語の通訳を書いています。問題があります: 任意の型の値をインデックスで配置できる型辞書を作成したいのですが、任意の型の値 (simple[int,float,string] または complex[list,array,dictionary] の単純型または単純型の複合体 ...)。これは python-lang と同じです。ハッシュ関数のどのアルゴリズムを使用すればよいですか?
文字列のハッシュには多くの例があります。最も単純なものは、すべての文字の合計を 31 倍し、HASH_SIZE で割った単純な数値です。
しかし、DIFFERENT TYPES については、もっと複雑なアルゴリズムに違いないと思います。SHA256 を見つけましたが、ハッシュ テーブルのアドレス指定に「unsigned char[32]」結果型を使用する方法がわかりません。コンピューターの RAM よりもはるかに多くなります。ありがとうございました。
一般的なアプローチは、ハッシュ関数を型に属するメソッドとして定義することです。このようにして、共通のAPIを介してさまざまなタイプのさまざまなアルゴリズムを呼び出すことができます。
もちろん、これには、インタプリタで使用するすべてのbaisc"cタイプ"のラッパークラスを定義する必要があります。
C++11、最新の C++ 標準 - std::unordered_map、std::unordered_set にはハッシュ テーブルがあります。
編集：
型ごとに分布が異なるため、通常、型ごとに独自のハッシュ関数があります。これは、Java (Object から継承された .hashCode() メソッド)、C#、C++11、およびその他の多くの実装で行われている方法です。
EDIT2：
典型的なハッシュ関数は、次の 2 つのことを行います。
1.) 自然数でオブジェクト表現を作成します。(これは Java の .hashCode() が行うことです) たとえば、文字列 "CAT" は次のように変換できます。
67 * 256^2 + 65 * 256^1 + 84 = 4407636
2.) この番号を配列内の位置にマップします。これを行う方法の1つは次のとおりです。
integer_part(fractional_part(k*4407636)*m)
ここで、k は定数です (Donald Knuth の著書 Art of Programming では (sqrt(5)+1)/2 を推奨しています)。m はハッシュ テーブルのサイズで、fractional_part と integer_part (明らかに) 実数の小数部分と整数部分を計算します。 .
ハッシュ テーブルの実装では、衝突を処理する必要があります。特に、ハッシュ テーブルのサイズよりもはるかに多くのキーが存在する場合です。
EDIT3：
この件についてもっと読んだところ、67 * 256^2 + 65 * 256^1 + 84 = 4407636 は hash_code を行うには本当に悪い方法のようです。これは、「somethingAAAAAABC」と「AAAAAABC」がまったく同じハッシュ コードを与えるためです。