标签: integer-hashing

我想散列一组整数,使得整数的顺序对计算的散列值没有影响.即H([32224,12232,564423]) == H([564423,32224,12232]).

唯一集的数量将在几百万的范围内.速度非常重要,但我需要通过选择的方法知道碰撞的上限.

维基百科有一个很好的关于散列向量的部分,但我不明白它背后的数学是在代码中自信地实现它们.如果有人能解释一些代码涉及的数学,我将不胜感激.理想情况下,我希望最终的哈希值为32位.如果它有用 - 我将用Java实现它.

更新:由于性能原因(在许多此类集上运行),我特别希望避免对集合中的整数进行排序.

我正在阅读关于整数的Universal散列.该先决条件和强制性先决条件似乎是我们选择一个素数p大于设定的所有可能的密钥更大.

我不清楚这一点.

如果我们的密钥集是类型,int那么这意味着素数需要是下一个更大的数据类型,例如long.

但最终无论我们得到什么,因为哈希需要下载到一个int来索引哈希表.这种降级是否会以某种方式影响Universal Hashing的质量(我指的是桶上的密钥分配)？

所以简单地说,这就是我想要做的:

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

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

有谁知道可能帮助我的算法/方程？我是用Java写的.如果需要,我可以提供更多细节,但我想我会尽量保持简单.

谢谢.

在另一个2元组列表中找到匹配的2元组的最快方法是什么？

以下代码效率极低.loc1和loc2是(x,y)坐标的元组列表.

loc3=[]
for loc in loc1:
    if loc in loc2:
        loc3.append(loc)

我认为哈希是关键但不确定如何在Python上做到这一点.请教我一个优雅的代码.谢谢.

背景资料:

在我的项目中,我正在将强化学习(RL)应用于Mario域.对于我的状态表示,我选择使用带有自定义对象的哈希表作为键.我的自定义对象是不可变的,并且覆盖了.equals()和.hashcode()(由IntelliJ IDE生成).

这是生成的.hashcode(),我在注释中添加了可能的值作为额外信息:

@Override
public int hashCode() {
    int result = (stuck ? 1 : 0);                // 2 possible values: 0, 1
    result = 31 * result + (facing ? 1 : 0);     // 2 possible values: 0, 1 
    result = 31 * result + marioMode;            // 3 possible values: 0, 1, 2
    result = 31 * result + (onGround ? 1 : 0);   // 2 possible values: 0, 1 
    result = 31 * result + (canJump ? 1 …

Run Code Online (Sandbox Code Playgroud)