算法与数据结构基础 – 哈希表(Hash Table)

• 2019 年 10 月 3 日
• 筆記

Hash Table基础

哈希表(Hash Table)是常用的数据结构，其运用哈希函数(hash function)实现映射，内部使用开放定址、拉链法等方式解决哈希冲突，使得读写时间复杂度平均为O(1)。

HashMap(std::unordered_map)、HashSet(std::unordered_set)的原理与Hash Table一样，它们的用途广泛、用法灵活，接下来侧重于介绍它们的应用。

相关LeetCode题：

705. Design HashSet  题解

集合

如果仅需要判断元素是否存在于某个集合，我们可以使用结构HashSet(std::unordered_set)。例如 LeetCode题目 349. Intersection of Two Arrays：

    // 349. Intersection of Two Arrays      vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {          unordered_set<int> s1(nums1.begin(),nums1.end());          unordered_set<int> s2(nums2.begin(),nums2.end());          vector<int> res;          for(auto& a:s1)              if(s2.count(a)) res.push_back(a);          return res;      }

相关LeetCode题：

349. Intersection of Two Arrays  题解

202. Happy Number  题解

720. Longest Word in Dictionary  题解

970. Powerful Integers  题解

36. Valid Sudoku  题解

计数

如果需要对元素进行计数，我们可以使用结构HashMap(std::unordered_map)，元素如取值范围固定可以用Array(std::vector)，例如LeetCode题目 217. Contains Duplicate：

    // 217. Contains Duplicate      bool containsDuplicate(vector<int>& nums) {          unordered_map<int,int> m;          for(int x:nums) if(m[x]++==1) return true;          return false;      }

相关LeetCode题：

811. Subdomain Visit Count  题解

266. Palindrome Permutation  题解

748. Shortest Completing Word  题解

451. Sort Characters By Frequency  题解

454. 4Sum II  题解

30. Substring with Concatenation of All Words  题解

在滑动窗口算法中常使用HashMap计数，关于滑动窗口算法，详见：算法与数据结构基础 – 滑动窗口(Sliding Window)

Key-Val

进一步地，HashMap表示一种Key-Val (或ID-属性) 关系，这里Val可以是计数、下标(index)等等。

相关LeetCode题：

219. Contains Duplicate II  题解

953. Verifying an Alien Dictionary  题解

1086. High Five  题解

981. Time Based Key-Value Store  题解

244. Shortest Word Distance II  题解

355. Design Twitter  题解 

映射

更一般地，HashMap表示一种映射关系，意义在于O(1)时间复杂度完成由 A->B 的映射。

相关LeetCode题：

205. Isomorphic Strings  题解

49. Group Anagrams  题解

249. Group Shifted Strings  题解

290. Word Pattern  题解

535. Encode and Decode TinyURL  题解

HashMap与Prefix sum

利用HashMap和Prefix sum，我们可以在O(n)时间复杂度求解一类子序列求和问题，其中HashMap用于计数，例如LeetCode题目 560. Subarray Sum Equals K：

    // 560. Subarray Sum Equals K      int subarraySum(vector<int>& nums, int k) {          unordered_map<int,int> m;          m[0]=1;          int sum=0,res=0;          for(auto& a:nums){              sum+=a;              res+=m[sum-k];              m[sum]++;          }          return res;      }

相关LeetCode题：

560. Subarray Sum Equals K  题解

525. Contiguous Array  题解

930. Binary Subarrays With Sum  题解

325. Maximum Size Subarray Sum Equals k  题解

554. Brick Wall  题解

HashMap与图形问题

HashMap可以应用于二维图形的一些问题求解，以欧拉距离、斜率、x/y坐标等为key，以计数、x/y坐标为val。图形问题中HashMap的映射关系不是那么直观和明显，需要单独计算key、仔细甄别映射关系。

相关LeetCode题：

447. Number of Boomerangs  题解

939. Minimum Area Rectangle  题解

149. Max Points on a Line  题解

    // 380. Insert Delete GetRandom O(1)      vector<int> v;      unordered_map<int,int> m;