哈希表基础

基本概念

  1. 哈希表又称为散列表，是根据关键码的值而直接进行访问的数据结构。
  2. 哈希表解决的问题是：快速判断一个元素是否在一个集合中，
  3. HashFunction = HashCode(name) % tableSize。也就是说，把各种数据格式（name）转化为索引，就可以实现快速访问了。
  4. 当不同的数据被映射到同一个哈希表上时，出现哈希碰撞，解决哈希碰撞的基本方法有：
  • 拉链法：把发生冲突的元素存储到链表中。
  • 线性探测法：向下找一个空位存放对应信息。

常见哈希结构

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)
映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)
  1. 是否有序：红黑树是一种平衡二叉树，树的节点是有序的，而哈希表的实现是无序的。
  2. 数值是否可以重复：只有multiset和multimap可以重复。
  3. 能否更改数值：三种实现都不能更改数值。

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

1
2
3
4
5
6
7
8
bool isAnagram(string s, string t) {
        unordered_map<char,int> map;
        for(char c:s)   map[c] ++;
        for(char c:t)   map[c] --;
        for(char c:s)   if(map[c])  return false;
        for(char c:t)   if(map[c])  return false;
        return true;
    }

核心就在于构造char到int的哈希映射。

两个数组的交集

给定两个数组，计算它们的交集。

此题用set不难实现，主要是学习一下STL的set容器以及方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
构造函数

set()：创建一个空的set。
set(const set& other)：拷贝构造函数，创建一个与other一样的新set。
set(set&& other)：移动构造函数，将other的内容移动到新创建的set中。
赋值操作

operator=(const set& other)：拷贝赋值运算符，用另一个set的拷贝替换当前内容。
operator=(set&& other)：移动赋值运算符，用另一个set的内容替换当前内容。
迭代器

begin() / cbegin()：返回指向第一个元素的迭代器。
end() / cend()：返回指向集合末尾的迭代器。
容量

empty()：检查set是否为空。
size()：返回set中元素的个数。
修改操作

clear()：移除所有元素，清空set。
insert(const value_type& value)：插入元素。
insert(value_type&& value)：移动插入元素。
erase(iterator pos)：移除位于指定位置的元素。
erase(const key_type& key)：移除指定键的元素。
swap(set& other)：与另一个set交换内容。
查找操作

count(const key_type& key)：返回某个值在set中出现的次数（由于set中元素唯一，结果为0或1）。
find(const key_type& key)：查找键为指定值的元素，如果找到，则返回一个指向该元素的迭代器，否则返回end()。
equal_range(const key_type& key)：返回一个范围，包含所有与指定键相等的元素。
)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1;
        set<int> s2;
        vector<int> ans;
        for (int i:nums1)
            s1.insert(i);
        for (int i:nums2)
            s2.insert(i);
        for (int i:s1){
            if (s2.find(i)!= s2.end())
                ans.push_back(i);
        }
        return ans;
    }

核心在于运用set的自动去重功能。

但是这个题是可以展开思考的，如果交集是可重复集合，那么我们就可以构造unordered_map来记录数组中每个元素出现的次数，首先记录一个数组中元素出现的次数，然后遍历另一个数组中的元素，将非零的计数器的值减1并放入结果vector中即可。