问题标签 [integer-hashing]

简单地说，这就是我想要做的：

我有一组Range连续的对象（不重叠，它们之间没有间隙），每个对象都包含一个start和endint，以及对另一个对象的引用obj。这些范围不是固定大小的（第一个可以是 1-49，第二个可以是 50-221，等等）。这个集合可能会变得非常大。

我希望找到一种方法来查找包含给定数字的范围（或更具体地说，它引用的对象），而不必遍历整个集合来检查每个范围以查看它是否包含数字。这些查找将经常执行，因此速度/性能是关键。

有谁知道可能在这里帮助我的算法/方程？我正在用 Java 编写。如果需要，我可以提供更多细节，但我想我会尽量保持简单。

谢谢。

背景

我在 OpenGL 渲染管道的一个阶段中使用了一个小型静态哈希表（线性探测），我必须尽可能快地检索和更新 int64_t 类型的键和一些数据。简而言之，这个阶段是关于将大 ID 转换为后续阶段使用的小本地索引（所以在这个阶段我需要处理一次 64 位密钥，并且不能使用 32 位密钥）。

我已经尝试了很长时间，以找到一个在 32 位和 64 位 arm 架构（iOS 和 Android 智能手机）上都能快速运行的哈希函数。自然，在 32 位设备上散列 64 位密钥比散列 32 位密钥慢得多（在我的测试用例中几乎是 10 次）。

我现在对我在 SO 上找到的哈希非常有信心，它在我的情况下优于 MurmurHash3 32 位终结器（有更多的碰撞，但在我的情况下并不重要）： https ://stackoverflow.com/a /12996028/1708349

现在一切都很好，但这里有一个问题：我天真地将 64 位密钥分配给 int32_t 类型，然后再对其进行散列 - 这是出于 32 位平台的性能原因。这似乎可行，大数据被包裹起来。但是问题当然是没有定义这种行为。

所以，我的问题是：将 int64_t 类型分配给 int32_t 类型的最佳（例如定义的编译器行为）是什么，所以它会环绕 - 例如不只是分配 64 位 int 的低 32 位？

这是我的实际哈希函数：

我正在阅读有关整数的通用散列。前提和强制性前提似乎是我们选择的质数p大于所有可能键的集合。

我不清楚这一点。

如果我们的键集是类型，int那么这意味着质数需要是下一个更大的数据类型，例如long。

但最终我们得到的任何哈希值都需要向下转换为 int 来索引哈希表。这种向下转换不会以某种方式影响通用哈希的质量（我指的是密钥在桶上的分布）吗？

在哈希图中，如何以下面的形式给出整数 repersentation.我试过但我无法得到解决方案。

(1,2)=17；

给定一个数字列表，例如一些唯一的整数或长 ID，计算可重现的“签名”（最好不考虑元素顺序）的最佳方法是什么？

用例是检测是否从（对象）列表中添加或删除了任何 ID。

Javaarray.hashCode()不符合要求，因为即使它在 JVM 调用之间显然是一致的，如果元素的顺序发生变化或创建具有相同元素的另一个实例，它也会返回不同的哈希：

我的理解是ids1.hashCode()计算数组内存地址的哈希值，而不是数组中原始元素的累积哈希码。

除了单独散列每个元素之外，在这种情况下还可以使用哪些其他方法？