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設計映射函數,可以映射到a到[0,50)上，映射b到[0,99]上，這樣總共有50*100=5000的需求。

另外，你的數字還有一個規律，在a相同的情況下，會出現b的連續值，這個在設計b的hash函數時可以利用起來，hash(b)=b%100就能夠比較好的把連續的b映射到不同的key。但你要是用了取高位的hash函數，就會把連續b映射到相同的key上，衝突會比較大。

update:

其是你這個完全可以用bitmap來做。每個映射到一個a256+b的整數上，這樣實際總共是[0,256101]，可以設定一個bitset<256101+1>就可以了，每一個存在就設定bitset[256a+b]為1,總共需要空間也不大。訪問也是常數時間的。

Answer 3

有個O(n)的演算法，也有個O(2)的演算法，直接就能夠定位。

這不就是個二維向量麼，求向量模做hash，產生衝突的時候根據方向來決定取previous還是next。

舉例：
1. 準備一個一維數組存node，這個node有兩個指針，一個previous，一個next，然後剩下的部分存
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的數就可以表示一個了（25855=256100+255，也就是組合的最大表示數)。假設這個數是x，則x=a256+b。用一個bool數組mark[i]表示數字i是否已經出現過。這樣就去分開了。我覺得這個方法是程式設計複雜度最小。

如果你需要效率最高的話，應該還是用開散列

Answer 5

確實如上所說 hashed = a*256+b 但是樓上兩位和題主似乎忽略了一個問題，有10000個數，但是hash範圍只有5000，這衝突率不是200%麼？