問題タブ [integer-hashing]

簡単に言えば、これが私がやろうとしていることです：

私は連続しているオブジェクトのコレクションを持っていRangeます (重なり合っておらず、それらの間にギャップはありません)。それぞれに astartとendint が含まれており、別の object への参照が含まれていますobj。これらの範囲は固定サイズではありません (最初の範囲は 1 ～ 49、2 番目の範囲は 50 ～ 221 など)。このコレクションは非常に大きくなる可能性があります。

コレクション全体を反復処理して各範囲に番号が含まれているかどうかを確認することなく、特定の番号を含む範囲 (より具体的には、それが参照するオブジェクト) を検索する方法を見つけたいと考えています。これらのルックアップは頻繁に実行されるため、速度/パフォーマンスが重要です。

ここで私を助けるかもしれないアルゴリズム/方程式を知っている人はいますか? 私はJavaで書いています。必要に応じて詳細を提供することもできますが、シンプルにしようと思いました。

ありがとう。

バックグラウンド

私は、OpenGL レンダリング パイプラインの段階で必要な小さな静的ハッシュ テーブル (線形プローブ) を使用します。そこでは、int64_t 型のキーといくつかのデータをできるだけ速く取得して更新する必要があります。要するに、この段階では、大きな ID を、後続の段階で使用する小さなローカル インデックスに変換します (したがって、この段階では、64 ビット キーを 1 回処理する必要があり、32 ビット キーは使用できません)。

私は、32 ビットと 64 ビットの両方のアーム アーキテクチャ (iOS と Android スマートフォン) で高速に動作するハッシュ関数を見つけるために、長い間実験してきました。当然のことながら、32 ビット デバイスでは、64 ビット キーのハッシュは 32 ビット キーのハッシュよりもはるかに遅くなります (私のテスト ケースではほぼ 10 倍)。

SOでここで見つけたハッシュに非常に自信を持っています。これは、私の場合、MurmurHash3 32ビットファイナライザーよりも優れています(さらに衝突がありますが、私の場合は問題ではありません): https://stackoverflow.com/a /12996028/1708349

今のところすべて正常に動作しますが、ここに問題があります。ハッシュ化する前に、64 ビット キーを単純に int32_t 型に割り当てます。これは、32 ビット プラットフォームのパフォーマンス上の理由から行われます。これは機能しているようで、大きなデータがラップされています。しかし、問題はもちろん、この動作が定義されていないことです。

だから、私の質問は次のとおりです: int64_t 型を int32_t 型に割り当てるのに最適なもの (定義されたコンパイラの動作など) は何ですか?

これは私の実際のハッシュ関数です:

ハッシュマップでは、以下の形式で整数を与える方法 repersentation.i を試しましたが、解決策が得られません。

(1,2)=17;

たとえば、一意の整数または長い ID などの数値のリストが与えられた場合、再現可能な「署名」を計算する最適な方法は何でしょうか (できれば要素の順序に関係なく)。

使用例は、ID のいずれかが (オブジェクトの) リストに追加または削除されたかどうかを検出することです。

Javaarray.hashCode()は、JVM 呼び出し間で一貫しているように見えても、要素の順序が変更されたり、同じ要素を持つ別のインスタンスが作成されたりすると、異なるハッシュを返すため、法案に適合しません。

私の理解では、配列内のプリミティブ要素の累積ハッシュ コードではなくids1.hashCode()、配列のメモリ アドレスのハッシュを計算します。

この場合、各要素を個別にハッシュする以外に、他にどのようなアプローチを使用できますか?