哈希hash 各种用法最全详解 (2)

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)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgypzj.html