|
参考引用
Hello 算法 Github：hello-algo
1. 哈希表
1.1 哈希表概述
哈希表（hash table），又称散列表，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询
具体而言，向哈希表输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 如下图所示，给定 n 个学生，每个学生都有 “姓名” 和 “学号” 两项数据。假如希望实现 “输入一个学号，返回对应的姓名” 的查询功能，则可以采用下图所示的哈希表来实现
除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下图所示
在哈希表中进行增删查改的时间复杂度都是 O(1)，非常高效
1.2 哈希表常用操作
哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等
/* 1、初始化哈希表 */
unordered_map map;
/* 2、添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";
/* 3、查询操作 */
// 向哈希表输入键 key ，得到值 value
string name = map[15937];
/* 4、删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);
哈希表有三种常用遍历方式：遍历键值对、遍历键和遍历值/* 5、遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
cout |