第三课：哈希表、集合、映射【C++】

1. 哈希表

哈希表(hash table)又称散列表&＃xff0c;是一种可以通过“关键码”(key)直接进行访问的数据结构。
哈希表由两部分组成

• 一个数据结构&＃xff0c;通常是链表、数组
• hash函数&＃xff0c;输入“关键码”(key)&＃xff0c;返回数据结构的索引

对外表心啊喂可以通过关键码直接访问&＃xff1a;hash_table[key] &＃61; value
实际上是在数据结构的hash(key)位置存储了value: data_structure[hash(key)] &＃61; value

最简单的例子&＃xff0c;关键码是整数&＃xff0c;定义hash(key) &＃61; key
那这个哈希表其实就是一个数组了&＃xff0c;key自己就是下标

当然一般情况下&＃xff0c;关键码key是一个比较复杂的信息&＃xff0c;比如很大的数、字符串&＃xff0c;这时候key就不能直接作为数据结构的下标了。
此时就需要设计要给Hash函数&＃xff0c;把复杂的信息映射到一个较小的值域内&＃xff0c;所谓索引

例子&＃xff1a;

对外表现为字符串lies&＃xff0c;实际存储为233的整数。设计哈希函数hash_table["lies"] &＃61; ASCII &＃43;&＃43; % 20 &＃61; 9哈希函数令输入lies映射到9这个索引&＃xff0c;然后9的下标索引对应的数值为233

哈希碰撞

哈希碰撞(Collisions)指的是两个不同的key被计算出同样的hash结果

把复杂信息映射到小的值域&＃xff0c;发生碰撞是不可避免的

好的hash函数可以减少碰撞发生的几率&＃xff0c;让数组尽可能的均匀分布

开散列是最常见的碰撞解决方案

• hash函数依然用于计算数组下标
• 数组的每个位置存储一个链表的表头指针&＃xff08;成为表头数组&＃xff09;
• 每个链表保存具有同样hash值的数据

形象描述&＃xff1a;“挂链”——表头数组每个元素“挂”着一个链表。数组套链表

工程应用

• 电话号码簿
• 用户信息表
• 缓存&＃xff08;LRU Cache&＃xff09;
• 键值对存储 (Redis)

开散列完整结构图

时间复杂度

• 期望&＃xff1a;插入、查询、删除O(1)
  • 数据分布比较均匀时
• 最坏&＃xff1a;插入、查询、删除O(n)
  • 数据全部被映射为相同的hash值时

2. 集合与映射

集合&＃xff08;set&＃xff09;存储不重复的元素

• 有序集合&＃xff0c;遍历时按元素大小排列&＃xff0c;一般用平衡二叉搜索树实现&＃xff0c;O(logN)
• 无序集合&＃xff0c;一般用hash实现&＃xff0c;O(1)

映射&＃xff08;map&＃xff09;存储关键码&＃xff08;key&＃xff09;不重复的键值对&＃xff08;key-value pair&＃xff09;

• 有序集合&＃xff0c;遍历时按照key大小排列&＃xff0c;一般用平衡二叉搜索树实现&＃xff0c;O(logN)
• 无序集合&＃xff0c;一般用哈希表实现&＃xff0c;O(1)

对于语言内置的类型&＃xff08;int , string&＃xff09;&＃xff0c;已经有默认的优秀的hash函数&＃xff0c;可以直接放进set/map中使用

C&＃43;&＃43; code

set与unordered_set

• 文档
• Unordered_set s;
• insert, find, erase, clear等方法
• multiset

map与unordered_map

• 文档
• Unordered_map h
• h[key] &＃61; value
• find(key), erase(key), clear等方法
• multimap

实战

1 两数之和https://leetcode-cn.com/problems/two-sum/

/*
- 建立值到下标的映射
- 边循环查询&＃xff0c;边插入&＃xff0c;每次只查询i前面的映射
- 维护nums[0, i - 1]
- 防止查询到i本身
*/


874 模拟行走机器人https://leetcode-cn.com/problems/walking-robot-simulation/

/*
- 可以用set或者map存储障碍物&＃xff0c;从而快速判断一个格子里有没有障碍
- 利用方向数组简化实现(代替if)
*/


