C++中的哈希表

最近刷题经常使用到哈希表。

哈希表

官方定义:

哈希表是根据关键码的值而直接进行访问的数据结构。

数组其实就是一张最基础的哈希表。

它的下标数字作为键(key)对应一个值(value)。

比如:

a[key] = value;

键不能相同，但值可以相同。

哈希表可以用来快速检索一个元素。

比如我们拿学生的名字作为键(key)，ta所在的宿舍作为值(key)。

我们要查询一个学生在哪个宿舍，只需要，

dormitory = student[name]

但是数组的下标访问本质是编程语言的一个语法糖。(详情见数组与指针)

而name大部分情况下并不是数字。

所以我们需要一个哈希函数，能够把任意信息变成一串数字。

例如:

小李 ----> 0
小王 ----> 1
小张 ----> 2
……

然后再直接操纵下标就能读取数据了。

// 存储数据
student["小李"] = "c1";
// 读取数据
cout << student["小李];

-----
output:
c1

但数字是有一定范围的，由于是从无穷集映射到有限集。

所以有可能会出现不同的键映射到同一个索引。

这就是哈希碰撞。

哈希碰撞

有两种方法解决这个问题。

拉链法

如果发生了哈希碰撞，可以将冲突的数据用链表连起来。

这样就可以通过遍历来找出冲突的值。

不过这样查找性能可能会产生损耗。

线性探测法

如果发生哈希碰撞，将冲突的数据移去空位就行了。

这样在插入数据时会产生性能损耗。

C++中的哈希表

C++的STL标准模版库中的unordered_map就是哈希表。

~~map是基于红黑树实现的~~

定义

unordered_map<string, string> umap;

修改

umap[key] = value

如果key不存在会创建一个。

查找

umap[key]

直接访问key对应的value值。

umap.find(key)

返回指向符合要求key的迭代器，若未找到会返回umap.end()。

umap.count(key)

返回umap中对应key值的个数，返回1或0。常用于判断哈希表内是否存在某个key。

umap.empty()

如果哈希表为空返回true，反之为false。

删除

umap.erase(key)

移除指定位置处的元素。

umap.clear()

删除所有元素。

迭代器

it->first

it指向的键。

it->second

it指向的值。

注意，若想根据值来反查对应的键需要遍历整个哈希表！

小结

这篇博客当个笔记来看，以后要用到什么函数就查一下。