字符串哈希

• 字符串的hash是通过某种字符串hash函数将不同的字符串映射到不同的数字，配合其他数据结构或STL，进行判重，统计，查询等操作。

实现哈希

• 一个常用的字符串hash函数是hash[i]=(hash[i-1]*p+idx(s[i]))%mod， 即hash[i]是字符串的前i个字符组成的前缀的hash值，而idx(s)为字符s的一个自定义索引，例如，idx(‘a’)=1，idx(‘b’)=2，……，idx(‘z’)=26。

• 例如，p=7，mod=91，把字符串"abc"映射为一个整数：

hash[0]=idx(‘a’)%91=1，字串"a"被映射为1；

hash[1]=(hash[0]*p+idx(‘b’))%mod=9，表示字符串"ab"被映射为9；

hash[2]=(hash[1]*p+idx(‘c’))%mod=66，所以，字符串"abc"被映射成66。

运用哈希

• 基于字符串hash函数，可以求字符串的任何一个子串的hash值：hash[l…r]=((hash[r]-hash[l-1]*p(r-l+1)) %mod+mod) %mod。

• 如上例，对于字符串"abab"，

hash[2]=(hash[1]*p+idx(‘a’))%mod=64，表示字符串"aba"被映射为64；

hash[3]=(hash[2]*p+idx(‘b’))%mod=86，即字符串"abab"被映射为86。

则hash[2…3]=( (hash[3]-hash[1]*p2)%mod+mod)%mod =9=hash[1]，

即字符串"abab"的第一个"ab"子串和第二个"ab"子串所对应的hash值相同，都是9。

• p和mod取值要合适，否则可能会出现不同字符串有相同的hash值。一般p和mod要取素数，p取一个6位到8位的较大的素数，mod取一个大素数，比如109+7，或者109+9。

优化哈希

•经验值：根据极多大佬的计算得出p取131或13331时hash值重合概率较小，mod则取尽量大的素数

•溢出取模：用unsigned long long定义hash数组，在计算过程中因为unsigned long long的数据范围在-264~264,数据溢出时相当于对264取模。这样可以省去取模操作。

•在计算p的n次方时，用普通的累乘或pow函数常常会超时，这里可以采用快速幂，或在计算hash[i]值的同时计算p的i次方存在一个数组中

快速幂代码

ll cal(int x,ll y) //计算和返回 y^x % mod 的结果值
{
	ll re = 1;
	while(x)
	{
		if(x&1) re = (re*y)%mod;
		x >>= 1; y = (y *y)%mod;
	}
	return re;
}

题目地址：POJ2406【Power Strings】
例题讲解
AC代码：
#include<iostream>
#include<string.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 1000010,base = 131;
char str[N];
ULL h[N],p[N];
int len; 
ULL get(int l,int r)//获得 l 到 r 的 hash 值 
{
	return h[r] - h[l - 1] * p[r - l + 1];
}
bool check(int x)//若所有长度为 x 的相邻子串对应的散列函数值相等，则返回 true；否则返回 false
{
	for(int i = x*2 ;i <= len;i += x)
		if(h[x] != get(i-x+1,i))
			return false;
	return true;
}
int main()
{
	while(~scanf("%s",str + 1))
	{
		len = strlen(str + 1);
		if(len == 1&&str[1] == '.')
			return 0;		
		h[0] = 0,p[0] = 1;
		for(int i = 1;i <= len;i ++ )
		{
			h[i] = h[i-1] * base + str[i] - 'a' + 1; 
			p[i] = p[i-1] * base;
		}		
		for(int i = 1;i <= len;i ++ )
			if(len%i == 0 && check(i))
			{
				printf("%d\n",len/i);
				break;
			}
	}
	return 0;
}

目录

给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)

线性探测法例题

链地址法例题

网上一些博客错误的指正

给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)

哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。

1. 请画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算查找成功和查找失败时的平均查找长度各是多少。

2. 请画出按照链地址法处理冲突得到的哈希表，并计算查找成功和查找失败时的平均查找长度各是多少。

ps:老师改题啦，原来和下面的那题是一样的，题目任你改做不出算我输，哈哈哈（低调低调）

