本文共 1554 字,大约阅读时间需要 5 分钟。
哈希表
今天的内容没有代码,只是来简单介绍一下哈希表!
1. 定义
哈希表:
- 哈希表(Hash Table,又称为散列表),是一种线性表的存储结构。
- 哈希表由一个直接寻址表和一个哈希函数组成。
- 哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。
例子:
假设有一个长度为7的哈希表,哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图
哈希表一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:
- insert(key, value): 插入键值对(key,value)
- get(key): 如果存在键为key的键值对则返回其value,否则返回空值
- delete(key): 删除键为key的键值对
2. 为嘛使用哈希表?
直接寻址表: key为k的元素放到k位置上
直接寻址技术缺点:
- 当域U很大时,需要消耗大量内存,很不实际
- 如果域U很大而实际出现的key很少,则大量空间被浪费
- 无法处理关键字不是数字的情况
改进直接寻址表——哈希(Hashing)
- 构建大小为m的寻址表T
- key为k的元素放到h(k)位置上
- h(k)是一个函数,其将域U映射到表T[0,1,…,m-1] 可以见1中的例子!
3. 哈希冲突
哈希冲突:由于哈希表的大小是有限的,而要存储的值的总数量是无限的,因此对于任何哈希函数,都会出现两个不同元素映射到同一个位置上的情况,这种情况叫做哈希冲突。比如h(k)=k%7, h(0)=h(7)=h(14)=…
1. 解决哈希冲突——开放寻址法
开放寻址法:如果哈希函数返回的位置已经有值,则可以向后探查新的位置来
存储这个值。
- 线性探查:如果位置i被占用,则探查i+1, i+2,…
- 二次探查:如果位置i被占用,则探查 i + 1 2 , i − 1 2 , i + 2 2 , i − 2 2 . . . . . . . i+1^{2}, i-1^2,i+2^2,i-2^2....... i+12,i−12,i+22,i−22.......
- 二度哈希:有n个哈希函数,当使用第1个哈希函数h1发生冲突时,则尝试使用h2,h3,…
2. 解决哈希冲突——拉链法
拉链法:哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后。
4. 常见哈希函数
- 除法哈希: h(k)=k % m
- 乘法哈希法: h(k) = floor(m*(A*key%1))
- 全域哈希: h_a_b(k)= ((a*key + b) mod p) mod m a,b = 1,2,…,p-1
5. 哈希表的应用
1. 哈希表的应用——集合与字典
字典与集合都是通过哈希表来实现的。
例子:
a= { 'name': 'Alex', 'age': 18, 'gender': 'Man'}使用哈希表存储字典,通过哈希函数将字典的键映射为下标。假设h('name') =3, h('age')= 1, h('gender')= 4,则哈希表存储为[None, 18, None, 'Alex, 'Man']
如果发生哈希冲突,则通过拉链法或开发寻址法解决
2. 哈希表的应用——md5算法
MD5(Message- -Digest Algorithm 5)曾经是密码学中常用的哈希函数,可以把任意长度的数据映射为128位的哈希值,其曾经包含如下特征:
- 同样的消息,其MD5值必定相同;
- 可以快速计算出任意给定消 息的MD5值;
- 除非暴力的枚举所有可能的消息,否则不可能从哈希值反推出消息本身;
- 两条消息之间即使只有微小的差别,其对应的MD5值也应该是完全不同、完全不相关的;
- 不能在有意义的时间内人工的构造两个不同的消息使其具有相同的MD5值。
转载地址:http://sbiwi.baihongyu.com/