【数据结构3】hash
source link: https://www.guofei.site/2017/09/18/hash.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【数据结构3】hash
2017年09月18日Author: Guofei
文章归类: 8-数据结构与算法 ，文章编号: 503
版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2017/09/18/hash.html
几个概念
哈希函数
数据中的关键字映射到存放位置的映射函数叫做 哈希函数 。
哈希冲突
Ki,Kj(i≠j)是两个关键字。 把Ki≠Kj,并且h(Ki)=h(Kj)现象叫做哈希冲突，
这样的Ki,Kj叫做 同义词
哈希冲突的可能性与三个因素有关：
- 填装因子α。设已存入数据个数为n，哈希地址空间大小m，α=nm
- 哈希函数。如果选择得当，可以使哈希地址尽可能均匀分布在地址空间上。
- 哈希冲突函数：为解决
哈希冲突问题，有哈希冲突函数，哈希冲突函数的选取也影响哈希冲突的可能性
几个经典哈希函数
余数法
关键字K，哈希表长度为m，那么：
h(K)=Kmodm
优点：
算法简单，适用范围广
如果关键字均匀，那么映射到每个地址的概率也均匀，减少了哈希冲突的概率
直接定址法
关键字K加上某个常量C
h(K)=K+C
优点：
计算简单
不可能有哈希冲突
缺点： 如果有1~1000的7个数字需要存放，可能需要1000个内存单元，造成大量浪费
数值分析法
分析数据内容，找出比较均匀的位（可以是多个），组合成为哈希地址
例如，某组数据有1000个数字，这些数字第1,3,6位取值比较均匀，那么可以提取1,3,6位，组成一个三位数作为哈希地址
哈希冲突的解决方法
开放定址法
非同义关键字 ： 开放定址法中，为了把某个发生哈希冲突的数据放到另一个空闲单元d中，因为对应的关键字的哈希值不为d，所以称为非同义关键字
开放定址法中，哈希空闲单元既向同义关键字开放，又向非同义关键字开放，至于填入哪个，要看谁先占用它
非同义词冲突 在解决哈希冲突时，如果Ki≠Kj(i≠j),h(Ki)≠h(Kj), 但哈希冲突函数h1(Ki)=h(Kj)，这种现象叫做非同义词冲突
开放定址法有以下几种：
1.线性探查法
d位置发生哈希冲突时，依次探查d的下一个地址。如果探查到哈希表尾部(m-1)时，下一个探查0位置.
{d0=h(K)di=(di−1+1)modm
缺点是容易产生堆积问题，如果连续出现几个同义词后，将连续占用哈希表的内存单元
2.平方探查法
{d0=h(K)di=(di−1+2i−1)modm
3.伪随机数法
{d0=h(K)di=(di−1+R)modm
其中，R是一个伪随机数
链表法
如果没有发生哈希冲突，直接存放该数据。
如果发生了哈希冲突，把冲突的数据放到链表中
您的支持将鼓励我继续创作！
Recommend
-
101
Developer community programs DevFest 2020 - Oct 16-18, 2020. Sign up at
-
106
-
50
-
81
I recently got an itch to design my own non-cryptographic integer hash function. Firstly, I wanted tobetter understand how hash functions work, and the best way to learn is to do. For years I’d been treating them like ma...
-
43
-
34
Note that no matter which you call, you should get the same result — they are not different hash functions, just different implementations of the same Meow hash function that uses different CPU register sizes....
-
69
hashABC hash是一种用于处理查找时非常高效的数据结构。时间复杂度一般情况下可以直接认为是O(1)。 散列技术是在记录的存储位置和它的关键字之间确立一个对应关系 f，使得关键字 key对应的存储位置 f(key)。函数 f被称...
-
4
酱油瓶20.6122019.03.17 08:36:19字数 3,267阅读 7,6591. 什么是Hash表 先看一下hash表的结构图： image.png
-
5
0x00 前言 多阶（级）Hash 是我司使用最普遍的数据结构，常用于海量数据（如 UIN、关系链等）的存储，此外，结合 Linux 共享内存机制，可以方便的实现在游戏后台中保存用户状态（进程崩溃恢复）。 0x01...
-
4
Redis 哈希Hash底层数据结构 1. Redis 底层数据结构
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK