hash - GUID のハッシュは一意ですか?

Question

GUID を (文字列として) 作成し、そのハッシュを取得します。このハッシュは一意であると見なすことができますか?

score 22 · Accepted Answer

GUID自体ほど確実に一意ではありません。

拡大すると、一意性が 4 分の 1 に減少し、16 バイトから 4 バイトの可能な組み合わせになります。

コメントで指摘されているように、ハッシュサイズによって違いが生じます。4 バイトということは、既定のハッシュサイズが 4 バイト (int) である .NET で使用される可能性があるという前提でした。したがって、上記の内容をハッシュのバイトサイズに置き換えることができます。

score 10 · Accepted Answer

いいえ。

ミニ GUID が必要な場合は、こちらを参照してください: https://devblogs.microsoft.com/oldnewthing/20080627-00/?p=21823

score 8 · Accepted Answer

一言で言えば、いいえ。

ハッシュのビット数が GUID よりも少ないと仮定しましょう。ピジョンホールの原則により、GUID よりもハッシュが少ないという理由だけで、いくつかの GUID -> ハッシュの複数のマッピングが存在する必要があります。

ハッシュが GUID よりも多くのビット数を持っていると仮定すると、適切なハッシュ関数を使用していると仮定すると、衝突の可能性は非常に小さいですが有限です。

score 4 · Accepted Answer

任意のサイズのデータブロックを固定サイズのビット数に縮小するハッシュ関数は、2 つの間で 1 対 1 のマッピングを生成しません。2 つの異なるデータブロックがハッシュ内の同じビットシーケンスに縮小される可能性は常に存在します。

優れたハッシュアルゴリズムは、このような事態が発生する可能性を最小限に抑えます。一般に、ハッシュのビット数が多いほど、衝突の可能性は低くなります。

score 2 · Accepted Answer

ハッシュ衝突のため、保証されていません。GUID 自体はほぼ保証されています。

実際的な理由から、おそらくハッシュは一意であると想定できますが、GUID 自体を使用しないのはなぜでしょうか?

score 2 · Accepted Answer

いいえ、ハッシュ値の一意性は想定していません。ハッシュ値は一意である必要はなく、範囲全体に均等に分散する必要があるだけなので、それは問題ではありません。分布が均一であるほど、(ハッシュテーブルで) 発生する衝突は少なくなります。衝突が少ないほど、ハッシュテーブルのパフォーマンスが向上します。

score 0 · Accepted Answer

暗号化ハッシュ (MD5、SHA1、RIPEMD160) を使用する場合、ハッシュは一意になります (非常にありそうもないモジュロ衝突 -- SHA1 はデジタル署名などに使用され、MD5 はランダムな入力に対しても衝突耐性があります)。しかし、なぜ GUID をハッシュしたいのでしょうか?

7 に答える 7