python实现散列表的直接寻址法
2023-09-11 14:17:11 时间
散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,
将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表,在首字母为W的表中查找“王”姓的电话号码,
显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则,存放首字母的表对应散列表。关键字和函数法
则理论上可以任意确定。
它仅支持插入,查找和删除三类字典操作,在散列表中查找一个元素的时间在最坏的情况下是O(n),这和链表的操作时间一致。在实际中,散列
的效率是非常高的,最高的查找期望时间为O(1)
在关键字的全域U比较小时,直接寻址是一种简单有效的方法。具体思路是取关键字或关键字的某个线性函数值为散列地址。即{hash(k)=k}或
{hash(k)=a*k+b},其中{a,b}为常数(这种散列函数叫做自身函数)
python语言是非常简洁的,我把python源码和算法导论的伪码对比发现,这伪码到python源码几乎可以算是一一对应,所以,我这里就贴出了
python源码,即直观又简洁:
KEYS = (12,6554,12345,34234,234234,6456456,34234,67645,2343432,23423,1343324) DELETED = -1 m=len(KEYS) T=[None for _ in range(m)] def h1(k): return k % m def HASH_INSERT(T,k): j=h1(k) if T[j]==None or T[j]==DELETED: T[j]=k return j def HASH_SEARCH(T,k): j=h1(k) if T[j] == k: return j if T[j]==None: return None def HASH_DELETE(T,k): i=HASH_SEARCH(T,k) if i is None: raise Exception("key %s doesn't exist"%k) T[i]=DELETED if __name__=='__main__': for k in KEYS: HASH_INSERT(T,k) print "all keys:" print(T) print "every key:" for k in KEYS: print(k,HASH_SEARCH(T,k)) print "del key1:" HASH_DELETE(T,KEYS[1]) print(T) print "none keys:" for k in KEYS: if HASH_SEARCH(T,k) is None: print(k) print "insert key1:" HASH_INSERT(T,KEYS[1]) print(T)
运行结果:
all keys: [234234, 12, 34234, 12345, 23423, None, 6456456, None, None, 6554, None] every key: (12, 1) (6554, 9) (12345, 3) (34234, 2) (234234, 0) (6456456, 6) (34234, 2) (67645, None) (2343432, None) (23423, 4) (1343324, None) del key1: [234234, 12, 34234, 12345, 23423, None, 6456456, None, None, -1, None] none keys: 6554 67645 2343432 1343324 insert key1: [234234, 12, 34234, 12345, 23423, None, 6456456, None, None, 6554, None]
相关文章
- Python中的列表List
- python零基础数据分析入门
- 我都30了,还能不能转行学python?
- 将自己OpenCV-Python-PyCharm开发环境的Python-3.6.8更换为python-3.9.10的详细过程记录
- python yield 用法详解
- 《python 与数据挖掘 》一1.3 Python开发环境的搭建
- Python: random
- gyp ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- Python中的列表
- python列表推导式,字典推导式,集合推导式详细介绍
- 二叉树的深度优先遍历和广度优先遍历-Python
- python 入门
- 《趣学Python编程》——2.4 你学到了什么
- 《Python核心编程(第二版)》——1.3 特点
- Python迭代和解析(1):列表解析
- Python 数据分析教程之如何验证线性回归的假设,线性回归的假设是什么?以及如何用python验证它们?
- python之unittest单元测试
- 华为OD机试 -单词接龙(Python)| 真题+思路+考点+代码+岗位
- Python 爬虫 之 爬取王者荣耀的英雄们所有大皮肤图片,并 json 形式保存英雄列表信息到本地
- 【python养成】:re模块正则表达式详解
- [Python]2分钟完成python + Selenium Web端自动化环境搭建,开启~~~
- Python 取列表的前几个