如 2 , 31 , 5 , 6 2,31,5,6 2,31,5,6:
查询 2 2 2,对 p p p取余,得到 2 2 2, h a s h [ 2 ] = 0 hash[2]=0 hash[2]=0,那么说明不存在;
查询 31 31 31,对 p p p取余,得到 5 5 5, h a s h [ 5 ] = 18 hash[5]=18 hash[5]=18,但不能说明不存在,要一直右移,每一位都判断一次,直到到了一个空位, h a s h [ 6 ] = 5 hash[6]=5 hash[6]=5, h a s h [ 7 ] = 31 hash[7]=31 hash[7]=31,发现存在,退出;
查询 5 5 5,对 p p p取余,得到 5 5 5, h a s h [ 5 ] = 18 hash[5]=18 hash[5]=18, h a s h [ 6 ] = 5 hash[6]=5 hash[6]=5,发现存在,退出;
查询 6 6 6,对 p p p取余,得到 6 6 6, h a s h [ 6 ] = 5 hash[6]=5 hash[6]=5, h a s h [ 7 ] = 31 hash[7]=31 hash[7]=31,直到 h a s h [ 8 ] = 0 hash[8]=0 hash[8]=0,没有发现存在,退出。
int find(int t) { int x=t%p; while(hash[x]) { if(hash[x]==t) return 1; x++; x%=maxn; } return 0; }这样也挖掘出了哈希的一个新功能——判重!!!
插入与判重可以把两个合并,
使它可以做到:如果返回是否存在,若不存在就插入!
int check(int t) { int x=t%p; while(hash[x]) { if(hash[x]==t) return 1; x++; x%=maxn; } hash[x]=t; return 0; } 压缩如果要存入的不是一个数,而是一个数对,甚至一个字符串呢?
当然可以,这时需要把各种千奇百怪的东西都压缩成一个数(归根结底还是变成了一个数)
怎么压缩?
尽可能使出现重复的概率少,
如数对 ( 4 , 3 ) (4,3) (4,3),