关于字符串哈希值模数的问题

      在学数据结构时我们会发现一些问题没有给出详细的说明,其中在解决哈希碰撞中二次探查法模数必须是4k+3这是怎么回事呢?

本文将会展开进行讨论

      对于简单的线性探查法来说,由于是线性探查因此第i次探查和第j次探查不会重,例如:

      但由于线性探查会造成拥挤的效应因此需要构造一个二次序列來解决这个问题。

       这就出现了本文开头提到的性质这使得二次探查的序列可以在开始的p步内遍历整个表,而不重

       为了照顾到这些性质,比较简单的方法就是目前教科书提到的二次探查法可以满足上述要求。

其实就是我看到了 ,于是想把他$hack$了..

($w$指的就是里面的那个$613613$那个东西,不知道叫什么;$D$就是指模数)

如果$w$跟字符集大小一样的话其实$hack$是很方便的,只要把$D$转化成$w$进制就行了.

不然的话我就呮会暴力了..

把它转化成背包问题,然后用$bitset$优化

因为这人模数太大了,数组也开不下,所以要输出方案的话就得多用一个答案长度的时间.

(找到串使嘚会被误判成和$aaa..aa$相同后还得做些操作)

(话说重测后发生了一些神奇的事情..比如我从$23ms$变成了$8ms$,排行榜上的顺序也发生了一些变化)

把原串变成用26个01串表示第i个串對应的字符是i 然后进行字符串hash,s和t双射的条件是26个串的hash值排序后一一相等

我要回帖

更多关于 字符串哈希 的文章

 

随机推荐