ハッシュと比較と検索
404 Blog Not Found:tips - MD5のコスト
ソースはちゃんと見ていないのだが,メモリに載るならハッシュを使って検索した方が速いのでは?
読み終わった.早とちりしてた.一つ一つファイルを検索して消すのかと思ってた.
重複を消すために追加データをファイルリストから検索をしているのではなく,追加データも含めてファイルリストをハッシュ値でソートして隣り合うデータを比較している.ハッシュ値はキャッシュして保存しているので毎回計算する必要はない.削除するときにハッシュ値だけでなくデータの比較も行っているのでコリジョンで間違って消すことはないっぽい.
ので,隣り合うデータが異なる場合はハッシュ値の比較のみなのでそれだけ速くなる.あと,ソートの部分もハッシュの方が速いだろう.逆に新たに入力されるデータはあたらしくハッシュ値を計算しなければいけないので,その分遅くなる.データの更新数が多いほど遅くなって,もともとあるファイルリストが多いほど速くなるということか.