171

このページを読みましたが、何のためにあるのmanかわかりません。namenamespace

バージョン3およびバージョン5のUUIDの場合、追加のコマンドライン引数の名前空間と名前を指定する必要があります。名前空間は、文字列表現のUUIDか、内部で事前定義された名前空間UUIDの識別子です(現在、「ns:DNS」、「ns:URL」、「ns:OID」、および「ns:X500」として知られています)。名前は任意の長さの文字列です。

名前空間:

名前空間は、文字列表現のUUIDまたは

生成されたUUIDv5に関連してどこかにそれ(UUID v4)を保存する必要があるということですか?どちらの場合でも、なぜこれが自動的に行われないのですか?

名前は任意の長さの文字列です。

name完全にランダムな文字列?それでは、その目的は何ですか?UUID v5からデコードできますか?

4

3 に答える 3

282

タイプ 3 およびタイプ 5 の UUID は、ハッシュを UUIDに詰め込む手法にすぎません。

  • タイプ 1MAC address : +datetimeを 128 ビットに詰め込む
  • タイプ 3MD5 hash : anを 128 ビットに詰め込む
  • タイプ 4random data : 128 ビットに詰め込む
  • タイプ 5SHA1 :ハッシュを 128 ビットに詰め込む
  • タイプ 6 :シーケンシャル UUID の非公式なアイデア

編集:非公式のタイプ6には公式のrfcがあります

SHA1 ハッシュは 160 ビット (20 バイト) を出力します。ハッシュの結果は UUID に変換されます。

SHA1 からの 20 バイトのダイジェストを使用:

SHA1 Digest:   74738ff5 5367 e958 1aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ⭡    ⬑first two bits set to 1 and 0, respectively
                             ╰─low nibble is set to 5, to indicate type 5

何をハッシュしますか?

あなたはおそらく、私が何をハッシュすることになっているのか疑問に思っているでしょう. 基本的に、次の連結をハッシュします。

sha1( NamespaceUUID+ AnyString);

名前の競合を防ぐために、文字列の前にいわゆる名前空間を付けます。

