IDの固有のランダム生成のための良いアルゴリズム

Question

ショートリンクサービスのIDとして、任意のID（英数字、6文字）を生成する必要があります。

現在、ランダムな6文字のコードを生成し、dbで検索して以前に使用されていたかどうかを調べ、もしあれば、その処理を繰り返します。私はすべての36^6の組み合わせで一意にする必要があります。システムが成長するにつれて、パフォーマンスは悪化します。

dbを打つのを最小限に抑え、グローバルに状態を保持し、ルックアップに100ms以上かかることはありません。任意の助け

Thxを

Answer 1

LCGで次の乱数を生成し、それを基数36に変換して、対応する疑似乱数列を書き込みます。

幸運を祈る！

Answer 2

使用連続番号、あなたはキーが既に存在するかどうかを検索するデータベースをヒットする必要はありませんので。今まで割り当てられた最大数を追跡するだけで済みます。

あなたが割り当てられた最初のIDは、その後000000、000001のように見えるだろうという事実を好きではない場合は36

をベースに、それを変換し、この順次IDの英数字を作るために、... 00000z、000010、。 ..、あなたは数学的なトリックを利用することができます：内部的には連続した数値IDを保持しますが、ユーザが見ることができる外部表現に対しては、それを36^6-1より小さい大きな素数で（mod 36^6） 1679979167は適切な選択です - ベース36に変換する前に。これはあなたのIDが実際にはなくてもランダムに表示されるようにします。

ここで出力のPythonサンプルです：

http://en.wikipedia.org/wiki/Linear_congruential_generator：この問題はよく知られているソリューションを有する

def baseN(num,b,numerals="abcdefghijklmnopqrstuvwxyz"): 
    return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b]) 

for internalID in range(1,200): 
    mangled = (internalID*1679979167)%(36**6) 
    print internalID, mangled, baseN(mangled,36) 

（ベイスンコードはhereからjellyfishtreeだ場合）

---

1 1679979167 rs7s7z 
2 1183175998 jkfkfy 
3 686372829 bcncnx 
4 189569660 34v4vw 
5 1869548827 ux2x3v 
6 1372745658 mpapbu 
7 875942489 ehihjt 
8 379139320 69q9rs 
9 2059118487 y1y1zr 
10 1562315318 pu5u7q 
11 1065512149 hmdmfp 
12 568708980 9eleno