URL短縮サービスに似たアプリケーションの場合、推測できないIDを作成したいと思います。これは、皆さんがよく知っていると思います。このようなIDの例を次に示します。
これらをデータベーステーブルの主キーとして挿入するときに衝突のリスクを最小限に抑えて（またはまったく）、これらを生成するための優れた効率的な手法は何ですか？
編集：
Piskvorはもちろん素晴らしいポイントになります。36 ^ 6の制限に達する前に、衝突のリスクを最小限に抑えることを意味していることを述べておかなければなりません。
編集2
ええと、それをスクラップします、彼のポイントはもちろんそれよりはるかに多くを説明していました。うーん。それなら、おそらく（私がすでに他の場所で読んだように）idでテーブルを事前生成しますか？36 ^ 6にバインドされていて、連続しない制約がある場合、これが最も効率的な手法でしょうか？
Set ID length. // e.g. 6
do {
Generate a short random ID of the given length
Collision?
- No:
DONE!
- Yes:
increase ID length
} while true
IDの長さが有限の場合、常に衝突のリスクがあります。例から[a-z0-9] {6} IDがあると仮定すると、2,176,782,336 IDになるとすぐに、衝突が100％保証されます（より多くの利用可能なキー）。誕生日の問題のために、あなたははるかに早く衝突するでしょう。このような小さなキースペースでは、衝突を回避する方法はありません。代わりに、何らかの衝突回復が必要になります。
衝突しなくなるまでIDを生成できますが、キースペースがいっぱいになると、徐々に遅くなります。[an]と[pz]が既に使用されている[az]のキースペースを想像してください。これで、新しいランダムIDはすべて次のようになります。衝突しないよりも衝突する可能性が高い。キースペースを完全に埋めると、ループはまったく終了しません。
私が提案するアルゴリズムは、この点で多分慎重です。衝突が見つかった場合、徐々に長いIDを試行します（「衝突=>短いキースペースをチェックすることは不可能である」と想定しているため）。効率的ではありませんが、数回の反復で衝突しないIDが見つかる可能性があります。
少し奇妙な考え。順列を使用しないのはなぜですか？たとえば、最初のIDを生成するときに値のセット[0-9a-z]があります。辞書式順序で最初の順列を取ります。次に2番目など。推測しにくくするために、辞書式順序の規則を変更できます。「a」は「t」などの後に続くと言います。完全な順列の代わりにタプルを使用することもできます。これにより、衝突が発生しなくなります。
このアイデアが実際に何であるかは、ある種の双方向ハッシュ関数を作成することです。基本的に、数値「1」を何らかの方法でエンコードして「q8d3dw」のようなものを取得し、「q8d3dw」をデコードして「1」に戻すことができる場合、この関数がすべての値に対して一意の文字列を提供することを確信できます。 1から36^6まで。
問題は、実際にこの関数を選択することです。簡単な方法は、「1」を「000000」、「2」を「000001」、「12」を「00000b」に関連付けることです。基本的に、使用可能なすべての文字列を辞書式順序で配置し、idと等しい位置で文字列を選択します。ただし、これは非常に簡単に推測できます。したがって、できることは、辞書式順序の規則を人為的に変更することです。通常の順序（0,1,2,3 ... a、b、c ... x、y、z）を使用する代わりに、少しシャッフルして（a、5、t、3）のようにすることができます。 ...）。これにより、もう少しわかりにくい結果が生成されます。ただし、最初の要素は「aaaaaa」、2番目は「aaaaaa5」、次に「aaaaat」であるため、それでもかなり推測できます。したがって、辞書式順序のルールをさらに変更できます。それらをキャラクターの位置に依存させます。2番目の文字ID（y、7,3、r ...）の最初の文字ID（a、5、t、3 ...）の順序を言います。
かなり長いものになるので、今は擬似コードを投稿しません。そして、あなたが楽しみのためにこの種のアルゴリズムを作成することに興味がない限り、私はあなたにそのルートで行くことを勧めていません:)。ただし、このルートを使用する場合は、衝突の可能性なしにこのIDを生成する非常に効率的な方法になる可能性があります。そして、ドナルド・クヌース博士による「Artofcomputerprogramming」の第4巻を読むことをお勧めします。このようなアルゴリズムの実装には多くの提案があります。
@ivan：これが実装です。
まず、6つの文字列が必要です。これらを生成するためのコードは、次のとおりです。
$letters = range('a', 'z');
$numbers = range(0, 9);
$char_list = array_merge_recursive($letters, $numbers);
for ($i = 0; $i <= 5; $i++) {
shuffle($char_list);
echo '$mysterykey[' . $i . "] = '" . implode($char_list) . "';\n";
}
次に、その出力を関数で使用できます。
function int_to_x36($value) {
$mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
$mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
$mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
$mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
$mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
$mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';
$x36 = array();
for ($i = 5; $i >= 0; $i--) {
$x36[$i] = 0;
$y = pow(36, $i);
if ($value >= $y) {
$z = floor($value/$y);
$value = $value - ($z * $y);
$x36[$i] = $z;
}
}
$encoded = '';
for ($i = 0; $i <= 5; $i++) {
$encoded .= $mysterykey[$i][$x36[$i]];
}
return $encoded;
}
function x36_to_int($value) {
$mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
$mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
$mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
$mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
$mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
$mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';
$value36 = str_split($value);
$x36 = array();
for ($i = 0; $i <= 5; $i++) {
$x36[$i] = strpos($mysterykey[$i], $value36[$i]);
}
$x = 0;
for ($i = 5; $i >= 0; $i--) {
$x += $x36[$i] * pow(36, $i);
}
return $x;
}
私は何かを見落としていると確信していますが、それは機能しているようです。
たとえば、大きな乱数とSHA-256ハッシュ？後でニーズに合わせて短くすることができます。
サイトが十分に大きい場合、つまり「 1秒あたり数百の新しいIDを割り当てる必要がある」（1年以内に36 ^ 6のキースペースを使い果たすなど、他の問題が発生する）のように、事前に生成することができます。キーを割り当てます。
以下は擬似コードの例です。このようなトラフィックの多いサイトでは、使用するアルゴリズムを最適化する必要があります。
事前生成は簡単です。最初から最後まで000000進み、zzzzzz各行をテーブルに挿入して、未使用のマークを付けます。
ID | used
==============
000000 0
000001 0
...
zzzzzz 0
新しいIDのリクエストを受け取ったら、ランダムなIDを選択し、使用済みとしてマークします（危険！同時実行の問題！）：
SELECT ID FROM ids WHERE RAND() LIMIT 1
UPDATE ids SET used = 1, url=what_you_want_shortened WHERE ID = whatever_you_got_from_previous_query
効率の問題（たとえばWHERE RAND()、テーブルのロックなど）に遭遇しますが、それは実行可能です。
.NET dllを持ち込むことを嫌がらないのであれば、私はこれを正確に行うためのプロジェクトを作成しました。ソースはここのGitHubにあり、バイナリはIdGeneratorNuGetパッケージにあります。
順序付けられたシーケンスおよび/またはユーザー指定の長さのランダムな値をすべてbase-36で提供します。IDは、複数のIDジェネレーターインスタンスがある場合や分散環境であっても、普遍的に一意です。
var generator = new Base36IdGenerator(
numTimestampCharacters: 11,
numServerCharacters: 4,
numRandomCharacters: 5,
reservedValue: "",
delimiter: "-",
delimiterPositions: new[] {15, 10, 5});
// This instance would give you a 20-character Id, with an
// 11-character timestamp, 4-character servername hash,
// and 5 character random sequence. This gives you 1.6 million
// hash combinations for the server component, and 60 million
// possible combinations for the random sequence. Timestamp is
// microseconds since epoch:
Console.WriteLine(generator.NewId());
// 040VZC6SL01003BZ00R2
// Argument name specified for readability only:
Console.WriteLine(generator.NewId(delimited: true));
// 040VZ-C6SL0-1003B-Z00R2
もちろん、順序付けられたシーケンスを持つよりも文字列が推測できないことに関心がある場合は、GetRandomStringメソッドを使用できます。
// 6-characters give you a little over 2 billion possible
// combinations (36 ^ 6). 7 characters is about 78 billion.
Console.WriteLine(generator.GetRandomString(length: 6));
その背後にある基本原則は次のとおりです。
0パッドを希望の長さに残しますBase36エンコーダー自体はhttp://www.stum.de/2008/10/20/base36-encoderdecoder-in-c/からのものです。