49 字母异位词分组https://leetcode-cn.com/problems/group-anagrams/

/*
- 对字符串的分组就是用hash&＃xff0c;让同一组的字符串拥有相同的hash值&＃xff0c;然后用hash map分组
- 思路1&＃xff1a;重新排序-->分组-->提取到ans- map
-思路2: 统计每个字符串中每个字母的出现的次数&＃xff0c;把长度为26的计数数组作为key- map
- 熟悉map的用法
- 字符串排序
- map的插入
*/


30 串联所有单词的子串https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

/*
长度相同&＃xff1a;滑动窗口长度固定
中间不能有其他字符&＃xff1a;连续判定word
不需要考虑顺序&＃xff1a;hash
思路&＃xff1a; 比较滑动窗口的map和输入的words的map是否相等&＃xff0c;考虑单词的重复
滑动窗口- 窗口size &＃61; words.size() * words[0].size()
对words建hash map */- // words的单词到次数的映射unordered_map word_to_times;for (string& word : words){word_to_times[word] &＃43;&＃61; 1&＃xff1b;}


set、map的使用及其特性和区别

STL总共实现了两种不同结构的管理式容器&＃xff1a;树型结构与哈希结构。树型结构的关联式容器主要有四种&＃xff1a;set&＃xff0c;map&＃xff0c;multiset&＃xff0c;multimap。下面介绍一下这四种容器的简单使用。

1.set

set里面每个元素只存有一个key值&＃xff0c;它支持高效的关键字查询操作&＃xff0c;比如检查一个关键字是否在set中。如果这个key值之前存在的话就不插入。

简单使用如下&＃xff1a;
插入&＃xff1a;

