c++ - 算法题：怎么区分互不相同的<a, b>数对，hash还是？

Question

问题：有N个数对<a, b>，其中a的范围是[0, 100]，b的范围是[0, 255]，N < 10000，如何区分这N对数对？

我的需求最好是利用a和b的值通过某种算法产生一个数，每个数对产生不一样的值，这样就能相互区分了。

比如有下列这些数对：
<1, 2>
<2, 3>
<2, 1>
<7, 76>
<4, 2>
<45, 123>
...
等等，怎么设计一个利用a和b设计一个算法，来区分这些数对，比如a + b，当然我只是举个例子，简单的加减乘除都不行，因为有些数对比如<2, 1>与<1, 2>就不能区分了。

如果区分不了，那么能不能设计一个hash算法，使得这些数对全部映射到[0, M]之间，M最好<5000，这样就可能有不能区分的了，没关系，只要使得冲突最小也行。

重点：这样的需求不好解决问题，因为<a, b>是随机的，没什么分布规律。但<a, b>有一些分布特点：如果同一个a，b非常有可能是分段连续的，比如像下面这样：
<2, 1>
<2, 2>
<2, 3>
<2, 4>
<2, 5>
<2, 124>
<2, 125>
<2, 126>
<2, 127>
<2, 128>
<2, 129>
<2, 130>
...

我的要求：尽可能时间高效，比如用hash，一下就能判断。

当然有人会想到用最简单的map<int, int> m，m的大小就是数对的个数，但显然这样的方向时空性能都不太高，而且没有利用a和b的某些规律。

请大家发挥自己的想象力吧~~~

Answer 1

101*256 > 5000 所以M<5000的时候确实不可能不冲突

那么怎么设计冲突最小的hash算法呢？ 这就涉及到题主的数据的分布情况了，那么姑且先认为分布是均匀的。

均匀分布的情况其实这个算法非常容易设计，直接取余即可 hash = (a * 256 + b) % M

按照上述hash算法，我们来算一下随机两个不同数对a1, b1和a2, b2hash冲突的概率

容易证明 a*256 + b这个数值在题主的ab范围内和数对是一一对应的，且正好是[0, 25600+255]

那么这个冲突的概率也就等价于[0, 25855]内两个不同的随机整数对M的同余的概率

没有公式编辑器，概率论的东西也差不多还给老师了，后面的计算和证明就省略了，总之，题主的问题在平均分布的假设下直接取余就是冲突最小的hash算法了。更普适的诸如md5、sha1等hash算法主要是在输入长度不固定，还不一定平均分布的情况下，最小化冲突为目标设计的

---

根据题主更新的分布，我建议M的取值选257的倍数，这样可以保证<x, 0-255>或<0-100, y>一定不冲突，不过会有<x+1, y+1>一定和<x,y>冲突的问题，如果要保证“斜着走不冲突”，还需要设法映射一下

Answer 2

算法：两步hash，你的数是很规范的，a和b的范围都是给定的。算全域hash，a也只有100个hash值，b有250个，所以总共只有100×250=25000个hash值，超过你的<5000的要求。所以就用两步hash吧。

具体设计：<a,b>先给a设计映射函数,可以映射到a到[0,50)上，映射b到[0,99]上，这样总共有50*100=5000的需求。

另外，你的数还有一个规律，在a相同的情况下，会出现b的连续值，这个在设计b的hash函数时可以利用起来，hash(b)=b%100就能够比较好的把连续的b映射到不同的key上。但你要是用了取高位的hash函数，就会把连续b映射到相同的key上，冲突会比较大。

update:

其是你这个完全可以用bitmap来做。每个<a,b>映射到一个a256+b的整数上，这样实际总共是[0,256101]，可以设置一个bitset<256101+1>就可以了，每一个<a,b>存在就设置bitset[256a+b]为1,总共需要空间也不大。访问也是常数时间的。

Answer 3

有个O(n)的算法，也有个O(2)的算法，直接就能够定位。

这不就是个二维向量么，求向量模做hash，产生冲突的时候根据方向来决定取previous还是next。

举个例子：
1. 准备一个一维数组存node，这个node有两个指针，一个previous，一个next，然后剩下的部分存<a,b>
2. 针对给出的<3，4>(假设是这个)取向量模=5=hashkey,根号计算比较耗时间，那就不用开根号，我们的'hashkey'就＝25.
3. 随便你用什么hash方法去算一维数组的index，我比较喜欢取模，那么就是 'hashkey%数组长度' 得到一个index.
4. 如果对应的index里面是个空node，那么就把这个node放进去，如果不是空的，那就算一下向量方向 '4-3 > 0'，方向大于0的node就用next去指，方向小于0的就用previous去指。
5. 然后根据上一次计算出来的方向不断访问previous或者next，直到找到就好。

因为有了方向，其实寻找到那个node就很快了，比一般的hash算法都能快很多。因为产生碰撞之后，另一个方向的node list直接就可以不用遍历了。

如果模和方向都一样，很容易就找到相同的node了。

O(2)的算法就是基于上面的再优化一下。可以根据向量斜率再来一轮hash，那么第二步直接就定位到唯一向量了，不会有冲突（模长相同且斜率相同的向量是相同向量，而且题设有个隐含条件，所有向量的起点都是原点<0,0>。）。要真出现冲突，那就恭喜，你找到重复的node了。不过我觉得一轮hash也差不多就足够了。一次遍历之后所有重复的node就都能找到了。

最终它大概长这个样子：
--------| <4,3> |
<1,1> | <3,4> | <1,3> |
--------| <根号5,根号5> | （假设有，我懒得去凑数字了。。。）

横线表示空格，没有任何意义

比如给一个<4,3>,你会发现5对应的位置有了<3,4>，然后你看方向，小于0，那么就取<3,4>那个node的previous指针往上找，诶，瞬间就找到<4,3>了～因为有了方向，<根号5, 根号5>直接就不用比较了。

Answer 4

用一个0-25855的数就可以表达一个<a,b>了（25855=256100+255，也就是组合的最大表示数)。假设这个数是x，则x=a256+b。用一个bool数组mark[i]表示数字i是否已经出现过。这样就去分开了。我觉得这个方法是编程复杂度最小。

如果你需要效率最高的话，应该还是用开散列

Answer 5

确实如上所说 hashed = a*256+b 但是楼上两位和题主似乎忽略了一个问题，有10000个数，但是hash范围只有5000，这冲突率不是200%么？