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

我的需求最好是利用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，这样就可能有不能区分的了，没关系，只要使得冲突最小也行。

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

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

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

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的倍数，这样可以保证或<0-100, y>一定不冲突，不过会有一定和冲突的问题，如果要保证“斜着走不冲突”，还需要设法映射一下

相关文章