Python 数据结构入门 - 哈希表(Hash Table)
18年9月10日 · Python123 25669 人阅读
哈希
散列(哈希)是电脑科学中一种对资料的处理方法,通过某种特定的函数/算法(称为散列函数/算法)将要检索的项与用来检索的索引(称为散列,或者散列值)关联起来,生成一种便于搜索的数据结构(称为散列表)。
哈希表是什么
哈希表(散列表)是根据键(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 字典吧
Python3Turtle