文字列に連結されたファイル名のリストを並べ替えましたが、一意のチェックサムによってそのような文字列をそれぞれ識別したいと考えています。
これらの文字列のサイズは、最小 100 バイト、最大 4000 バイト、平均 1000 バイトです。文字列の総数はいくらでもかまいませんが、約 . 10000。
CRC-32 はこの目的に適していますか?
たとえば、次の文字列のそれぞれに異なる固定長 (できれば短い) チェックサムが必要です。
"/some/path/to/something/some/other/path"
"/some/path/to/something/another/path"
"/some/path"
...
# these strings can get __very__ long (very long strings are the norm)
CRC-32 ハッシュの一意性は入力長によって増加しますか?
この目的のためのチェックサムのより良い選択はありますか?
いいえ。
ファイル名がすべて 4 文字以下でない限り、CRC が一意であるという保証はありません。10,000 個の名前がある場合、そのうちの少なくとも 2 つが同じ CRC を持つ確率は約 1% です。
これは、任意の 32 ビット ハッシュ値に当てはまります。
各名前に一意のコードを割り当てる最良の方法は、最初の名前のカウンターをゼロから開始し、名前ごとにインクリメントして、カウンターをその名前のコードとして割り当てることです。ただし、名前だけでコードを計算するのには役立ちません。
CRC やその他のハッシュなどのハッシュを使用できますが、衝突に対処する必要があります。文献にはいくつかの一般的なアプローチがあります。名前が割り当てられたハッシュのリストを保持し、衝突が発生した場合は、使用されていないものが見つかるまでハッシュをインクリメントして、それを割り当てることができます。次に、名前を検索するときは、計算されたハッシュから開始し、名前または未使用のスロットが見つかるまで名前の線形検索を行います。
ハッシュについては、XXH64をお勧めします。これは非常に高速な 64 ビット ハッシュです。このアプリケーションには、不必要に遅くなる暗号化ハッシュは必要ありません。