演算法題:怎麼區分互不相同的<a, b>數對,hash還是?

問題:有N個數對&,其中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非常有可能是分段連續的,比如像下面這樣:

&<2, 1&>

&<2, 2&>

&<2, 3&>

&<2, 4&>

&<2, 5&>

&<2, 124&>

&<2, 125&>

&<2, 126&>

&<2, 127&>

&<2, 128&>

&<2, 129&>

&<2, 130&>

...

請大家發揮自己的想像力吧~~~


按你給的a: [0-100], b: [0-255],這不是現成的 hash(a, b) = a*256 + b嗎?用一個不到3KB的bitmap就可以標記了: char bitmap[101*256/8];


推薦閱讀:

TAG:演算法 | CC | 演算法與數據結構 | 哈希函數 | ACM競賽 |