Hash Table

Introduction

哈希表（hash table），又称散列表，它通过哈希算法建立键 key 与值 value 之间的映射，实现高效的元素查询。

简单的说，我们可以直接将value存储在hash(key)的地方，之后查询直接到hash(key)的地方查询。此时，哈希表 添加/删除/查询 元素的时间复杂度都是O(1)。然而，不同的key之间，hash(key)是会发生冲突的。解决冲突就是哈希表的核心内容，如果冲突解决的不好，实际时间复杂度会退化到O(n)。

冲突解决算法有：

• 链式地址算法：对于相同的hash(key)，他们会存在一个链表中。增删改查就需要遍历这个链表。
• 开放寻址（open addressing）不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。

此外，对于哈希表来说，他希望哈希算法拥有下面的特性：

• 效率高：计算哈希值的过程应该足够快。计算开销越小，哈希表的实用性越高。
• 均匀分布：哈希算法应使得键值对均匀分布在哈希表中。分布越均匀，哈希冲突的概率就越低。

![Note]
哈希碰撞攻击：针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表（链式地址算法）。所以，在某些特殊的场景，还要让哈希函数具备一些抗碰撞性。

Usage

几乎所有的现代编程语言标准库中都内置了 哈希表。

另外，在许多编程语言中，只有不可变对象才可作为哈希表的 key 。原因也很简单，如果hash(key) 发生变化，那么怎么找到 value ？