算法小专栏:散列表(一)

栏目: 编程工具 · 发布时间: 5年前

内容简介:散列函数:简单来说是一个函数,传入一个对不同的关键字可能得到同一散列地址,即

散列表(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(简书)

QiShare(掘金)

QiShare(知乎)

QiShare(GitHub)

QiShare(CocoaChina)

QiShare(StackOverflow)

QiShare(微信公众号)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

中国网络媒体的第一个十年

中国网络媒体的第一个十年

彭兰 / 清华大学出版社 / 2005-7 / 35.00元

此书对中国网络媒体的第一个十年这一重要的历史阶段首次进行了全景式、全程式的历史记录,并进行了全面深入的研究,在一定程度上填补了中国网络媒体发展史宏观研究方面的空白。对于网络新闻传播的研究,以及当代中国媒体发展的研究.具有重要的意义。 ——方汉奇 图书目录 绪论 1 第一章 投石问路:中国网络媒体萌芽(1994一1995年) 9 第一节 从实验室走向市场:互联网兴起 10 ......一起来看看 《中国网络媒体的第一个十年》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

MD5 加密
MD5 加密

MD5 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具