安全防护的打印机为攻击者打开了大门

1 哈希表

哈希表属于编程中比较常见的数据结构之一，基本上所有的语言都会实现数组和哈希表这两种结构，Hash table 的历史是比较悠远的，我们在编程时也是离不开的，这种数据结构的作用其实很简单，就是我们可以根据一个 key 可以查找到对应的 value，也就是说这种数据结构存储的是键值对的“列表”。

1.1 原理

首先哈希表中第一个点就是哈希函数，也就是我们需要一个函数，根据我们的 key 计算出一个值，然后根据这个值可以直接找到对应的 value。因为我们的哈希表的一个作用就是 O(1) 复杂度找到 key 对应的 value。

完美的哈希函数是可以做到将任何一个 key 值都可以计算出一个唯一且固定大小的值，不幸的是目前世界上还没有这种完美的哈希函数。因此我们需要解决的另外一个问题就是哈希冲突的解决。

1.1.1 哈希冲突

假如我们有两个不同的 key，通过哈希函数计算出的结果相同，那么我们是不能认为这两个 key 在 map 中是相同的，也就是如果出现了这种情况，我们的 map 结构是可以解决这个问题的。目前解决办法有很多，这里只说三个比较常见的解决方案：

开放地址法(Open Addressing)：

• 写入时：假如 key Alice 与 Bob 通过哈希函数计算出结果冲突。当 map 中已经存在 key Alice，再写入 key 为 Bob时，发现哈希结果对应位置已经存在 Alice，此时在 Alice 位置之后再寻找位置，一直找到为空的位置，将 Bob 写入。
• 读取时：此时 map 中已存在 key Alice、Bob，且哈希结果相同，此时想查找 Bob 对应 value 时，先计算 Bob 哈希结果，再通过哈希结果在 map 中查找位置，此时由于和 Alice 哈希结果相同，并且 Alice 先于 Bob 存入 map，所以会直接找到 Alice 的位置，发现 key 是 Alice 不是 Bob，接着在 Alice 位置后面查找，直到找到 key Bob 或者找到空。

再哈希法(Re-Hashing)：

• 设计多个哈希函数，假如 Alice 与 Bob 计算哈希结果相同，那么用另外一个哈希函数来计算 Bob 的哈希值，这种方式来解决哈希冲突。
• 链地址法(Separate Chaining)：
• 此方法将同一个哈希结果对应的位置想象成一个桶，如果多个 key 对应哈希结果相同，那么都放到同一个桶中，并且桶中元素使用链表结构存储。
• 写入时：Alice 于 Bob 哈希结果相同，此时 map 已经有 Alice，再写入 Bob 时，发现对应哈希结果位置已经存在了 Alice，此时在当前桶中的 Alice 后链接一个 Bob，此时哈希结果对应的桶就存在了两个元素 Alice 与 Bob。
• 读取时：读取 Bob key 时，发现对应哈希结果的桶中第一个元素是 Alice，此时在桶中按链表顺序挨个查找，直到 key 相同或者空。
• 装载因子：此方案存在一个问题，当一个桶中元素过多时，其复杂度将增加，极端情况下就变成了链表。所以我们会限制在一个桶中元素的个数。这样在一个桶中元素过多时，需要生成新的桶。
• 装载因子 = 元素总量 / 桶总个数

在 Go 语言中，map 使用的是链地址法。

2 Go 中 map分析

2.1 map 数据结构

（编辑：宜春站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!