演算法題:怎麼區分互不相同的<a, b>數對,hash還是?
03-03
問題:有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];
推薦閱讀: