Hash——哈希法概念、哈希函数构造⽅法、哈希冲突解决办法（重点讨论链地 址法）
声明：本篇博客根据回顾⽼师上课知识和书籍《数据结构——⽤C语⾔描述》（耿国华）整理得出，仅作知识回顾学习⽤。
1.哈希法
哈希法⼜称散列法、杂凑法、关键字地址计算法。相对应的表称为哈希表、散列表、或杂凑表等。 哈希⽅法思想：
供配电系统设计
⾸先在元素的关键字k和元素的存储位置p之间建⽴⼀个对应关系H，使得 p = H(k)，H成为哈希函数。创建哈希表时，把关键字为k的元素直接存⼊地址为H(k)的单元，以后查关键字为k的元素时，再利⽤哈希函数计算该元素的存储位置。再按关键字存取元素。Hash中存储的key值都是唯⼀的。
哈希冲突：
当关键字集合很⼤的时候，关键字值不同的元素可能会映射到哈希表的同⼀个地址，即k1 != k2，H(k1)
== H(k2)，这种现象称为冲突，此时k1和k2为同义词。事实上冲突是不可避免的，由于关键字可能发⽣冲突的集合远远⼤于实际开辟的哈希表长度 ，构成冲突的必然性，可通过改进哈希的性能来减少冲突，即降低冲突的可能性。
2.哈希函数的构造⽅法
构造哈希函数原则：
（1）函数本⾝便于计算
（2）计算出来的地址分布均匀，即对应任意⼀个关键字k，H(k)对应的不同地址的概率应该相同，以尽可能减少冲突
在实际应⽤中，构造哈希函数要考虑以下五个因素：
（1）计算哈希函数所需要的时间。哈希函数⼀定要简单，取放key值都需要根据哈希函数和key值计算位置，计算是要花时间的，尽可能要计算简单⼀点，这样计算时间也会少。
（2）关键字的长度。关键字过长，我们可以考虑取关键的某⼏位来建⽴哈希函数。
（3）哈希表的⼤⼩。哈希表可以减少查次数，但是哈希表过短，或者过长都会使哈希法性能降低。
（4）关键字分布情况。为了使key值和哈希函数计算出来的地址分布均匀，要考虑关键字分布情况建⽴合适哈希函数。
（5）记录查的频率。
2.1数字分析法
⽅法：
⾸先⼤概了解关键字集合。如果每个关键字的位数⽐哈希表的地址码位数多时，可以从key值选择分布均匀的若⼲位，构成哈希地址。
⽐如哈希表长度为100，即地址空间为0~99，如果有200个key值，且key值都是8位⼗进制数d1d2d3d4d5d6d7d8，那么我们可以选择分布较均匀的两位数字作为key值。⽐如说所有key中，第⼆位和第五位数字都分布较均匀（即200个key值的第⼆位第五位都⽐较随机），那么我们就取d2d5作为key值地址码，⽐如 34982748，地址码为42。
（在这⾥存在不相同的key值，但是地址码⼀样，这是哈希冲突，哈希冲突解决办法在最后给出。哈希表，⼀个地址码可以代表（存放）⼀组数据）。
2.2平⽅取中法
⽅法：
当⽆法确定关键字中哪⼏位分布较均匀时，可以求出关键字的平⽅值，再结合哈希表长度，取平⽅值的中间⼏位作为哈希地址（⽐如哈希表长度是 100，那哈希地址就00-99，我们就取key值平⽅后的中间2位作为地址码；如果哈希表长度是1000，那么哈希地址可以是000-999，那么就取key值平⽅后的中间3位作为地址码）。这是因为完成平⽅运算后，中间⼏位和关键字的每⼀位都相关，所以不同关键字会以较⾼的概率产⽣不同的哈希地址。
2.3分段叠加法
按哈希表地址位数将关键字分成位数相等的⼏部分（最后⼀部分可以较短），然后将这些部分相加，舍弃最⾼进位，剩下的数字作为地址码。⽐如哈希表长度为1000，可以表⽰地址码000-999。我们就把key值分成三位数为⼀部分。具体折叠⽅法有移位法和折叠法。以为叠加法直接将每⼀部分相加。折叠叠加法是将奇数段和偶数段分开，奇数段（偶数段）正常，偶数段（奇数段）倒序，再相加。
举例：12360324711202065
2.4除留余数法
顾名思义，即对key值进⾏取余。看有多少key值，如果有⼏⼗个key值，我们可以选择对10取余，对15取余，等等。余数就是对应的地址码。
其实不论什么⽅法，⽬的都是为了在保证哈希函数尽可能简单的情况下让key值计算出来的地址码尽可能均匀。即让哈希表起到提⾼查效率的作⽤。所以不管什么⽅法，只要达到最终这个⽬的就⾏。
2.5伪随机数法
即⽤⼀个为随机函数作为哈希函数p = H(key) = random(key)。
3.处理冲突的⽅法
坎儿井英文3.1开放定址法
也叫做再散列法。cat计算机辅助
思想：当关键字key的初始哈希地址p0 = H(key)出现冲突时（即该地址有key值了），以p0为基础，产⽣另⼀个地址p1，如果p1仍然冲突，再以p0为基础，产⽣另⼀个哈希地址p2…直⾄到⼀个不冲突的地址pi，将key值存到⾥⾯。生态健康
即hi = (h0 + di)%m
m为表长，m为增量序列
（1）线性探测再散列
di = 1,2,3,4,…,m-1
（2）⼆次探测再散列
di = 1^2, -1^2, 2^2, -2^2,…, k^2, -k^2(k <= m/2)
3.2再哈希法
同时构造多个不同的哈希函数：
中国人民解放军第四军医大学Hi = RHi(key)
哈希地址H1 = RH1(key)差⽣冲突时，再计算H2 = RH2(key)…直到冲突不再产⽣。
3.3建⽴公共溢出区
哈希表分为基本表和溢出表两部分，凡是和基本表发⽣冲突的元素⼀律填⼊溢出表。
3.4链地址法
哈希表⾥每个表格是⼀个地址码和⼀个指针。将对应的key值都放在（key，指针）这种空间中，连接在对应的地址码后⾯。⽐如我们哈希表的地址码是key值对10取余。
有数10，12 ，32，34，92，33，11，67，那么都映射到哈希表上，对应的结构为
结构体类型如下：
#define TABLESIZE 10
typedef int KeyType;// 键值的类型
typedef struct
{
KeyType key;// 学⽣信息学号
//....其他数据成员姓名
//....其他数据成员
}DataType;// 存储的数据类型
typedef struct
{
DataType key;
湖南卫视成人礼KeyNode* next;
}KeyNode;//key以这种结点⽅式被连接
typedef struct Node
{
int addcode;//地址码（0，1，2，3， (9)
KeyNode* next;//指向KeyNode类型的结点}List;//哈希表每个格⼦的结构
typedef struct Hash
{
List* hash_table[TABLESIZE];
}ListHash;//哈希表
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议