算法题:怎么区分互不相同的<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的某些规律。

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

c C++ 数据结构和算法

野生草泥馬 10 years, 11 months ago

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> 冲突的问题,如果要保证“斜着走不冲突”,还需要设法映射一下

七分熟的牛排 answered 10 years, 11 months ago

Your Answer