HASH code 的选择

ssikkiss

目前我正在做一个推箱子工具，算法在运行时要尝试很多次，每次是一个节点，每个节点都要有一个值来与其他节点区分开，区分的方法就是对当前的地图进行描述，也就是要描述当前每个箱子的位置。我的地图最大是128*128个格子。（当然目前我还没看到这么大的推箱子地图，但不妨以此作为极限)。
箱子的坐标表示方法：坐标place=X坐标 + Y坐标*128，记为：place=x+y*128
一开始，我只求尽快完成程序，使用了一个简单的方法来描述：
我把每个箱子按坐标排序（这是必不可少的），从坐标最小的箱子开始，把箱子的坐标转化为一字符串，后面接一个“，”号，再接下一个坐标，再接一个逗号，。。。。。直到结束。最后得到一个字符串，而后我把求hash code的工作丢给系统了，因为我用的是java，里面的Hashmap自己会处理这个字符串。


现在，这个这个方法终于暴露了它的不足，它占的内存太多了！一般我搜索到100万个节点，就用了2G内存，后来查资料，知道即使一个空的字符串就有占40多byte，占了我一个节点的多半！
请问有什么好的算法，能得到较短的hash code，要求在42亿个不同节点内不重复，最好是一个64位整数!(java里32位和64位的整数的对象一样大，不过如果是使用32位，每个节点或许能节约4byte）

KeyTo9_Fans

我没有开发过工具，只做过大量的ACM在线评测的题目，所以只能把做题的经验与你分享。

按照你的思路，记$place=x+y*128$。

其中$x$的范围为$0$到$127$，$y$的范围也是$0$到$127$。

所以$place$的范围是$0$到$16383$。

把每个箱子按$place$值从小到大排序，得到一个数列，如：

$647$，$649$，$1027$，$1540$，$1545$，......

记为$a_1$、$a_2$、$a_3$、......、$a_n$。

把这个数列看成一个$K$进制数，其中每一项是一个数位。

由于$place$的范围是$0$到$16383$，所以这个数列天然地就是一个$16384$进制的数，每个数位可以是$0$、$1$、$2$、$3$、......、$16383$，共$16384$种可能。

把这个$16384$进制的数转化成$10$进制的数，然后除以$2^64$取余数即可。

但$2^64$是$16384$的倍数，所以高位对余数没有影响，这样取到的余数丢失了高位的信息。

所以我们取$K=16411$，这样每一位都对余数有影响，不会丢失信息。

最终哈希值的计算公式如下：

$code=(n+a_1*K+a_2*K^2+a_3*K^3+......+a_n*K^n)mod 2^64$

值域为$0$到$2^64-1$，恰好是一个$64$位整数。

冲突概率分析：

考虑到$K$值的随意性，可以使取模结果在$0$到$2^64-1$内分布均匀。

所以

$1$个节点不冲突的概率为$1$；

$2$个节点不冲突的概率为$(2^64-1)/2^64$≈$1$；

$3$个节点不冲突的概率为$(2^64-1)/2^64*(2^64-2)/2^64$≈$1$；

$4$个节点不冲突的概率为$(2^64-1)/2^64*(2^64-2)/2^64*(2^64-3)/2^64$≈$1$；

……

$4294967296$个节点不冲突的概率为$(2^64-1)/2^64*(2^64-2)/2^64*(2^64-3)/2^64*......*(2^64-4294967295)/2^64$≈$0.60653066$。

即$4294967296$个节点有$60%$左右的概率完全不冲突。

如果觉得这个概率不够保险，可以另取一个$K$，得到另一个$64$位整数。

用两个$64$位整数来标识一个节点，$4294967296$个节点不冲突的概率为$0.999...9$（至少连续$18$个$9$），可以放心使用了。

不知道真正实现起来还会有什么问题？

ssikkiss

谢谢!真正实现起来的话，其实我会把每个箱子的place，乘以16，再加一个“可接触值”，所谓“可接触值”，是描述此箱子能否被人接触到的状态，一个箱子有4个方向客被接触，所以这个“可接触值”的所有组合有16种，所以每个箱子的place要乘16。现在place的最大值是16384*16+15，得到的数列的就是262160进制的数，请问这时要如何选取那个素数k？另外，其实42亿个节点有点多了，目前我估计最多搜到1000万就要内存溢出

ssikkiss

还有，选取k需要什么原理？为什么是要比16384大的16411？比16484小行吗？

KeyTo9_Fans

随便取。

只要不丢失全局信息，求出来的哈希值概率分布均匀即可。

你取$7$、$97$、$997$等都没问题的。

$10^7$个节点不冲突的概率约为$(10^7*10^7)/(2*2^64)$≈$2.71e-6$。

所以尽管放心使用，没有必要用两个$64$位整数来标识了，一个就足够了。

一般来说，当冲突概率较小的时候，可以这样来估计：

冲突概率$p$=$n^2/(2m)$。

其中$n$是节点数，$m$是哈希值的值域大小。

ssikkiss

刚刚测试了下，发现用3，很快就出现了冲突，换了11，晚一点还是冲突，换103后就没冲突。我估计可能还是k越大越好。可能因为箱子不多，k又太小，导致code=(n+a1⋅K+a2⋅K2+a3⋅K3+......+an⋅Kn)更本没超过2^64.不知对不对？另外的原因可能是我算法错了，我是这样实现的：
假设最多10000个箱子：
  以我取k=3为例：
先循环10000次求出一个k值数组：
Kn=(Kn-1)*3 mod 2^64。

然后计算hashcode的时候，
循环每个箱子：
hash=hash+place * Kn
这里我并没有用hash=（hash+place * Kn）mod 2^64，因为我以为如果hash+place * Kn大于2^64，系统会自己只留下64位以内的那部分

mathe

>>>
再加一个“可接触值”，所谓“可接触值”，是描述此箱子能否被人接触到的状态
---------------------------
像这种辅助信息，没有必要添加到HASH code里面。
也许，你这里需要的不是HASH code,而是一种信息压缩算法。也许你可以试一下算术编码压缩，应该可以达到非常高的压缩比

ssikkiss

读了开源的推箱子工具JSoko（很成熟强大），发现它的hashcode算法是这样的：
1.先对一个大小为X*Y的地图的每一个格子赋值，赋值的方法是采用系统里的一个随机数发生器，使得每个格子都有一个不同的，随机的值。
2.以后要计算hashcode的时候，对每个箱子，查到他们所在的格子的值，把这些值异或，然后得到一个hashcode。
他这种算法速度十分快，而且也不用对箱子排序了，因为异或的结果是与顺序没关系的。

我照搬它的方法试了下，发现仍然有很多冲突。
不过JSoko是自己写的哈希表，出现冲突时，他把这个节点以链表的方式挂在hashcode相同的那个节点下面。而我是用的系统提供的哈希表，所有我添加到哈希表里的节点都应该不同，至于如何处理冲突则是系统的事。不过发现了他的这个算法后我有点想也像它那样自己弄hash表了。

请问，以128*128的地图为例，使用JSoko的算法，生成128*128个随机数（32位），任意选其中100个数拿出来异或，得到的值，再 mod  2^22,（2^22是哈希表的桶的数目），然后添加到哈希表对应的桶里，添加100万次后，求最长链表的长度，以及链表的平均长度？