我想使用滚动哈希函数来获取一个非常大字符串的n-gram哈希值。
例如:
我知道一般来说这个哈希函数是生成为:
H = c1a^(k − 1) + c2a^(k − 2) + c3a^(k − 3) + ... + ck*a^0
其中a是一个常数,c1, …, ck是输入字符。
如果您在Rabin-Karp字符串搜索算法上跟随此链接,则说明"a"通常是某个大质数。
我希望我的哈希值存储在32位整数中,那么“a”应该有多大的质数才能避免整数溢出?
是否存在我可以使用的此哈希函数的现有实现?
这是我创建的一个实现:
"stackoverflow",分成5个字母组合,则为:
这种方法对于滚动哈希函数非常理想,因为在计算第一个n-gram哈希值之后,接下来的哈希值相对便宜,只需要删除第一个哈希值的第一个字符并添加第二个哈希值的新的最后一个字符即可。"stack", "tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow"
我知道一般来说这个哈希函数是生成为:
H = c1a^(k − 1) + c2a^(k − 2) + c3a^(k − 3) + ... + ck*a^0
其中a是一个常数,c1, …, ck是输入字符。
如果您在Rabin-Karp字符串搜索算法上跟随此链接,则说明"a"通常是某个大质数。
我希望我的哈希值存储在32位整数中,那么“a”应该有多大的质数才能避免整数溢出?
是否存在我可以使用的此哈希函数的现有实现?
这是我创建的一个实现:
public class hash2
{
public int prime = 101;
public int hash(String text)
{
int hash = 0;
for(int i = 0; i < text.length(); i++)
{
char c = text.charAt(i);
hash += c * (int) (Math.pow(prime, text.length() - 1 - i));
}
return hash;
}
public int rollHash(int previousHash, String previousText, String currentText)
{
char firstChar = previousText.charAt(0);
char lastChar = currentText.charAt(currentText.length() - 1);
int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1));
int hash = (previousHash - firstCharHash) * prime + lastChar;
return hash;
}
public static void main(String[] args)
{
hash2 hashify = new hash2();
int firstHash = hashify.hash("mydog");
System.out.println(firstHash);
System.out.println(hashify.hash("ydogr"));
System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr"));
}
}
我使用101作为我的质数。如果我的哈希值溢出,是否会有影响?我觉得这是可取的,但我不确定。
这样做是否正确?