由第一个H（19） = 19MOD 13 =  6以此类推

19
			
14
			
23
			
1
			
68
			
20
			
84
			
27
			
55
			
11
			
10
			
79
		
6
			
1
			
10
			
1
			
0
			
7
			
6
			
1
			
3
			
11
			
10
			
1
		
可以得到散列表为

0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
65
			
14
			
1
			
21
			
55
			
79
			
19
			
78
			
84
			
 
			
23
			
11
			
10
			
 
			
 
		
 

key
			
0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
count
			
1
			
1
			
2
			
3
			
2
			
5
			
1
			
1
			
3
			
 
			
1
			
1
			
3
			
 
			
 
		
查找成功的平均长度：（1+1+2+3+2+5+1+1+3+1+1+3）÷12 = 24/12 = 2; 

key
			
0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
count
			
10
			
9
			
8
			
7
			
6
			
5
			
4
			
3
			
2
			
1
			
4
			
3
			
2
			
 
			
 
		
查找失败得平均长度：（10+9+8+7+6+5+4+3+2+1+4+3+2）÷13 = 64/13；

（2）

链地址法：



查找成功的平均长度：（1×7+2×3+3×1+4×1）÷12 = 20/12=5/3；

查找失败的平均长度：（2+5+1+2+1+1+3+2+1+1+3+2+1）÷13 = 25/13； 

 

 

请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中，查找失败时的平均查找长度如何计算？


例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)


       哈希函数为：H(key)=key MOD 13, 哈希表长为m=15，


       设每个记录的查找概率相等，采用以上两种方法处理冲突，查找失败时的平均查找长度各是多少

 

 这题可真得是出到点子上去啦，看视频，找资料，网上有得解释真的是有点误人子弟，随后加上问了老师一番才有了确定的结果

没错我们主要得难点还是查找失败得分母到底是什么呢，还有一个网上解释错得，但广为流传得，

但是还是全部体系得去写吧毕竟也许以后就忘了

线性探测

（1）

有第一个H（19） = 19MOD 13 =  6，后面得以此类推，

19
			
14
			
23
			
1
			
68
			
20
			
84
			
27
			
55
			
11
			
10
			
79
		
6
			
1
			
10
			
1
			
3
			
7
			
6
			
1
			
3
			
11
			
10
			
1
		
可以得到散列表为

0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
 
			
14
			
1
			
68
			
27
			
55
			
19
			
20
			
84
			
79
			
23
			
11
			
10
			
 
			
 
		
 

key
			
0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
count
			
 
			
1
			
2
			
1
			
4
			
3
			
1
			
1
			
3
			
9
			
1
			
1
			
3
			
 
			
 
		
查找成功的平均长度：（1+2+1+4+3+1+1+3+9+1+1+3）÷12 = 30/12 = 2.5; 

 

key
			
0
			
1
			
2
			
3
			
4
			
5
			
6
			
7
			
8
			
9
			
10
			
11
			
12
			
13
			
14
		
count
			
1
			
13
			
12
			
11
			
10
			
9
			
8
			
7
			
6
			
5
			
4
			
3
			
2
			
 
			
 
		
查找失败得平均长度：（1+13+12+11+10+9+8+7+6+5+4+3+2）÷13 = 7

 

 

ps:查找失败得平均长度分母是MOD后面得数也就是13

（2）

链地址法：



查找成功的平均长度：（1×6+2×4+3×1+4×1）÷12 = 21/12；

查找失败的平均长度：（1+5+1+3+1+1+3+2+1+1+3+2+1）÷13 = 25/13； 

ps：它的分母也是mod后面的数13 ，并且查的范围是0-12；

 

线性探测法例题

将关键字序列（14、15、9、4、16、2、21）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为： H(key) = (key x 3) MOD 7，处理冲突采用线性探测再散列法，要求装填因子为0.7。

(1) 请画出所构造的散列表；

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

当时由于老师让及时做出来，就有点匆忙，能懂哪个意思就行



链地址法例题

题目

将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为：H(key)=key mod 11，处理冲突采用链地址法，求在等概率下查找成功和查找不成功的平均查找长度

1mod11=1，所以数据1是属于地址1

13mod11=2，所以数据13是属于地址2