UUID RFCでは、次の4 つの名前空間が事前に定義されています。

  • NameSpace_DNS: {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_URL: {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_OID: {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_X500:{6ba7b814-9dad-11d1-80b4-00c04fd430c8}

したがって、一緒にハッシュすることができます:

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com");
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com");

次に、RFC は次の方法を定義します。

  • SHA1 から 160 ビットを取得します
  • それを128ビットのUUIDに変換します

基本的な要点は、最初の 128 ビットのみを取得5し、タイプレコードに a を詰め込み、clock_seq_hi_and_reservedセクションの最初の 2 ビットをそれぞれ 1 と 0 に設定することです。

その他の例

いわゆるNameを生成する関数ができたので、関数を (疑似コードで) 持つことができます。

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    //Note: All code on stackoverflow is public domain - no attribution required.

    Byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    Uuid result;

    //Copy first 16-bytes of the hash into our Uuid result
    Copy(hash, result, 16);

    //set high-nibble to 5 to indicate type 5
    result[6] &= 0x0F; 
    result[6] |= 0x50; 

    //set upper two bits to "10"
    result[8] &= 0x3F; 
    result[8] |= 0x80; 

    return result;
}

(注: システムのエンディアンは、上記のバイトのインデックスに影響を与える可能性があります)

これで、電話をかけることができます:

uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com');
uuid = NameToUUID(Namespace_DNS, 'www.google.com');
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com');
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112');
uuid = NameToUUID(Namespace_URL, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm');

さて、あなたの質問に戻ります

バージョン 3 およびバージョン 5 の UUID の場合、追加のコマンド ライン引数の名前空間と名前を指定する必要があります。名前空間は、文字列表現の UUID か、内部で事前定義された名前空間 UUID の識別子です (現在知られているのは、"ns:DNS"、"ns:URL"、"ns:OID"、および "ns:X500" です)。名前は任意の長さの文字列です。

名前空間は任意の UUID です。事前定義されたものの1つにすることも、独自のものを作成することもできます。たとえば、1 :

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

名前は任意の長さの文字列です。

名前は、名前空間に追加し、ハッシュして UUID に詰め込みたいテキストです。

uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch');
于 2015-02-28T01:04:47.450 に答える
133

名前と名前空間を使用して、(おそらく) 一意の UUID の階層を作成できます。

大まかに言えば、タイプ 3 またはタイプ 5 の UUID は、名前空間識別子と名前を一緒にハッシュすることによって生成されます。タイプ 3 UUID は MD5 を使用し、タイプ 5 UUID は SHA1 を使用します。利用できるのは 128 ビットのみで、タイプの指定には 5 ビットが使用されるため、すべてのハッシュ ビットが UUID になるわけではありません。(また、MD5 は暗号的に壊れていると見なされ、SHA1 は最後の手段にあるため、「非常に安全」である必要があるデータを検証するためにこれを使用しないでください)。とは言うものの、階層的な名前を確率的に一意の 128 ビット値にマッピングし、階層的なハッシュまたは MAC のように機能する可能性がある、反復可能/検証可能な「ハッシュ」関数を作成する方法を提供します。

(キー、値) ストアがあるとしますが、サポートされる名前空間は 1 つだけです。タイプ 3 またはタイプ 5 の UUID を使用して、多数の個別の論理名前空間を生成できます。まず、名前空間ごとにルート UUID を作成します。これは、どこかに隠しておく限り、タイプ 1 (ホスト + タイムスタンプ) またはタイプ 4 (ランダム) UUID の可能性があります。別の方法として、ルート用に1 つのランダムな UUID を作成 (またはnullUUID:00000000-0000-0000-0000-000000000000をルートとして使用) し、" " を使用して名前空間ごとに再現可能な UUID を作成することもできますuuid -v5 $ROOTUUID $NAMESPACENAME。「uuid -v5 $NAMESPACEUUID $KEYこれらの UUID は、衝突を回避する可能性が高い単一のキー値ストアにスローできます。このプロセスを再帰的に繰り返すことができるため、たとえば、UUID キーに関連付けられた「値」が何らかの論理的な「名前空間」を表す場合" バケット、コンテナ、またはディレクトリのように、その UUID を使用してさらに階層的な UUID を生成できます。

生成されたタイプ 3 またはタイプ 5 の UUID は、名前空間 ID と名前空間内の名前 (キー) の (部分的な) ハッシュを保持します。メッセージ MAC がエンコード元のメッセージの内容を保持するのと同様に、名前空間 UUID を保持することはありません。この名前は、uuid アルゴリズムの観点からは「任意の」(オクテット) 文字列です。ただし、その意味はアプリケーションによって異なります。論理ディレクトリ内のファイル名、オブジェクト ストア内のオブジェクト ID などです。

これは、適度に多数の名前空間とキーに対してはうまく機能しますが、非常に高い確率で一意である非常に多数のキーを目指している場合、最終的には力を使い果たしてしまいます。誕生日問題 (別名誕生日パラドックス) のウィキペディアのエントリには、さまざまな数のキーとテーブル サイズについて、少なくとも 1 回の衝突の確率を示すテーブルが含まれています。128 ビットの場合、この方法で 260 億のキーをハッシュするとp=10^-18(無視できる) 衝突の確率がありますが、26 兆のキーでは、少なくとも 1 回の衝突の確率が(1 兆分の 1)に増加し、キーのp=10^-12ハッシュにより、次の確率が増加します。26*10^15への少なくとも 1 つの衝突p=10^-6(100万人に一人)。UUID タイプをエンコードする 5 ビットに合わせて調整すると、いくらか早く使い果たされるため、1 兆個のキーが 1 兆分の 1 の確率で 1 回衝突します。

確率表については、http://en.wikipedia.org/wiki/Birthday_problem#Probability_tableを参照してください。

UUID エンコーディングの詳細については、http://www.ietf.org/rfc/rfc4122.txtを参照してください。

于 2013-03-13T19:55:55.677 に答える