u64ペアへのインデックスを作成するある種のハッシュ関数を使用します。一方はキーの作成元の値で、もう一方は置換値です。技術的には、スペースを節約する必要がある場合、インデックスの長さは3バイト（1600万- "16000千"-ペアと仮定）にすることができますが、私はu32を使用します。保存された値が（ハッシュ衝突）で計算された値と一致しない場合は、オーバーフローハンドラーに入ります。
- データに合わせてカスタムハッシュアルゴリズムを決定する必要があります
- データのサイズがわかっているので、データを大きくするためのアルゴリズムは必要ありません。
- 特定のデータに適合することはめったにないため、標準的なアルゴリズムの使用には注意が必要です。
- コードがWYSIWYGであることが確実でない限り、C ++メソッドの使用には注意が必要です（多くの非表示の呼び出しは生成されません）
- インデックスはペアの数より25％大きくする必要があります
考えられるすべての入力を実行し、衝突数の最小、最大、平均、および標準偏差を決定し、これらを使用して許容可能なパフォーマンスレベルを決定します。次に、プロファイルを作成して、可能な限り最高のコードを実現します。
必要なメモリスペース（u32インデックスを使用）は、（4 * 1.25）+ 8 + 8=ペアあたり21バイトまたは336MeBになり、通常のPCでは問題ありません。
________ 編集________
私は「RocketRoy」にお金を口の中に入れるように挑戦されました。ここに行きます：
問題は、（固定サイズの）ハッシュインデックスでの衝突処理に関係しています。ステージを設定するには：
- n個のエントリのリストがあり、エントリのフィールドに、ハッシュの計算元となる値vが含まれています。
- 数xが素数になるように、n * 1.25（およそ）の数のベクトルがあります。
- xの分数である素数yが計算されます
- ベクトルは、空いていることを示すために-1と言うように初期化されます
かなり標準的なものあなたが同意すると思います。
リスト内のエントリが処理され、ハッシュ値hが計算されてモジュロ処理され、ベクトルへのインデックスとして使用され、エントリへのインデックスがそこに配置されます。
最終的に、インデックスが指すベクトルエントリが占有されている（-1が含まれていない）状況に遭遇します-voilà、衝突。
だから私は何をしますか？元のhをhoとして保持し、yをhに追加し、xを法として、ベクトルに新しいインデックスを取得します。エントリが空いている場合はそれを使用します。それ以外の場合は、hoに到達するまでxを法としてyを追加し続けます。理論的には、xとyの両方が素数であるため、これが発生します。実際には、xはnより大きいので、そうではありません。
したがって、RocketRoyが非常にコストがかかると主張する「再ハッシュ」はそのようなことではありません。
このメソッドのトリッキーな部分は、すべてのハッシュメソッドと同様に、次のとおりです。
- xの適切な値を決定します（最終的に使用されるxが大きいほどトリッキーではなくなります）
- h = a（v）％xのアルゴリズムaを決定して、hのインデックスができるだけ少ない衝突でインデックスベクトルに合理的に均等に（「ランダムに」）入るようにします。
- 衝突がインデックスベクトルに適度に均等に（「ランダムに」）インデックスを付けるように、yの適切な値を決定します
________ 編集________
このコードを作成するのに時間がかかってすみません...他のものはより高い優先順位を持っていました。
とにかく、これは、ハッシュが二分木よりも迅速なルックアップの可能性が高いことを証明するコードです。一連のハッシュインデックスサイズとアルゴリズムを実行して、特定のデータに最適なコンボを見つけるのに役立ちます。すべてのアルゴリズムについて、コードは最初のインデックスサイズを出力します。これにより、ルックアップに14回以上の検索が必要にならず（バイナリ検索の場合は最悪の場合）、平均ルックアップにかかる検索は1.5回未満になります。
あなたが気づいていない場合に備えて、私はこれらのタイプのアプリケーションの素数が好きです。
必須のオーバーフロー処理を使用してハッシュアルゴリズムを作成する方法はたくさんあります。私はそれがスピードに変換されると仮定して単純さを選びました...そしてそれはそうします。i5 M 480 @ 2.67 GHzを搭載した私のラップトップでは、平均的なルックアップには55〜60クロックサイクルが必要です（1秒あたり約4500万回のルックアップになります）。一定数のインデックスと同上再ハッシュ値を使用して特別なget操作を実装し、サイクル数を40（1秒あたり6,500万回のルックアップ）に減らしました。getOpSpecを呼び出す行を見ると、インデックスiは0x444で排他的論理和されてキャッシュを実行し、より「現実世界」のような結果を実現します。
プログラムが特定のデータに適した組み合わせを提案していることをもう一度指摘しなければなりません。他のデータでは、別のコンボが必要になる場合があります。
ソースコードには、16000のunsigned long longペアを生成するためのコードと、さまざまな定数（インデックスサイズと再ハッシュ値）をテストするためのコードの両方が含まれています。
#include <windows.h>
#define i8 signed char
#define i16 short
#define i32 long
#define i64 long long
#define id i64
#define u8 char
#define u16 unsigned short
#define u32 unsigned long
#define u64 unsigned long long
#define ud u64
#include <string.h>
#include <stdio.h>
u64 prime_find_next (const u64 value);
u64 prime_find_previous (const u64 value);
static inline volatile unsigned long long rdtsc_to_rax (void)
{
unsigned long long lower,upper;
asm volatile( "rdtsc\n"
: "=a"(lower), "=d"(upper));
return lower|(upper<<32);
}
static u16 index[65536];
static u64 nindeces,rehshFactor;
static struct PAIRS {u64 oval,rval;} pairs[16000] = {
#include "pairs.h"
};
struct HASH_STATS
{
u64 ninvocs,nrhshs,nworst;
} getOpStats,putOpStats;
i8 putOp (u16 index[], const struct PAIRS data[], const u64 oval, const u64 ci)
{
u64 nworst=1,ho,h,i;
i8 success=1;
++putOpStats.ninvocs;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffff) /* unused position */
{
index[h]=(u16)ci;
goto added;
}
if (oval==data[i].oval) goto duplicate;
++putOpStats.nrhshs;
++nworst;
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted: /* should not happen */
duplicate:
success=0;
added:
if (nworst>putOpStats.nworst) putOpStats.nworst=nworst;
return success;
}
i8 getOp (u16 index[], const struct PAIRS data[], const u64 oval, u64 *rval)
{
u64 ho,h,i;
i8 success=1;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffffu) goto not_found; /* unused position */
if (oval==data[i].oval)
{
*rval=data[i].rval; /* fetch the replacement value */
goto found;
}
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted:
not_found: /* should not happen */
success=0;
found:
return success;
}
volatile i8 stop = 0;
int main (int argc, char *argv[])
{
u64 i,rval,mulup,divdown,start;
double ave;
SetThreadAffinityMask (GetCurrentThread(), 0x00000004ull);
divdown=5; //5
while (divdown<=100)
{
mulup=3; // 3
while (mulup<divdown)
{
nindeces=16000;
while (nindeces<65500)
{
nindeces= prime_find_next (nindeces);
rehshFactor=nindeces*mulup/divdown;
rehshFactor=prime_find_previous (rehshFactor);
memset (index, 0xff, sizeof(index));
memset (&putOpStats, 0, sizeof(struct HASH_STATS));
i=0;
while (i<16000)
{
if (!putOp (index, pairs, pairs[i].oval, (u16) i)) stop=1;
++i;
}
ave=(double)(putOpStats.ninvocs+putOpStats.nrhshs)/(double)putOpStats.ninvocs;
if (ave<1.5 && putOpStats.nworst<15)
{
start=rdtsc_to_rax ();
i=0;
while (i<16000)
{
if (!getOp (index, pairs, pairs[i^0x0444]. oval, &rval)) stop=1;
++i;
}
start=rdtsc_to_rax ()-start+8000; /* 8000 is half of 16000 (pairs), for rounding */
printf ("%u;%u;%u;%u;%1.3f;%u;%u\n", (u32)mulup, (u32)divdown, (u32)nindeces, (u32)rehshFactor, ave, (u32) putOpStats.nworst, (u32) (start/16000ull));
goto found;
}
nindeces+=2;
}
printf ("%u;%u\n", (u32)mulup, (u32)divdown);
found:
mulup=prime_find_next (mulup);
}
divdown=prime_find_next (divdown);
}
SetThreadAffinityMask (GetCurrentThread(), 0x0000000fu);
return 0;
}
生成されたペアファイルを含めることができませんでした（回答は明らかに30000文字に制限されています）。しかし、私の受信箱にメッセージを送ってください、そして、私はそれを郵送します。
そして、これらは結果です：
3;5;35569;21323;1.390;14;73
3;7;33577;14389;1.435;14;60
5;7;32069;22901;1.474;14;61
3;11;35107;9551;1.412;14;59
5;11;33967;15427;1.446;14;61
7;11;34583;22003;1.422;14;59
3;13;34253;7901;1.439;14;61
5;13;34039;13063;1.443;14;60
7;13;32801;17659;1.456;14;60
11;13;33791;28591;1.436;14;59
3;17;34337;6053;1.413;14;59
5;17;32341;9511;1.470;14;61
7;17;32507;13381;1.474;14;62
11;17;33301;21529;1.454;14;60
13;17;34981;26737;1.403;13;59
3;19;33791;5333;1.437;14;60
5;19;35149;9241;1.403;14;59
7;19;33377;12289;1.439;14;97
11;19;34337;19867;1.417;14;59
13;19;34403;23537;1.430;14;61
17;19;33923;30347;1.467;14;61
3;23;33857;4409;1.425;14;60
5;23;34729;7547;1.429;14;60
7;23;32801;9973;1.456;14;61
11;23;33911;16127;1.445;14;60
13;23;33637;19009;1.435;13;60
17;23;34439;25453;1.426;13;60
19;23;33329;27529;1.468;14;62
3;29;32939;3391;1.474;14;62
5;29;34543;5953;1.437;13;60
7;29;34259;8263;1.414;13;59
11;29;34367;13033;1.409;14;60
13;29;33049;14813;1.444;14;60
17;29;34511;20219;1.422;14;60
19;29;33893;22193;1.445;13;61
23;29;34693;27509;1.412;13;92
3;31;34019;3271;1.441;14;60
5;31;33923;5449;1.460;14;61
7;31;33049;7459;1.442;14;60
11;31;35897;12721;1.389;14;59
13;31;35393;14831;1.397;14;59
17;31;33773;18517;1.425;14;60
19;31;33997;20809;1.442;14;60
23;31;34841;25847;1.417;14;59
29;31;33857;31667;1.426;14;60
3;37;32569;2633;1.476;14;61
5;37;34729;4691;1.419;14;59
7;37;34141;6451;1.439;14;60
11;37;34549;10267;1.410;13;60
13;37;35117;12329;1.423;14;60
17;37;34631;15907;1.429;14;63
19;37;34253;17581;1.435;14;60
23;37;32909;20443;1.453;14;61
29;37;33403;26177;1.445;14;60
31;37;34361;28771;1.413;14;59
3;41;34297;2503;1.424;14;60
5;41;33587;4093;1.430;14;60
7;41;34583;5903;1.404;13;59
11;41;32687;8761;1.440;14;60
13;41;34457;10909;1.439;14;60
17;41;34337;14221;1.425;14;59
19;41;32843;15217;1.476;14;62
23;41;35339;19819;1.423;14;59
29;41;34273;24239;1.436;14;60
31;41;34703;26237;1.414;14;60
37;41;33343;30089;1.456;14;61
3;43;34807;2423;1.417;14;59
5;43;35527;4129;1.413;14;60
7;43;33287;5417;1.467;14;61
11;43;33863;8647;1.436;14;60
13;43;34499;10427;1.418;14;78
17;43;34549;13649;1.431;14;60
19;43;33749;14897;1.429;13;60
23;43;34361;18371;1.409;14;59
29;43;33149;22349;1.452;14;61
31;43;34457;24821;1.428;14;60
37;43;32377;27851;1.482;14;81
41;43;33623;32057;1.424;13;59
3;47;33757;2153;1.459;14;61
5;47;33353;3547;1.445;14;61
7;47;34687;5153;1.414;13;59
11;47;34519;8069;1.417;14;60
13;47;34549;9551;1.412;13;59
17;47;33613;12149;1.461;14;61
19;47;33863;13687;1.443;14;60
23;47;35393;17317;1.402;14;59
29;47;34747;21433;1.432;13;60
31;47;34871;22993;1.409;14;59
37;47;34729;27337;1.425;14;59
41;47;33773;29453;1.438;14;60
43;47;31253;28591;1.487;14;62
3;53;33623;1901;1.430;14;59
5;53;34469;3229;1.430;13;60
7;53;34883;4603;1.408;14;59
11;53;34511;7159;1.412;13;59
13;53;32587;7963;1.453;14;60
17;53;34297;10993;1.432;13;80
19;53;33599;12043;1.443;14;64
23;53;34337;14897;1.415;14;59
29;53;34877;19081;1.424;14;61
31;53;34913;20411;1.406;13;59
37;53;34429;24029;1.417;13;60
41;53;34499;26683;1.418;14;59
43;53;32261;26171;1.488;14;62
47;53;34253;30367;1.437;14;79
3;59;33503;1699;1.432;14;61
5;59;34781;2939;1.424;14;60
7;59;35531;4211;1.403;14;59
11;59;34487;6427;1.420;14;59
13;59;33563;7393;1.453;14;61
17;59;34019;9791;1.440;14;60
19;59;33967;10937;1.447;14;60
23;59;33637;13109;1.438;14;60
29;59;34487;16943;1.424;14;59
31;59;32687;17167;1.480;14;61
37;59;35353;22159;1.404;14;59
41;59;34499;23971;1.431;14;60
43;59;34039;24799;1.445;14;60
47;59;32027;25471;1.499;14;62
53;59;34019;30557;1.449;14;61
3;61;35059;1723;1.418;14;60
5;61;34351;2803;1.416;13;60
7;61;35099;4021;1.412;14;59
11;61;34019;6133;1.442;14;60
13;61;35023;7459;1.406;14;88
17;61;35201;9803;1.414;14;61
19;61;34679;10799;1.425;14;101
23;61;34039;12829;1.441;13;60
29;61;33871;16097;1.446;14;60
31;61;34147;17351;1.427;14;61
37;61;34583;20963;1.412;14;59
41;61;32999;22171;1.452;14;62
43;61;33857;23857;1.431;14;98
47;61;34897;26881;1.431;14;60
53;61;33647;29231;1.434;14;60
59;61;32999;31907;1.454;14;60
3;67;32999;1471;1.455;14;61
5;67;35171;2621;1.403;14;59
7;67;33851;3533;1.463;14;61
11;67;34607;5669;1.437;14;60
13;67;35081;6803;1.416;14;61
17;67;33941;8609;1.417;14;60
19;67;34673;9829;1.427;14;60
23;67;35099;12043;1.415;14;60
29;67;33679;14563;1.452;14;61
31;67;34283;15859;1.437;14;60
37;67;32917;18169;1.460;13;61
41;67;33461;20443;1.441;14;61
43;67;34313;22013;1.426;14;60
47;67;33347;23371;1.452;14;61
53;67;33773;26713;1.434;14;60
59;67;35911;31607;1.395;14;58
61;67;34157;31091;1.431;14;63
3;71;34483;1453;1.423;14;59
5;71;34537;2423;1.428;14;59
7;71;33637;3313;1.428;13;60
11;71;32507;5023;1.465;14;79
13;71;35753;6529;1.403;14;59
17;71;33347;7963;1.444;14;61
19;71;35141;9397;1.410;14;59
23;71;32621;10559;1.475;14;61
29;71;33637;13729;1.429;14;60
31;71;33599;14657;1.443;14;60
37;71;34361;17903;1.396;14;59
41;71;33757;19489;1.435;14;61
43;71;34583;20939;1.413;14;59
47;71;34589;22877;1.441;14;60
53;71;35353;26387;1.418;14;59
59;71;35323;29347;1.406;14;59
61;71;35597;30577;1.401;14;59
67;71;34537;32587;1.425;14;59
3;73;34613;1409;1.418;14;59
5;73;32969;2251;1.453;14;62
7;73;33049;3167;1.448;14;61
11;73;33863;5101;1.435;14;60
13;73;34439;6131;1.456;14;60
17;73;33629;7829;1.455;14;61
19;73;34739;9029;1.421;14;60
23;73;33071;10399;1.469;14;61
29;73;33359;13249;1.460;14;61
31;73;33767;14327;1.422;14;59
37;73;32939;16693;1.490;14;62
41;73;33739;18947;1.438;14;60
43;73;33937;19979;1.432;14;61
47;73;33767;21739;1.422;14;59
53;73;33359;24203;1.435;14;60
59;73;34361;27767;1.401;13;59
61;73;33827;28229;1.443;14;60
67;73;34421;31583;1.423;14;71
71;73;33053;32143;1.447;14;60
3;79;35027;1327;1.410;14;60
5;79;34283;2161;1.432;14;60
7;79;34439;3049;1.432;14;60
11;79;34679;4817;1.416;14;59
13;79;34667;5701;1.405;14;59
17;79;33637;7237;1.428;14;60
19;79;34469;8287;1.417;14;60
23;79;34439;10009;1.433;14;60
29;79;33427;12269;1.448;13;61
31;79;33893;13297;1.445;14;61
37;79;33863;15823;1.439;14;60
41;79;32983;17107;1.450;14;60
43;79;34613;18803;1.431;14;60
47;79;33457;19891;1.457;14;61
53;79;33961;22777;1.435;14;61
59;79;32983;24631;1.465;14;60
61;79;34337;26501;1.428;14;60
67;79;33547;28447;1.458;14;61
71;79;32653;29339;1.473;14;61
73;79;34679;32029;1.429;14;64
3;83;35407;1277;1.405;14;59
5;83;32797;1973;1.451;14;60
7;83;33049;2777;1.443;14;61
11;83;33889;4483;1.431;14;60
13;83;35159;5503;1.409;14;59
17;83;34949;7151;1.412;14;59
19;83;32957;7541;1.467;14;61
23;83;32569;9013;1.470;14;61
29;83;33287;11621;1.474;14;61
31;83;33911;12659;1.448;13;60
37;83;33487;14923;1.456;14;62
41;83;33587;16573;1.438;13;60
43;83;34019;17623;1.435;14;60
47;83;31769;17987;1.483;14;62
53;83;33049;21101;1.451;14;61
59;83;32369;23003;1.465;14;61
61;83;32653;23993;1.469;14;61
67;83;33599;27109;1.437;14;61
71;83;33713;28837;1.452;14;61
73;83;33703;29641;1.454;14;61
79;83;34583;32911;1.417;14;59
3;89;34147;1129;1.415;13;60
5;89;32797;1831;1.461;14;61
7;89;33679;2647;1.443;14;73
11;89;34543;4261;1.427;13;60
13;89;34603;5051;1.419;14;60
17;89;34061;6491;1.444;14;60
19;89;34457;7351;1.422;14;79
23;89;33529;8663;1.450;14;61
29;89;34283;11161;1.431;14;60
31;89;35027;12197;1.411;13;59
37;89;34259;14221;1.403;14;59
41;89;33997;15649;1.434;14;60
43;89;33911;16127;1.445;14;60
47;89;34949;18451;1.419;14;59
53;89;34367;20443;1.434;14;60
59;89;33791;22397;1.430;14;59
61;89;34961;23957;1.404;14;59
67;89;33863;25471;1.433;13;60
71;89;35149;28031;1.414;14;79
73;89;33113;27143;1.447;14;60
79;89;32909;29209;1.458;14;61
83;89;33617;31337;1.400;14;59
3;97;34211;1051;1.448;14;60
5;97;34807;1789;1.430;14;60
7;97;33547;2417;1.446;14;60
11;97;35171;3967;1.407;14;89
13;97;32479;4349;1.474;14;61
17;97;34319;6011;1.444;14;60
19;97;32381;6337;1.491;14;64
23;97;33617;7963;1.421;14;59
29;97;33767;10093;1.423;14;59
31;97;33641;10739;1.447;14;60
37;97;34589;13187;1.425;13;60
41;97;34171;14437;1.451;14;60
43;97;31973;14159;1.484;14;62
47;97;33911;16127;1.445;14;61
53;97;34031;18593;1.448;14;80
59;97;32579;19813;1.457;14;61
61;97;34421;21617;1.417;13;60
67;97;33739;23297;1.448;14;60
71;97;33739;24691;1.435;14;60
73;97;33863;25471;1.433;13;60
79;97;34381;27997;1.419;14;59
83;97;33967;29063;1.446;14;60
89;97;33521;30727;1.441;14;60
列1と2は、再ハッシュ値とインデックスサイズの間の大まかな関係を計算するために使用されます。次の2つは、最初のインデックスサイズと再ハッシュ係数の組み合わせで、ルックアップの平均検索数は1.5未満で、最悪の場合は14回の検索です。次に、平均および最悪の場合。最後に、最後の列はルックアップごとの平均クロックサイクル数です。タイムスタンプレジスタの読み取りに必要な時間は考慮されていません。
最良の定数（インデックスの数=31253および再ハッシュ係数=28591）の実際のメモリスペースは、最初に示した値（16000 * 2 * 8 + 1,25 * 16000 * 2 => 296000バイト）よりも多くなります。実際のサイズは16000*2 * 8 + 31253 * 2=>318506です。
最速の組み合わせは、およそ11/31の比率で、インデックスサイズは35897、再ハッシュ値は12721です。これは、平均1.389（1つの初期ハッシュ+ 0.389の再ハッシュ）で、最大14（1 + 13）になります。
________ 編集________
「gotofound;」を削除しました。main（）ですべての組み合わせを表示します。これは、もちろん、インデックスサイズが大きくなる代わりに、はるかに優れたパフォーマンスが可能であることを示しています。たとえば、57667と33797の組み合わせは、平均1.192と最大再ハッシュ6を生成します。44543と23399の組み合わせは、平均1.249と最大10の再ハッシュを生成します（（57667-44543）* 2 =26468バイトのインデックステーブルを節約します。 57667/33797）。
ハードコードされたハッシュインデックスサイズと再ハッシュ係数を持つ特殊な関数は、変数と比較して60〜70％の時間で実行されます。これはおそらく、コンパイラ（gcc 64ビット）がモジュロを乗算に置き換え、即時値としてコード化されるため、メモリ位置から値をフェッチする必要がないためです。
________ 編集________
キャッシュに関しては、2つの問題があります。
1つ目は、データのキャッシュです。これは、ルックアップが大規模なプロセスの小さなステップであり、テーブルデータのキャッシュラインがより少ないまたは（おそらく）より多く無効になり始めるリスクがあるためです。完全ではないにしても、より大きなプロセスの他のステップでの他のデータアクセスによって。つまり、プロセス全体で実行されるコードとアクセスされるデータが多いほど、関連するルックアップデータがキャッシュに残る可能性は低くなります（これは、OPの状況に関連する場合と関連しない場合があります）。（my）ハッシュを使用してエントリを見つけるには、実行する必要のあるすべての比較で2つのキャッシュミス（1つはインデックスの正しい部分をロードし、もう1つはエントリ自体を含む領域をロードする）が発生します。最初の試行でエントリを見つけると、2回のミス、2回目の試行で4回のミスが発生します。私の例では、ルックアップあたりの60クロックサイクルの平均コストは、テーブルがおそらく完全にL2キャッシュに存在し、ほとんどの場合、L1がそこに移動する必要がないことを意味します。私のx86-64CPUにはL1-3があり、RAM待機状態は約4、10、40、100です。これは、RAMが完全に排除され、L3がほとんどないことを示しています。
2つ目は、コードのキャッシュです。これは、小さく、タイトで、インラインで、制御転送（ジャンプと呼び出し）がほとんどない場合に、より大きな影響を及ぼします。私のハッシュルーチンは、おそらく完全にL1コードキャッシュにあります。通常の場合、コードキャッシュラインのロード数が少ないほど高速になります。