一意（ユニーク）かつ、ソートに対してランダムなIDの発行方法

質問

随時増加するあるデータに対して、一意なIDを割り当ててゆきます。
通常は、1, 2, 3, … と連番を割り当てて行けば一意なIDになると思います。
その上で、IDでソートした時に発行順に並ぶのではなく、順番がランダムになるようにしたいのです。
（アルゴリズムを知らない人から、発行順を推測されないようにしたい。）

そこで考えたのが、"1", "2", "3", …という文字列に対するハッシュ（SHA1やMD5）ですが、sha1("1"), sha1("2"), sha1("3"), …とIDを発行していった場合、IDが重複してしまう可能性を心配しています。（とても低い確率ではあることは分かっていますが、皆無ではありません。）

ハッシュ関数を利用する他に、「一意」で「ランダム」で「衝突の可能性がゼロ」である文字列の生成方法はありませんでしょうか？（可能性がゼロというのは物理的に不可能だと思うので、例えばSHA-1であれば、160bitのハッシュが生成されますが、2^160個のIDを発行しても重複しない、ということを考えます。）

一応、規模は1000万ID程度を考えていますが、もっと大きなオーダーでも衝突しないに越したことはありません。

回答No.3

alioth

> 「一意」で「ランダム」で「衝突の可能性がゼロ」である文字列の生成方法はありませんでしょうか？
１．ランダムな文字列を作る
２．if (そのＩＤは発行済み) then １に戻る
で、何か問題でも？

お礼

ご回答ありがとうございます。

この方法は、IDを発行するにつれて処理が重くなってしまうという欠点があると思います。
重複の可能性が高くなるとともに、重複しているかどうかチェックする対象も増えるわけなので。

この方法でも実現可能ですが、もっとスマートな方法があれば、と思い質問させて頂きました。

回答No.2

noname#39970

一意の連番をハッシュ　の後に　タイムナンバー(PCが規定の日時からどれくらい経過してるかを表してる方の。ミリ秒以上の精度で取れるのが望ましい)を桁揃えして付加。
後ろに付ける、というのがミソ(ソートだから前に付けると発行順になってしまう)

あるいは似た考えで一意の番号とタイムナンバーをそれぞれハッシュにかけてくっつける
一連の番号を管理するのが面倒なら　タイムナンバーだけ使って前者の細工をしても良さそう

お礼

ご回答ありがとうございます。
御礼が遅くなりまして、失礼致しました。

この方法でも実現可能ですね。ただ、タイムナンバーを生で末尾につけてしまうと、
確かにソートに対してはランダムになりますが、発行順を推測することが容易です。
また、hash(連番) + hash(タイムナンバー) であっても、（さらに確率は低くなりますが）
重複の可能性が0ではありません。

回答No.1

BLUEPIXY

０）ＤＢに１０００万個のＩＤを準備する（適当な連番でＯＫ）

１）ＤＢの件数を問い合わせる
２）件数からその範囲の乱数を求める
３）求まった番目のデータを取り出しＩＤとして発行する。
４）発行したＩＤのデータを削除する
５）手順１に戻る

お礼

ご回答ありがとうございます。
御礼が遅くなりまして、失礼致しました。

確かにこの方法で実現可能ですね。ひとまずOKだとは思うのですが、
もう少しスマートな方法があれば、と思い質問いたしました。
万一1000万を超えてしまった時の処理も大変そうです。