内容简介:散列函数:简单来说是一个函数,传入一个对不同的关键字可能得到同一散列地址,即
散列表(Hash table,也叫哈希表) 是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 这个映射函数叫做 散列函数 ,存放记录的数组叫做 散列表 。(来源360百科)
二、内部机制
2.1 散列函数:
散列函数:简单来说是一个函数,传入一个 Key
就返回一个固定的数。该数即为散列表数组的下标。( 用一句话描述:散列函数将“输入”映射到“数字”。 )
2.2 解决冲突:
对不同的关键字可能得到同一散列地址,即 k1≠k2
,而 f(k1)=f(k2)
,这种现象称为冲突(碰撞)。
常见的解决哈希冲突方案有以下四种:(详细细节见 下篇 讲解)
-
开放定址法:为产生冲突的地址
H(key)
求得一个新的地址序列:Hi =(H(key)+ di)% m
(i=1,2,3,...,m-1) 其中H(key)
为哈希函数,m
为表长,di
称为增量序列。(其中增量di
的取值方法也有多种,详细细节见 下篇 ) -
链地址法:将所有哈希地址相同的记录都链接在同一 链表 中。
-
再哈希法:产生冲突时计算**另一个哈希函数(散列函数)**的地址,直到冲突不再发生为止。
-
建立公共溢出区:把冲突的值都放在另一个溢出表中,不把冲突的值存原表中。
三、性能对比
先介绍一个散列表的专有名词: 填装因子 ( 负载因子 )。
这里列出了常见数据结构操作的时间复杂度。
/ | 散列表(最佳情况) | 散列表(最坏情况) | 数组 | 链表 |
---|---|---|---|---|
取值 | O(1) | O(n) | O(1) | O(n) |
插入 | O(1) | O(n) | O(n) | O(1) |
删除 | O(1) | O(n) | O(n) | O(1) |
可以看出散列表在最佳情况下的性能是很出色的,虽然最坏情况的性能不好,但我们可以通过一些手段避免掉最坏情况。因此,散列表的最优情况就是平均情况,时间复杂度为常数级O(1)。
因此,散列表在使用中需要注意两点:
- 较低的 填装因子 (或称 负载因子 )。(建议:高于
0.7
时,考虑散列表翻倍扩容) - 优秀的 散列函数 。(尽量减少冲突的发生)
PS:Python的做法是,会设法保证大概还有三分之一的表元是空的,当快要达到这个阀值的时候,会进行扩容,将原散列表复制到一个更大的散列表里。
四、应用实例
例如,用散列表实现一个电话薄。
主要功能如下:
- 加入联系人及电话号码。
- 通过查找对应名称首字母,得到所有该首字母名称的联系人。
图解如下:
代码如下:
# 创建一个telBook的散列表 telBook = dict() # 将A-Z的字母作为telBook的Key,Value还是一个散列表 for ch in xrange(0x41, 0x5A): telBook[unichr(ch)] = dict() # 将联系人加入telBook中,取首字母作为第一个Key,名称作为第二个Key,电话作为第二个Key的Value。 def addFriend(name, phoneNumber): telBook[name[0:1]][name] = phoneNumber addFriend("QiShare1", 13800000000) addFriend("QiShare2", 13811111111) addFriend("QiShare3", 13822222222) addFriend("QiShare4", 13833333333) addFriend("QiShare5", 13844444444) addFriend("QiShare6", 13855555555) addFriend("Police", 110) addFriend("XiaoMing1", 1) addFriend("XiaoMing2", 2) addFriend("XiaoMing3", 3) # 输出结果: for ch in xrange(0x41, 0x5A): if telBook[unichr(ch)]: print unichr(ch)+":" print telBook[unichr(ch)] 复制代码
打印结果如下:
小编微信:可加并拉入《QiShare技术交流群》。
关注我们的途径有:
QiShare(微信公众号)
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
程序员的数学思维修炼(趣味解读)
周颖 / 清华大学出版社 / 2014-4-1 / 45.00元
本书是一本专门为程序员而写的数学书,介绍了程序设计中常用的数学知识。本书门槛不高,不需要读者精通很多高深的数学知识,只需要读者具备基本的四则运算、乘方等数学基础知识和日常生活中的基本逻辑判断能力即可。本书拒绝枯燥乏味的讲解,而是代之以轻松活泼的风格。书中列举了大量读者都很熟悉,而且非常有趣的数学实例,并结合程序设计的思维和算法加以剖析,可以训练读者的数学思维能力和程序设计能力,进而拓宽读者的视野,......一起来看看 《程序员的数学思维修炼(趣味解读)》 这本书的介绍吧!