算法题:怎么区分互不相同的<a, b>数对,hash还是?
问题: 有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的某些规律。
请大家发挥自己的想象力吧~~~
Answers
101*256 > 5000 所以M<5000的时候确实不可能不冲突
那么怎么设计冲突最小的hash算法呢? 这就涉及到题主的数据的分布情况了,那么姑且先认为分布是均匀的。
均匀分布的情况其实这个算法非常容易设计,直接取余即可
hash = (a * 256 + b) % M
按照上述hash算法,我们来算一下随机两个不同数对
a1, b1
和
a2, b2
hash冲突的概率
容易证明
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>
冲突的问题,如果要保证“斜着走不冲突”,还需要设法映射一下