0

入力（i、k）を取り、一意の解を決定するハッシュ関数を決定しようとしています。

（i、k）の可能な入力は、0〜100の範囲です。各（i、k）を、三項ツリー内のノードの位置と見なします。

Ex: (0, 0) can diverge to (1, 1) (1, 0) (1, -1). 
    (1, 1) can diverge to (2, 2) (2, 1) (2, 0).

ここに与えられたサンプル：

http://www.google.com/imgres?imgurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlimg1156.gif&imgrefurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlnode41.html&h=413&w=416&sz=4&tbnid=OegDZu-yeVitZM:&tbnh=90&tbnw=91&zoom=1&usg=__9uQWDNYNLV14YioWWbrqPgfa3DQ=&docid=2hhitNyRWjI_DM&hl=en&sa=X&ei=xAfFUIbyG8nzyAHv2YDICg&ved=0CDsQ9QEwAQ

地図を使っています

map <double, double> hash_table

ペア（i、k）から決定され、その（i、k）の値にハッシュするキー値が必要です。

これまでのところ、次のような線形関数しか思い付くことができませんでした：double Hash_function（int i、int k）

{
    //double val = pow(i, k) + i;
    //return (val % 4294967296);
    return (i*3.1415 + k*i*9.12341); 
}

ただし、特定の（i、k）を持つ一意キーを判別することはできません。そのためにどのような機能を使用できますか？

4

3 に答える 3

2

数学的に言えば、あなたは全単射を求めています。これは、コンピュータサイエンスの意味でのハッシュ関数ではありません。これは、ハッシュ関数がときどき衝突を生成することが予想されるためです（完全なハッシュ関数でない限り）。

ラベルを付けhash_tableたのはハッシュテーブルではありません。std::mapは順序付きマップと呼ばれる別のデータ構造であり、未満の演算子が厳密な弱順序を<提供する任意のキータイプを使用できます。実際、ヘッダーから使用できます。std::pairutility

std::map<std::pair<int, int>, double> table;

テーブルに挿入するには、次を使用します。

table[std::make_pair(i, j)] = value;
于 2012-12-09T22:47:59.967 に答える
1

@Grizzly は、 double をキーとして使用すると問題があることは正しいです。文字列ベースのハッシュ手法を使用する方がよいでしょうか?

于 2012-12-09T22:18:45.593 に答える
0

i & k が 0 ～ 100 の場合、キーは単純な短い (署名されている場合もある) であり、. のようなもので一意に生成されますshort key = i | k << 8。

于 2012-12-09T23:01:20.610 に答える