Python 数据结构入门 - 哈希表（Hash Table）

哈希

散列（哈希）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。

哈希表是什么

哈希表（散列表）是根据键（Key）直接访问内存存储位置的数据结构。根据键（Key）值将数据映射到内存中一个位置的函数称为哈希函数，根据哈希函数建立的记录数据的表称为哈希表。

哈希表的特点

• 若关键字为 k，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。
  

• 对不同的关键字可能得到同一散列地址，即 k1≠k2，而 f(k1) = f(k2) ，这种现象称为冲突。

• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

处理冲突

开放定址法

开放定址法就是产生冲突之后去寻找下一个空闲的空间。函数定义为：

其中，hash(key) 是哈希函数，di 是增量序列，i 为已冲突的次数。

• 线性探测法：di= i ，或者其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，然后放置在该单元。
• 平方探测法：

链表法

这是另外一种类型解决冲突的办法，散列到同一位置的元素，不是继续往下探测，而是在这个位置是一个链表，这些元素则都放到这一个链表上。

再散列

如果一次不够，就再来一次，直到冲突不再发生。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(注意：在这个方法里面是把元素分开两个表来存储)。

哈希表的应用

• 查字典
  
• 网络防火墙中，根据源IP，目的IP，源端口，目的端口，协议号构成的五元组来标识一条网络数据流的，并且根据五元组来建立会话表项(session entry)。为了查找便捷，一般都使用Hash表来实现这个会话表，以提高转发的效率。
• Linux 内核大量采用哈希表

动手试一试

下面用开放地址法（线性探测）实现了一个简单的哈希表。仔细阅读后试试哈希表的各种操作，感受以下哈希表飞一般的速度吧！

代码段 1

上述代码实现了一个简单的哈希表，但表的长度只有11，填入表中元素越来越多后，产生冲突的可能性会越来越大。

由此引出另一个概念，叫做载荷因子（load factor）。载荷因子的定义为：

在上述代码中重新升级我们的 Hash 吧！示例代码代码段2中。

代码段 2

经典实践

Python 中的字典就是用哈希表来实现的，它的特点如下：

• 字典的每个键值 key=>value 对用冒号 : 分割，每个键值对之间用逗号 , 分割，整个字典包括在花括号 {} 中 ,格式：dict = {key1 : value1, key2 : value2 }
• 通过中括号访问，添加，更新元素

根据 Python 中的字典特性，自己手动实现一个 Python 字典吧