1

最近、個人用 URL 短縮用のドメインを購入しました。そして、リファレンスとして4文字の英数字文字列を生成する関数を作成しました。

しかし

それらがすでに使用されているかどうかを確認するにはどうすればよいですか? すべての URL がデータベースに存在するかどうかを確認することはできません。もしそうなら、(14.776.336 から) 13.000.000 個の URL が生成されたとしたらどうなるでしょうか。DB にまだ存在しない文字列が見つかるまで、文字列を生成し続ける必要がありますか?

これは正しい方法ではないように見えますが、アドバイスをくれる人はいますか?

4

3 に答える 3

3

私が考える1つのメモリ効率的で高速な方法は次のとおりです。この問題は、データベースをまったく使用せずに解決できます。使用済みのURLをデータベースに保存する代わりに、メモリに保存できるという考え方です。また、それらをメモリに格納すると多くのメモリ使用量がかかる可能性があるため、ビットセット（ビットの配列）を使用し、URLごとに1ビットのみを使用します。

  1. 生成するランダムな文字列ごとに、b /w0と最大数Kにあるハッシュコードを作成します。
  2. ビットセット（基本的にはビット配列）を作成します。URLを使用する場合は常に、対応するハッシュコードビットを1に設定してください。
  3. 新しいURLを生成するときはいつでも、そのハッシュコードビットが設定されているかどうかを確認してください。はいの場合は、そのURLを破棄して、新しいURLを生成します。未使用のものが1つ得られるまで、このプロセスを繰り返します。

このようにして、DBを永久に回避し、ルックアップは非常に高速で、必要なメモリ量は最小限に抑えられます。

この場所からアイデアを借りました

于 2012-04-19T12:28:05.800 に答える
0

妥協案は、ランダムIDを生成し、それがすでにデータベースにある場合は、それよりも大きい最初の空のIDを見つけることです。（上記の範囲に空きスペースが見つからない場合は、折り返します。）

IDを推測できないようにしたくない場合（4文字しか使用しない場合はおそらくそうしないでしょう）、このアプローチは問題なく機能し、迅速です。

于 2012-04-19T12:27:16.277 に答える
0

アルゴリズムの 1 つは、N 文字の空き URL を見つけるために数回試行することです。それでも見つからない場合は、N を増やします。N=4 から始めます。

于 2012-04-19T15:43:56.543 に答える