大整數Hash

總是聽高屆的大佬說，一個字符串Hash，能搞出大部分的字符串題，Hash真的有那么神嗎？
答:是的
近來，參加很多NOIP模擬賽，其中一場設計判斷大整數是否存在偷懶了一下，開了一個map原本能A的題T掉了三個點，OJ上評測T3個點還跑了1480ms，忍痛改Hash后發現A了只跑了356ms
對于整數的判重、Hash事實上有很多方法，具體應用要看數據范圍和題目要求
看大整數HASH好多博客都是工業編程，那我就寫個OI的吧，接下來就列舉一些常見判重方法

1.數組判重

數組判重是一種較為常見的方式，我以前很常用，桶排序（多種叫法）就是類似于這樣的
優點：速度快，單次O(1)，支持統計次數，可以動態
缺點：支持范圍小，數組可能會開不下，數據在10^8及以上基本就不能使用了

2.set、map判重

set、map判重簡單又方便，還有各種高級功能，但由于調用STL，速度會有點慢
優點：功能多，使用方便，一般數據不大可以使用，map支持統計次數，可以動態，支持的范圍較大，只要數字數量不爆就能開下
缺點：速度較慢，常數可能會優點大，單次O(logn)

3.二分判重

二分判重，比較傳統，手打的常數小，相較于map性能更好，但是功能不多
優點：常數小，支持范圍也較大（同set、map），較為簡單
缺點：單次還是O(logn)，功能少，不支持動態，而且統計次數會增加常數

4.平衡樹

各種平衡樹都還行，但是我比較菜，手打容易打掛，但是整體性能不得不承認還是可以的
優點：常數小，支持范圍也較大（同set、map），功能也比較多，支持動態還能統計次數
缺點：單次還是O(logn)，打起來麻煩

5.整數HASH

Hash真的有用，信仰的力量！！！
優點：常數小，支持范圍較大，支持動態、可以統計次數，單次O(1)!!!打起來也不煩
缺點：打Hash要看臉，可以故意來卡你（但隨機數一般卡不了）

具體代碼+注釋介紹

#include<cstdio> #include<cstring> inline int max(const int a,const int b){return a>b?a:b;}//手寫，讓這些函數的常數小一點 inline int min(const int a,const int b){return a<b?a:b;} inline int abs(const int a){return a>0?a:-a;} inline void swap(int&a,int&b){int c=a;a=b;b=c;} inline void read(int&x)//可讀負數的讀入優化 {char cu=getchar();x=0;bool fla=0;while(cu<'0'||cu>'9'){if(cu=='-')fla=1;cu=getchar();}while('0'<=cu&&cu<='9')x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } void printe(const int x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } inline void print(const int x)//可輸負數的輸出優化 {if(x<0)putchar('-'),printe(-x);else printe(x); } namespace bigHash//打板子，當然放一個namespace方便使用 {const int mod=100007,maxn=100001;//mod可以自己調，maxn是不同元素的種類數量int head[mod],nxt[maxn],vau[maxn],tmp=0;int tow[maxn];inline void add(const int x)//加入元素{int whom=x%mod;for(int i=head[whom];~i;i=nxt[i])if(tow[i]==x){vau[i]++;return;}tmp++;nxt[tmp]=head[whom];head[whom]=tmp;tow[tmp]=x;vau[tmp]++;}inline bool find(const int x)//查找元素是否存在1存在0不存在{int whom=x%mod;for(int i=head[whom];~i;i=nxt[i])if(tow[i]==x)return 1;return 0;}inline int get(const int x)//獲得數字x的數量{int whom=x%mod;for(int i=head[whom];~i;i=nxt[i])if(tow[i]==x)return vau[i];return 0;}inline void init()//初始化{memset(head,-1,sizeof(head)); } } using namespace bigHash; int main() {init();//初始化int n,q;read(n);//開始的數組的數字個數for(int i=1;i<=n;i++){int a;read(a);add(a);}read(q);//詢問for(int i=1;i<=q;i++){int a;read(a);if(find(a))print(get(a));//如果存在輸出數量else print(0);//否則輸出0putchar('\n');}return 0; }

這個Hash的原理其實很簡單，如圖，具體會不會被卡要看你的模數咋樣，一般取一個質數比較保險

嗯，就講到這吧，如發現有問題可以提出，有問題也可以問我哦

總結

以上是生活随笔為你收集整理的整数判重、大整数Hash的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。