34

まず第一に、再ハッシュは賢明なトピックであるという事実を認識していることを保証したいと思います。ただし、ここでどのようなアプローチをとるか、いくつかの意見をお聞きしたいと思います。

ノードがUUIDで識別されるエンティティをリモートで作成する分散アプリケーションを構築しています。最終的に、すべてのエンティティは、これらの UUID を使用してすべてのエンティティを格納する専用のドレイン ノードに収集される必要があります。

ここで、人間のユーザーにとってより便利な追加の識別子を作成したいと思います。UUID を Base64 でエンコードしても 22 文字の ID が作成されるため、人間の使用には適していません。だから、URL短縮サービスのようなものが必要です。全単射関数を適用しても、情報の価値が低下しないため、役に立ちません。もちろん、ID を短くするために情報を失う必要があることは承知しています。また、ハッシュの情報を減らすと、衝突の可能性が高くなることも認識しています。人間の短いIDを作成するために情報を減らす最も適切な方法は何ですか?

ここにいくつかの前提条件があります: データ ストレージを介して {UUID, 短縮 ID} をマップする機能を提供します。私はまだ非集中型のソリューションを好むでしょう。合計で約 100 万 (~2^20) を超える ID が必要になることはおそらくないでしょう。

これまでに私が思いついた考えは次のとおりです。

  • 自動インクリメント ID: 自動インクリメント IDを使用する場合、この ID を難読化された文字列に転送して渡すことができます。これが最も簡単な方法です。キーがほとんどない限り、キーはそれほど長くはありません。ただし、私が本当に望んでいない中央集権型のエンティティを導入する必要があります。
  • UUID を短くする:元の 128 ビット uuid のビットの一部を使用できます。次に、少なくとも UUID のバージョンを考慮する必要があります。または、これには他に何か問題がありますか？
  • UUID の再ハッシュ:最初の UUID に 2 番目のハッシュ アルゴリズムを適用し、マッピングを保存できます。

他のアプローチはありますか？有利とは？

前もって感謝します！

4

4 に答える 4

27

1）UUIDを短くするには、上半分と下半分をXORするだけです（十分に短くなるまで繰り返します）。これにより、分布特性が保持されます。出力を短くする他のソリューションと同様に、誕生日のパラドックスによる衝突の可能性が高くなります

2) XOR は些細なハッシュになりますが、追加のミキシングは必要ないため問題ありません。UUID に CRC または非暗号化ハッシュを使用することもできますが、それで改善されるとは思えません。

3)中央管理を受け入れても構わないと思っているなら、それは苦痛である必要はありません。中央機関は中サイズのアドレス空間ブロックを各クライアントに分配でき、クライアントは ID を割り当てるときにそのサブレンジを繰り返し処理できます。これにより、衝突がないことが保証されますが、各 ID の往復も回避されます。これを行う 1 つの方法は、ID に 32 ビット整数を使用し、一度に 16 ビット ブロックを分配することです。つまり、最初のクライアントには 0001 が渡され、これにより 00010000 から 0001FFFF までが許可されます。

4) UUID を使用してデータベースに挿入できますが、ID フィールドもあります。これにより、代替のよりコンパクトな一意の ID が提供され、32 ビットの int に制限できます。

于 2010-02-12T18:05:36.510 に答える
4

頭に浮かぶいくつかのこと：

あなたのユースケースは何ですか？分散方式で ID を生成することに懸念がある場合、1 つの解決策は、各マシンに独自の一意の int ID を割り当て、それを ID のプレフィックスまたはサフィックスとして使用することです。

中央エンティティを持たないことで、ローカルでも ID を追跡する意味がない場合、これは実際には役に立ちません。UUID 自体からページを借りて、上記のように割り当てられたマシン ID と組み合わせてシステム時間を使用できます。これにより、64 ビット + マシン ID のサイズに制限されます。基本的に、これは UUID V1 スキームですが、マシン ID に MAC アドレスよりも短いものを使用しています。2010 年 2 月 12 日以降の日付から開始できることがわかっている場合は、さらに短縮できる可能性があります。

ウィキペディアの UUID エントリをまだチェックしていない場合はチェックしてください。独自の UUID エントリを作成する方法について、そこから 1 つまたは 2 つのアイデアが得られるかもしれません。

于 2010-02-12T18:17:30.443 に答える
1

これが私が書いた簡単なハッシュアルゴリズムです。これを使用できます...読みやすさと衝突の可能性をトレードオフするために、入力と出力のマッピング、およびハッシュの長さを簡単に変更できます。

このアルゴリズムは、安全または効率的に設計されていませんが、うまくいくはずです。

public class HashTools {

  final static String inputMapping = "0123456789ABCDEF";

  final static String[] outputMapping = new String[] {
      "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
      "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"
  };

  /* Input: String - containing mostly letters / numbers
   * Output: <hashLength> String using 0-9,A-Z encoding
   */
  public static String simpleHash(String str, int hashLength) {
    StringBuilder hashStr = new StringBuilder(hashLength);
    String strUpper = str.toUpperCase();
    int[] hash = new int[hashLength];

    int i, j, num;
    for (i = 0; i < strUpper.length(); i++) {
      char strChar = strUpper.charAt(i);
      num = mapCharToInt(strChar);

      j = i % hashLength;
      hash[j] += num;
    }

    for (i = 0; i < hashLength; i++) {
      hashStr.append(mapIntToHashChar(hash[i]));
    }

    return hashStr.toString();
  }

  private static int mapCharToInt(char hexChar) {
    return inputMapping.indexOf(hexChar);
  }

  private static String mapIntToHashChar(int num) {
    return outputMapping[num % outputMapping.length];
  }
}
于 2012-09-01T14:16:33.637 に答える