哈希表的原理与实现
哈希表
哈希表(Hash table)又称散列表,是一种可以通过"关键码” (key) 直接进行访问的数据结构。
哈希表由两部分组成
- 一个数据结构,通常是链表、数组
- Hash函数,输入“关键码” (key) ,返回数据结构的索引
对外表现为可以通过关键码直接访问: hash_ table[key] = value
实际上是在数据结构的hash(key)位置处存储了value: data_ structure[hash(key)] = value
最简单的例子,关键码是整数,定义hash(key) = key
那这个哈希表其实就是一一个数组了，key 自己就是下标
当然，一般情况下，关键码key是一个比较复杂的信息，比如很大的数、字符串
这时候key就不能直接作为数据结构的下标了
此时就需要设计一个Hash函数,把复杂信息映射到一个较小的值域内，作为索引
一个简单的hash _table[“ies”]= 233的例子，以各字符ASCII码相加mod 20为Hash函数
哈希碰撞
哈希碰撞(Collisions) 指的是两个不同的key被计算出同样的Hash结果
把复杂信息映射到小的值域，发生碰撞是不可避免的
好的Hash函数可以减少碰撞发生的几率,让数据尽可能地均衡分布
开散列是最常见的碰撞解决方案
- Hash函数依然用于计算数组下标
- 数组的每个位置存储一个链表的表头指针(我们称它为表头数组)
- 每个链表保存具有同样 Hash值的数据
形象描述:“挂链” 一表头数组每个位置 “挂”着一个链表
哈希碰撞 + 开散列
工程应用
- 电话号码簿
- 用户信息表
- 缓存(LRUCache)
- 键值对存储(Redis)
完整结构图
时间复杂度
- 期望:插入、查询、删除0(1)
- 数据分布比较均衡时 - 最坏:插入、查询、删除0(n)
- 数据全部被映射为相同的Hash值时
无序集合、映射的实现与应用
集合与映射
集合(set) 存储不重复的元素
- 有序集合, 遍历时按元素大小排列，一般用平衡二叉搜索树实现, 0(logN)
- 无序集合，一般用hash实现，0(1)
映射(map)存储关键码(key) 不重复的键值对(key-value pair)
- 有序集合, 遍历时按照key大小排列，一般用平衡二叉搜索树实现, O(logN)
- 无序集合，一般用哈希表实现，0(1)
对于语言内置的类型(int, string) ,已经有默认的优秀的hash函数，可以直接放进set/map
里使用
C++ code
set与unordered_ set
- unordered_ set S;
- insert, find, erase, clear等方法
- multiset
map与unordered_ map
- unordered_map h;
- h[key] = value
- find(key), erase(key), clear等方法
- multimap
Java code
Set:不重复元素的集合
- HashSet<…> set = new HashSet<>()
- set.add(value)
- set.contains(value)
- set.remove(value)
Map: key-value对， key不重复
- HashMape<…,…> map = new HashMap<>()
- map.put(key, value)
- map.get(key)
- map.remove(key)
- map.clear()
Python code
list_ a= list([1,2,3, 4])
集合
set_ a = {‘jack’, ‘selina’, ‘Andy’}
set_ b= set(list_ _a)
字典
map_ a= {
‘Jack’: 100,
‘张三’: 80,
‘Candela’: 90,
}
实战
1.两数之和
https://leetcode.cn/problems/two-sum/description/
基本思路:枚举一个数x, 找它前面有没有target-x
所以建立一个数值到下标的hash map就可以了
对于每个数x,先查询target-x，再插入x
时间复杂度0(n)
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0;i < nums.size(); i++){ if(h.find(target - nums[i]) != h.end()) { return {h[target - nums[i]],i }; } h[nums[i]] = i; } return {}; } private: unordered_map<int,int> h; };
874.模拟行走的机器人
https://leetcode.cn/problems/walking-robot-simulation/
可以用set或者map存储障碍物，从而快速判断一个格子里有没有障碍
可以利用方向数组简化实现(代替if)
class Solution { public: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) { unordered_set<long long> obstacles_set; for(auto obstacle : obstacles){ obstacles_set.insert(callHash(obstacle)); } int ans = 0; int dir=0; int x=0; int y=0; int dx[4] = {0 ,1, 0, -1}; int dy[4] = {1, 0, -1, 0}; for(int i=0; i < commands.size() ;i++){ if(commands[i] == -2){ dir = (dir + 3) % 4; }else if(commands[i] == -1){ dir = (dir + 1) % 4; }else{ for(int step = 0;step < commands[i]; step++){ int nx = x + dx[dir]; int ny = y + dy[dir]; if( obstacles_set.find(callHash({nx , ny})) != obstacles_set.end()){ break; } x = nx; y = ny; ans = max(ans,x * x + y * y); } } } return ans; } private: long long callHash(vector<int> obstacle){ return (obstacle[0] + 30000) *60000ll +(obstacle[1] + 30000); } };
49.字母异位词分组
https://leetcode.cn/problems/group-anagrams/
对字符串分组，其实就是进行Hash
让同一组的字符串具有相同的Hash函数值,不同组的字符串具有不同的Hash函数值
然后就可以用hash map分组了
方案一: 把每个字符串中的字母排序，排序后的串作为hash map的key
map
方案二:统计每个字符串中各字母出现次数,把长度为26的计数数组作为key
map, group> (C++ std::array, Python tuple)
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { for(string& s : strs) { string copy = s; sort(copy.begin(), copy.end()); groups[copy].push_back(s); } vector<vector<string>> ans; for(const pair<string, vector<string>> & group : groups) { ans.push_back(group.second); } return ans; } private: unordered_map<string, vector<string>> groups; };
30.串联所有单词的子串
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
遇到难题，先分解
不会求解，可以先想想判定:
给出一个s的子串、words,判定这个子串是不是words的串联?
把子串划分以后，其实就是比较两个Hash map是否相等
“barfoothefoobarman” mapA= {“bar”: 1, “foo”: 1}
[“oo”,“bar”] mapB ={“bar”: 1, “foo”: 1}
mapA ?= mapB
回到原问题:
枚举子串的所有起始位置, 0(length of s * total length of words)
barfoothefoobarman→barfoothefoobarman >…
枚举部分起始位置+滑动窗口，O(length of s * length of one word)
barfoothefoobarman→barfoothefoobarman→…
barfoothefoobarman→barfoothefoobarman→…
…
class Solution { public: vector<int> findSubstring(string &s, vector<string> &words) { vector<int> res; int m = words.size(), n = words[0].size(), ls = s.size(); for (int i = 0; i < n && i + m * n <= ls; ++i) { unordered_map<string, int> differ; for (int j = 0; j < m; ++j) { ++differ[s.substr(i + j * n, n)]; } for (string &word: words) { if (--differ[word] == 0) { differ.erase(word); } } for (int start = i; start < ls - m * n + 1; start += n) { if (start != i) { string word = s.substr(start + (m - 1) * n, n); if (++differ[word] == 0) { differ.erase(word); } word = s.substr(start - n, n); if (--differ[word] == 0) { differ.erase(word); } } if (differ.empty()) { res.emplace_back(start); } } } return res; } };
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ans; int tot =0; for(string& word:words){ tot+=word.length(); wordsMap[word]++; } for(int i=0;i+tot<=s.length();i++){ if(valid(s.substr(i,tot),words)){ ans.push_back(i); } } return ans; } private: //怎么看两个数组含有一样的元素,字符排序,字符串比较有问题,统计次数,hash bool valid(string str, vector<string>& words){ //分解是不是好点,不是n阶乘 int k = words[0].length(); //vector<string> splitWords; unordered_map<string,int> splitWordsMap; for(int i=0;i<str.length();i+=k){ //splitWords.push_back(str.substr(i,k)); splitWordsMap[str.substr(i,k)]++; } return equalsMap(splitWordsMap,wordsMap); } bool equalsMap(unordered_map<string,int> &a,unordered_map<string,int> &b){ for(auto& key_and_value : a){ const string &key=key_and_value.first; int value = key_and_value.second; if(b.find(key) == b.end() || b[key] != value) return false; } for(auto& key_and_value : b){//严谨 const string &key=key_and_value.first; int value = key_and_value.second; if(a.find(key) == a.end() || a[key] != value) return false; } return true; } unordered_map<string,int> wordsMap; };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
