# 字符串哈希

例子为 LeetCode 187. 重复的 DNA 序列

DNA 序列由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA 序列。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA 序列的字符串 s ，返回所有在 DNA 分子中出现不止一次的长度为 10 的序列 (子字符串)。你可以按任意顺序返回答案。

常规解法

本题限制时间的操作就是拿到一个长度为 10 的字符串，如何快速找到原字符串是否出现过相同的字符串。常规解法就是将遍历过的每个字符串都放到哈希表里面，然后 O (1) 时间复杂度查找是否出现相同的字符串。

	class Solution {
	public List<String> findRepeatedDnaSequences(String s) {
	List<String> res = new ArrayList<>();
	Map<String,Integer> map = new HashMap<>();
	int n = s.length() - 10;

	for(int i = 0; i <= n; i++) {
	String tmp = s.substring(i,i+10);
	int t = map.getOrDefault(tmp,0);
	if(t == 1) res.add(tmp);
	map.put(tmp, 1+t);
	}
	return res;
	}
	}

这是基于子串长度较低才可以使用，如果子串长度很大，光是生成子串的操作复杂度就很高。

如何给定一个字符串，计算其子串的哈希值：

原理是：给定一个字符串，要把它转换为数字，先把每个字符都先对应一个数字，然后按第 i 个字符乘以一个进制 P 的 i 次方，再相加，这个数也许很大，所以一般会取模。

为什么会和进制扯上关系：

我们类比推理一下：12345 和 abcde，前者是整数，后者是字符串。对于整数，我们可以就用它的值来作为哈希值，那这个整数的哈希值是怎么算的呢？假设是在 10 进制下：

12345 = (((1*10 + 2)*10 + 3)*10 + 4)*10 + 5 = 1*10^4 + 2*10^3 + 3*10^2 + 4*10 + 5

同理，字符串中每个字符也可以代表某个数字，那么就可以看做每个字符就是数位上的一个数字，就可以快速转换为整数了，那么进制 P 为多少合适呢？P 最好是素数，1313，131313。

hash(abc) = (a*P + b)*P + c = a*P^2 + b*P + c

定义两个数组， h[i] 表示 [0,i-1] 字符串的哈希值， p[i] 表示 P^i ，也就是进制的值，所以这两个数组的初始化也就出来了（ h[i] 表示的不是 [0,i] 是有原因的，你当然可以这么表示，只是本题写成 i-1 更方便）：

	int n = s.length(), P = 131313;
	int[] h = new int[n+1], p = new int[n+1]; // 防止越界，多分配一个

	p[0] = 1;h[0] = 0; // 这一步可以省略
	for(int i = 1; i <= n; i++) {
	h[i] = h[i-1]*P + s.charAt(i-1);
	p[i] = p[i-1] * P;
	}

那么现在根据两个数组求解 [i,j] 子串的哈希值？举个🌰，现有字符串 s = "abcdef" ，要求 sub = "cd" 的哈希值（我们遍历计算的话可知： c*P + d ）：

d 的下标是 3， h[4] = a*P^3 + b*P^2 + c*P + d; h[2] = a*P + b; 简单计算可知：

	// 计算的是 [2,3] 区间哈希值
	int res = h[4] - h[2] * p^(3-1);

推广到 [i,j] 就是：

所以这个题的字符串哈希解法就是：

	class Solution {
	public List<String> findRepeatedDnaSequences(String s) {
	List<String> res = new ArrayList<>();
	Map<Integer,Integer> map = new HashMap<>();
	int n = s.length(), P = 131313;
	if(n <= 10) return res;

	int[] h = new int[n+1], p = new int[n+1];
	p[0] = 1; h[0] = 0;

	// 这里做个处理，h [i] 表示 h [0,i-1] 的哈希值
	for(int i = 1; i <= n; i++) {
	h[i] = h[i-1]*P + s.charAt(i-1);
	p[i] = p[i-1] * P;
	}

	// 试想一下，如果 h [i] 表示的是 [0,i], 那么 h [0] 的计算就要放在 for 循环外，不好看
	// 这个东西看个人吧 hhhhh
	for(int i = 0; i <= n-10; i++) {
	int hash = h[i+10] - h[i]*p[10];
	int t = map.getOrDefault(hash,0);
	if(t == 1) res.add(s.substring(i,i+10));
	map.put(hash,t+1);
	}
	return res;
	}
	}

# 哈希冲突

其实，如果在计算中不会出现任何溢出，那么是不存在哈希冲突的，但是这样的数据量其实是会溢出的。

以本题为例，先看一下计算过程哪里会出现溢出：

	public static void main(String[] args) {
	int s = 1;
	for(int i = 0; i < 34; i ++) {
	s *= 2;
	System.out.println(s);
	}
	}

s 到最后肯定溢出了，最后几个打印出来的都是 0，我们在计算 h[i] 的时候，如果出现溢出，也就可能溢出导致哈希值冲突。

如何降低冲突：单 Hash 方法出现冲突的概率比较大，所以可以采用双 Hash 方法，也就是再加一个进制 P2，除了维护通过 P 计算出来的 h[i] 以外，还要维护通过 P2 计算出来的 h2[i] ，比较哈希值的时候通过两个哈希值来确定一个字符串，这样更准确。

三叶姐的文章：字符串哈希入门
【算法学习】字符串哈希（Hash）