我所认识的Hash
前言
关于Hash表，是我们经常会碰到的数据结构。大多数时候，它能高效地解决我们的一些实际问题。当然，多数情况下时间和空间正如鱼和熊掌，不可兼得。只有在特定的情况下，我们去选择适合当前需求的数据结构和算法。
Hash表本质是可以理解为键值对的集合。key-value一一对应。
字符Hash的简单应用
- 先来看这样一个简单的例子，有一个字符串，仅有大写字母’A'~'Z'组成，我们需要对这个字符串中所有的字母进行统计。然后输出对应的表，如 ACAADEB, 则A->3, B->1, C->1, D->1, E->1。
- 那么如何来做这个统计呢，这时候Hash表就可以派上用场了。字符‘A'对应的ASCII码为65，那么根据Hash的思想，我们可以把一个数组中的下标映射为字符，将下标对应的值中存储我们的统计结果，比如Hash['A'] = 3;
int hash[26];
string str = "ACAADEB";
void count_char_on_string(string &str) {
for (int i = 0; i < str.length(); ++i) {
++hash[str[i] - 'A'];
}
}
通过以上这个代码，我们就能将字符串中的字符一一统计下来。贯彻的思想就是将字符映射成数组下标。
字符串Hash
- 既然能够将字符映射成整数，那么肯定有办法将字符串也映射成整数。
- 关于字符串hash算法，有很多种，可以通过这篇博客了解，不同的字符串hash算法的对比。各种字符串Hash函数比较
- 此处，我仅仅以BKDRHash算法作为例子，核心的思想是通过一个选择器，我们也成为种子(seed)，通常选择种子应该是一个质数，如31， 131，1313等，这样的好处在于减少不同字符串映射为相同整数的冲突。通过一个计算公式，将不同的字符串进行转化为数字。
// BKDR Hash Function
unsigned int BKDRHash(char *str) {
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str) {
//每转化一位字符，用当前的hash值 * seed，在加上字符的ASCII码。
//hash * seed, 此处我们可以理解为当前字符串在前一个字符串hash值的基础上，偏移了一个种子的数级距离。
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF); //最后用hash & Ox7FFFFFFF 确保hash值在unsigned int 范围中。
}
利用字符串Hash可以解决很多问题，可以做字符串匹配。效率也蛮高的，相比KMP算法或者后缀数组和AC自动机等数据结构，它也不失为一种巧妙的办法。我们可以通过将每一位计算得到的hash偏移值存储在一个数组里，然后通过计算偏移得到子串的hash值，在和匹配串的hash值进行对比，如果相同，则说明匹配成功。
typedef unsigned long long ull;
const int MOD = 0x7FFFFFFF;
ull hash[1000]; //假设字符串长度小于1000
ull char_hash[1000]; //存储对应字符的hash值
inline ull cal_hash(string &str, const int l, const int r) {
if (l == 0) return cal_hash[r];
ull seed = 131;
hash[0] = 1;
for (int i = 1; i < str.length(); ++i) {
hash[i] = hash[i-1] * seed; //计算偏移
}
//用当前r对应的char_hash值-减去当前子串前一部分多计算的偏移hash值。就能得到字串的hash值了。
return (char_hash[r] - char_hash[l-1] * hash[r-l+1]) + MOD) % MOD;
}
解决字符串Hash冲突
- 或多或少，BKDRHash算法在极小的几率下会出现Hash冲突，解决的办法有很多，多数时候，我们采用邻接表来解决这个问题。
- 由于算法涉及&操作，会有导致冲突的可能。在多串匹配的情况下，我们需要将所有匹配字符串计算得到的hash值，存放到邻接表中，所谓的邻接表就是数组套链表。将计算到的匹配串hash值作为数组中的值，并加入到对应的链表中，如果我们计算到的hash值出现冲突的情况，就往对应链表中加入新的节点。在后续匹配的情况下，进行查找链表并做多一次简单的匹配即可。
关于Hash的一个有趣应用
- 有这么一个4 * 4的棋盘，棋子有两种状态，黑色或白色。我们这个时候也可以通过Hash来记录当前棋盘的信息。
那么对应的棋盘，我们用1表示黑色，用0表示白色。那么就有：
这个图转化成矩阵就是：
1 0 1 0
0 0 0 0
1 1 0 1
1 0 0 1
那么如何转化成整数来记录棋盘呢？
2^0 2^1 2^2 2^3
2^4 2^5 2^6 2^7
2^8 2^9 2^10 2^11
2^12 2^13 2^14 2^15
最后得到的棋盘我们可以通过判断当前棋子颜色，如果是黑色，则在对应位n上加上对应的2^n, n可以通过行列式计算出来。
int state[4][4]; //预处理记录棋子状态
unsigned int hash = 0;
for (int i = 0; i < 16; ++i) {
hash += state[i/4][i%4] * (1 << i);
}
这样我们就把棋盘信息转化成一个整数了。
最后
关于Hash表仍有很多的应用，还有一种应用是搜索领域，如何将互联网上大量的字符串存储，这里推荐大家了解一下字典树，它也是基于Hash算法的思想的数据结构。在iOS中，NSDictionary就是基于Hash的实现。以后有机会会深入CF框架看看实现源码，到时候再来分享。
