2 つの文字列が同一かどうかをできるだけ早く確認しようとしています。文字列全体を比較せずに、ハッシュの衝突から身を守ることはできますか?
文字列をキーとするアイテムのキャッシュがあります。文字列のハッシュ、文字列の長さ、および文字列自体を保存します。(現在、djb2を使用してハッシュを生成しています。)
入力文字列がキャッシュ内のアイテムと一致するかどうかを確認するために、入力のハッシュを計算し、それを格納されているハッシュと比較します。それが一致する場合、入力の長さ (ハッシュ計算の副作用として取得したもの) を格納されている長さと比較します。最後に、一致する場合は、入力と格納された文字列の完全な文字列比較を行います。
その完全な文字列比較を行う必要がありますか? たとえば、同じ長さの 2 つの文字列が同じハッシュを生成しないことを数学的に保証できる文字列ハッシュ アルゴリズムはありますか? そうでない場合、アルゴリズムは、最初の N 文字のいずれかが異なる場合、同じ長さの 2 つの異なる文字列が異なるハッシュ コードを生成することを保証できますか?
基本的に、文字列が異なる場合は O(1) のパフォーマンスを提供するが、一致する場合は O(n) のパフォーマンスよりも優れた文字列比較スキームは、私が現在行っていることよりも改善されます。