set s;s.insert(2);s.insert(1);s.insert(4);s.insert(5);s.insert(3);s.insert(5);s.insert(5);s.insert(5);s.insert(5);s.insert(5);for (auto e : s){cout <

插入如上数据之后&＃xff0c;打印出来的值为1 2 3 4 5。set容器自动对以上数据进行了排序&＃xff0c;并且实现了去重。但是不能对set里的值进行修改。

查找&＃xff1a;

//时间复杂度&＃xff1a;O(logN)----底层是搜索树
set::iterator pos &＃61; s.find(3);
//时间复杂度&＃xff1a;O(N)----需要遍历一遍&＃xff08;不建议使用&＃xff09;
//set::iterator pos &＃61; find(s.begin(), s.end(), 3);
if (pos !&＃61; s.end())
{cout <<"找到了" <

set容器中的find查找效率高&＃xff0c;因为底层是一个二叉搜索树&＃xff0c;比要查找的值小就去左子树查找&＃xff0c;反之则去右子树查找。

删除&＃xff1a;

//s.erase(3);
s.erase(pos);//找到了我就删&＃xff0c;没找到要删的话会报错


采用s.erase(3);这种操作如果没有3并不会报错&＃xff0c;如果有3则会删除这个结点。
找到pos位置&＃xff0c;采用s.erase(pos);这种操作如果没有3则会报错&＃xff0c;如果有3则会删除这个结点。

交换&＃xff1a;

set ss;
ss.insert(6);
ss.insert(9);
ss.insert(8);
ss.insert(7);
ss.insert(10);ss.swap(s);//交换根节点的指针&＃xff0c;效率高


两个set的交换的其实是交换结点的指针&＃xff0c;效率高。

清空&＃xff1a;

s.clear();//清掉所有数据


遍历方法&＃xff1a;

//新式for循环
for (auto e : s)
{cout <}
cout <set::iterator sit &＃61; s.begin();
while (sit !&＃61; s.end())
{cout <<*sit <<" ";sit&＃43;&＃43;;
}
cout <

推荐大家使用新式for循环~比较简单一些٩(๑❛ᴗ❛๑)۶

2. multiset

其实整体的接口和set都相同&＃xff0c;但是multiset可以插入key相同的值。

multiset ms;
ms.insert(2);
ms.insert(1);
ms.insert(4);
ms.insert(5);
ms.insert(3);
ms.insert(5);
ms.insert(5);
ms.insert(5);
ms.insert(5);
ms.insert(5);for (auto e : ms)//可以重复插入相同key值
{cout <}
cout <if (pos !&＃61; ms.end())
{cout <<"找到了" <}--pos;//倒数第一个5
ms.erase(pos);for (auto e : ms)//可以重复插入相同key值
{cout <}
cout <

multiset允许key的冗余&＃xff0c;如果用find查找key值时&＃xff0c;找到的是中序遍历第一个&＃xff0c;因此不断遍历下午可以找到这个multiset里所有的key值。

multiset和set一样不能够对数据进行修改。

3.map

有别于set的是&＃xff0c;map是一种key(键),value(值)的形式&＃xff0c;用来保存键和值组成的集合&＃xff0c;键必须是唯一的&＃xff0c;但值可以不唯一。里面的元素可以根据键进行自动排序&＃xff0c;由于map是key_value的形式&＃xff0c;所以map里的所有元素都是pair类型。pair里面的first被称为key(键&＃xff09;&＃xff0c;second被称为value(值&＃xff09;。

它可以通过关键字查找映射关联信息value&＃xff0c;同时根据key值进行排序。

相关类型的返回值

//成员类型 含义
key_type The first template parameter (Key)
mapped_type The second template parameter (T)
value_type pair


简单的使用如下&＃xff1a;
插入&＃xff1a;

map dict;
dict.insert(pair("string", "字符串"));//模板类型pair&＃xff1a;构造了一个匿名对象插入到map
dict.insert(make_pair("apple", "苹果"));//模板函数make_pair&＃xff1a;偷懒了&＃xff0c;实际调的是pair
dict.insert({ "left", "左边" });
dict.insert({ "left", "剩余" });//插入不进去了&＃xff0c;因为key值已经有了


插入有三种方法&＃xff1a;

采用创建pair的形式插入pair(“string”, “字符串”)
采用make_pair的形式进行插入make_pair(“apple”, “苹果”)
采用大括号的形式进行插入{ “left”, “左边” }
遍历方法&＃xff1a;

//新式for循环
for (const auto &e : dict)
{cout <}
cout <map::iterator mit &＃61; dict.begin();
while (mit !&＃61; dict.end())
{cout <first <<":" <second <}


打印出来为&＃xff1a;&＃xff08;根据key值进行了排序和key值的去重&＃xff09;

operator[ ]&＃xff1a;
// operator[]可以通过key值找到对应的value值。并且还可以使用operator[]插入数据。dict["banana"];
// 如上&＃xff0c;插入一个pair&＃xff0c;这个pair的key值为“banana”&＃xff0c;value为空字符串(\0)dict["key"] &＃61; "关键字";
// 如上&＃xff0c;插入一个pair&＃xff0c;这个pair的key值为“key”&＃xff0c;value为“关键字”dict["left"] &＃61; "剩余";
// 如上&＃xff0c;因为本来map里“left”这个key值&＃xff0c;所以operator[]找到了这个key值&＃xff0c;将它的value改成“剩余”。


4.multimap

// multimap允许key值的冗余&＃xff0c;因此key值相同也可以进行插入。multimap mmp;
mmp.insert(pair("left", "左边"));
mmp.insert(make_pair("key","关键字"));
mmp.insert({ "map", "地图" });
mmp.insert({ "left", "剩余" });for (const auto &e : mmp)
{cout <}


set和map特性和区别
set是一种关联式容器&＃xff0c;其特性如下&＃xff1a;

• set以RBTree作为底层容器

• 所得元素的只有key没有value&＃xff0c;value就是key

• 不允许出现键值重复

• 所有的元素都会被自动排序

• 不能通过迭代器来改变set的值&＃xff0c;因为set的值就是键

• map和set一样是关联式容器&＃xff0c;它们的底层容器都是红黑树&＃xff0c;区别就在于map的值不作为键&＃xff0c;键和值是分开的。它的特性如下&＃xff1a;

  • map以RBTree作为底层容器
  • 所有元素都是键&＃43;值存在
  • 不允许键重复
  • 所有元素是通过键进行自动排序的
  • map的键是不能修改的&＃xff0c;但是其键对应的值是可以修改的