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

Hash Table基础

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

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

相关LeetCode题：

集合

如果仅需要判断元素是否存在于某个集合，我们可以使用结构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 题解

771. Jewels and Stones 题解

202. Happy Number 题解

166. Fraction to Recurring Decimal 题解

720. Longest Word in Dictionary 题解

970. Powerful Integers 题解

204. Count Primes 题解

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题：

217. Contains Duplicate 题解

811. Subdomain Visit Count 题解

1002. Find Common Characters 题解

266. Palindrome Permutation 题解

242. Valid Anagram 题解

748. Shortest Completing Word 题解

1072. Flip Columns For Maximum Number of Equal Rows 题解

451. Sort Characters By Frequency 题解

347. Top K Frequent Elements 题解

454. 4Sum II 题解

781. Rabbits in Forest 题解

30. Substring with Concatenation of All Words 题解

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

Key-Val

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

相关LeetCode题：

1. Two Sum 题解

219. Contains Duplicate II 题解

953. Verifying an Alien Dictionary 题解

359. Logger Rate Limiter 题解

1086. High Five 题解

690. Employee Importance 题解

981. Time Based Key-Value Store 题解

325. Maximum Size Subarray Sum Equals k 题解

244. Shortest Word Distance II 题解

355. Design Twitter 题解

336. Palindrome Pairs 题解

映射

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

相关LeetCode题：

246. Strobogrammatic Number 题解

205. Isomorphic Strings 题解

49. Group Anagrams 题解

249. Group Shifted Strings 题解

290. Word Pattern 题解

138. Copy List with Random Pointer 题解

535. Encode and Decode TinyURL 题解

710. Random Pick with Blacklist 题解

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 题解

356. Line Reflection 题解

HashMap与vector/list/stack结合

HashMap与vector、list、stack等数据结构可以结合成为复合数据结构，这样可以既用到HashMap O(1)的优点，也用到vector支持下标操作、list增删节点快、stack先进后出的特点。例如 LeetCode题目 380. Insert Delete GetRandom O(1)：

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

以上用vector存储元素，unordered_map存储元素和对应下标；getRandom函数利用vector下标操作，而删除元素时，使用unordered_map取得被删元素、将vector末尾元素与其对调，利用了HashMap O(1)的优点。

相关LeetCode题：

380. Insert Delete GetRandom O(1) 题解

381. Insert Delete GetRandom O(1) - Duplicates allowed 题解

895. Maximum Frequency Stack 题解

146. LRU Cache 题解

bangerlee

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