0

背景: オブジェクトの 2 つの配列があり、これら 2 つの配列が同じかどうかを知りたいです。すべてのオブジェクトの md5 を計算し、それらを合計して 1 つの比較を行うことはできますか?

基本的に、md5(a)=md5(b) を知っていれば、実質的に a=b

しかし、md5(a) + md5(b) = md5(c) + md5(d) がわかれば、a=c および b=d と言えますか?

4

1 に答える 1

1

オブジェクトの 2 つの配列があり、これら 2 つの配列が同じかどうかを知りたいです。すべてのオブジェクトの md5 を計算し、それらを合計して 1 つの比較を行うことはできますか?

これは最適化ですか？

配列が 2 つしかない場合、メモリ ブロックのハッシュの計算は O(n) 操作であるため、このメリットはありません。配列を 1 回比較する場合は、単に長さと各要素を比較する単純なアプローチの方が高速です。

しかし、md5(a) + md5(b) = md5(c) + md5(d) がわかれば、a=c かつ b=d と言えますか?

いいえ。膨大な数のケースを排除するための迅速な方法が必要な場合は、最初の推測としてそれを使用することがa == cできb == dます。ただし、確実ではありません。md5 チェックは成功するが、配列が等しくない状況が存在します。このチェックに頼る場合は、そのような誤検出を確実に排除する必要があります。md5(a) == md5(c)md5(b) == md5(d)

また、和を取ると順番は関係なくなります。言い換えれば、合計が等しい可能性があるいくつかの異なる状況になります。

  • a == cそしてb == d（予想）
  • a == dおよびb == c(値が交換されます)
  • a != cand a != dand b != cand b != d(偶然の偽陽性)

このヒューリスティックを有効にするには、これらすべてを考慮する必要があります。

于 2012-10-24T19:06:39.320 に答える