12mod11=1，所以数据12也是属于地址1（这个数据是数据1指针的另一个新数据）

34mod11=1，所以数据34是属于地址1（这个数据是数据12指针的另一个新数据）

38mod11=5，所以数据38是属于地址5

33mod11=0，所以数据33是属于地址0

27mod11=5，所以数据27是属于地址5，（这个数据是数据38指针的另一个新数据）

22mod11=0，所以数据22是属于地址0，（这个数据是数据33指针的另一个新数据）

链地址法处理冲突构造所得的哈希表如下：



查找成功时： ASL=（3×1+2×3+1×4）/8=13/8，

查找不成功时：ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11；或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11，



 

网上一些博客错误的指正

 这个里面的一个解释是错的



 



这个地址就是9

这个也是有错的



全部少加一个1

说到哈希，总感觉到它很高深，说到底它只不过是实现集合和字典（满足数据增删改查的结构）的一种方式，而不是总把它当成单独的一种数据结构或者算法去讨论。

散列法：

定义：将数据中key传给一个哈希函数f()，按照计算出来的哈希值h=f(key)将那个带有key的数据分布到一个哈希表中(大小m自定义)。
当m<数据量n的时候，会出现碰撞(即哈希值为同一个，意味着哈希值相同的数据要储存在哈希表的同一个哈希地址里)，甚至大于等于的时候也会出现（取决于哈希函数），所以此时需要解决碰撞的机制。
解决碰撞1开散列：每个哈希单元格都存储着一个链表，所有对应哈希值的数据都存储在这个链表里，所以碰撞后，直接将相同哈希值的数据依次往链表里push，所以可想而知最坏情况就是所有键的哈希值都是一样，这样的话所有数据都在一个哈希地址的单元格链表里。这样的话增删改查都是遍历对应那个哈希值的链表即可。
解决碰撞2闭散列：当碰撞时，对应哈希值的单元格已经存储数据，这时我们就线性探测（往这个单元格后面依次遍历，只要找到一个空的就将元素插在里面），这种方法比前一种更有可能出现最坏情况：会导致合并的哈希单元格越来越多，到最后可能插入一个元素就需要O(n)，因为可能需要遍历很多单元格才能找到空的。往哈希表里添加是这样，查找也是如此，依次往后找（但是如果哈希合并了就很麻烦了），删除更加麻烦，因为删除了以后查找某个键，就不会往后找，直接就不存在了，所以我们就需要在删除时添加个占位符，表示曾经有过数据，但是被删除了。而且闭散列有的时候防止最坏情况的发生，需要辅助双散列或者重散列。个人还是选择开散吧。

散列法对数据的操作为O(1)~O(n)（最坏情况），假如选择适当的哈希函数和哈希表的大小基本上为O(1)，实现集合/字典降低了操作的时间复杂度。
与另一种实现字典的数据结构平衡二叉搜索树相比：

时间复杂度的不同：哈希平均为O(1)，最坏为O(n)，而平衡二叉搜索树最好最坏都是O(logn)
有序性保留：哈希不保留key有序性，而后者保留，所以散列表不适合按序遍历和按范围查询的应用。

例题：

LeetCode 1.两数之和

首先暴力枚举：O(n^2),排个序双指针遍历O(nlogn)，关键效率不高的原因时，我需要在遍历给定数组的时候，比如遍历到第i个，知道可以和nums[i]一起组成target的那个数x，是否在我已经遍历到那些数字当中(肯定不会在没遍历到的数字当中)，所以我们需要一个数据结构去存储刚才遍历到的那些数字，并且可以数据结构是通过键(这些数字)值来增删改查的，因此我们需要一个集合这样的数据结构，而这道题明显采用哈希表会更优。

#define MP make_pair
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash_table;
        vector<int> ans;
        for(int i = 0;i < nums.size();++i){
            if(hash_table.count(target - nums[i])){
                return {i,hash_table[target - nums[i]]};
            }
            else 
                hash_table.insert(MP(nums[i],i));
        }
       return ans;
    }
};


LeetCode 217.存在重复元素

