哈希表概览与操作

在计算机世界中，哈希表如同一位聪慧的图书管理员，他知道如何计算索书号，从而可以快速找到目标图书。

「哈希表 hash table」，又称「散列表」，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。例如，给定 n 个学生，每个学生都有“姓名”和“学号”两项数据。假如希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用哈希表来实现。

• 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 O(1) 时间。
• 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 O(n) 时间。
• 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 O(n) 时间。

	数组	链表	哈希表
查找元素	O(n)	O(n)	O(1)
添加元素	O(1)	O(1)	O(1)
删除元素	O(n)	O(n)	O(1)

哈希表常用操作

（1）哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等，示例代码如下：

/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
string name = map[15937];

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);

（2）哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。示例代码如下：

/* 遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
    cout << kv.first << " -> " << kv.second << endl;
}
// 使用迭代器遍历 key->value
for (auto iter = map.begin(); iter != map.end(); iter++) {
    cout << iter->first << "->" << iter->second << endl;
}

（3）计算哈希值

certutil 是一个 Windows 命令行工具，通常用于管理、查看证书。不过，它也包含了一些其他功能，比如计算文件的哈希值。

certutil -hashfile filename algorithm
# e.g.
certutil -hashfile ffmpeg_version.cmake MD5

#powershell
Get-FileHash -Path "D:\program\fc\sources\.cache\ffmpeg\ffmpeg_version.cmake" -Algorithm MD5