首先暴力枚举：O(n^2),排个序遍历看是否和前一个元素相同O(nlogn)，关键在于遍历到第i个数时，是否知道前面出现过这个数，一旦出现就说明有重复的，所以需要实现一个集合，很明显以哈希O(1)实现的在这里更快。而且此题也可以换个思路，那就是把所有nums的元素都push到那个哈希集合里，因为在cpp中unordered_set默认只能插入不存在的元素，所以到最后比下哈希集合和nums数组的大小就知道是否重复了。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.empty()) return false;
        unordered_set<int> hash_table;
        for(int num:nums){
           hash_table.insert(num);
        }
        return hash_table.size() < nums.size();
    }
};


LeetCode 594.最长和谐子序列

首先要明确一点子序列是可以不连续的，而子串是要连续的，所以这道题我们可以不用考虑滑动窗口等方法。

这道题的关键点：如何知道某个数，和它相同的数出现了多少次，比它大1的数出现了多少次（假如在所有数字都会遍历到的情况下，我们只需要知道比它大1或者小1的即可），所以我们需要实现了以数值为键，次数为值的字典来实现查询，很明显这里用哈希实现效率会比红黑树高。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int> hash_table;
        for(int num:nums){
            hash_table[num]++;
        }
        int longest = 0;
        for(pair<int,int> t:hash_table){
            if(hash_table.count(t.first + 1)){
                longest = max(longest,t.second + hash_table[t.first + 1]);
            }
        }
        return longest;
    }
};

随笔之哈希表
哈希和哈希表
哈希
哈希表
哈希表例题和解析
存在重复元素
字母异位词分组

哈希和哈希表
哈希
哈希（Hash），也叫做散列，杂凑。可以认为是一种算法或者是思想。

其作用是对任意长度的输入通过一定的转换映射成相同的长度。

对于一个关键字Key，都会得到一个f(Key)，这个f()就是哈希函数。一般来说，一个好的哈希函数会让不同的Key对应不同的值（当不同的Key得到相同值的时候称为哈希碰撞，应当尽量避免）。
哈希表
哈希表（Hash Table），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。（百度百科）
哈希表例题和解析
通过以下几个例子来一起看看哈希表的一些使用。
简单：217.存在重复元素

中等：49. 字母异位词分组
存在重复元素
Q：给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
先来看题，很容易理解题目，在一个数组中找是不是出现了重复的元素，一看到重复，其实就很容易想到使用哈希的思想，因为在哈希中键和值总是有着对应的关系。在这道题目中，键就是数组中的元素，而值，可以是其存放的地址，可以是其出现的次数这些都可以让我们找到那个重复的元素。

下面是本题的java代码
public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }

这道题是一个非常简单的题目，但是我们可以从里面总结出一点就是哈希表是可以用来解决重复这个问题的。
字母异位词分组
Q：给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例：

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [

[“ate”,“eat”,“tea”],

[“nat”,“tan”],

[“bat”]

]
在这道题目中，我们可以找到问题的关键：分组。对于一串输入，我们要对他们进行分组，那么分组的依据是什么，就是组成该字符串的字母都是什么，在这个问题中，我们的键就是组成这个字符串的字母，值就是在输入中和键的组成相同的字符串组成的列表。

来看代码：
public List<List<String>> groupAnagrams(String[] strs) {
		//对于我们的思路，首先构建一个hashmap，key部分选择string类型用来存放组成字符串的字母串，在遍历过程中找到相同组成就加入到对应value的list中
       	Map<String, List<String>> map = new HashMap<String, List<String>>();
       	
       	for (String str : strs) {
       		int[] counts = new int[26];
            int length = str.length();
            //这里遍历字符串找出所有组成的字母
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            //获得key对应的value
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            //将str加入list
            list.add(str);
            //更新key对应的value
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
 
    }

在这个问题中， 我们可以看到，哈希表在分组这个问题中也有着它的作用。而重复，实际上也是分组的一种，把相同的元素分到同一组中。在解决诸如此类的问题中，不妨考虑一下是使用哈希表这种数据结构。
随便写写不喜勿喷，题目来源于LeetCode网站。
文尾贴一个java HashMap 底层源码解析的文章。

阿里，腾讯，字节的面试官最爱问的HashMap，这次直接连底层原理都帮你搞懂了