哈希表（HashTable）散列表（Key-Value）
⽬录
　哈希表（Hash Table）是⼀种特殊的数据结构，它最⼤的特点就是可以快速实现查、插⼊和删除。因为它独有的特点，Hash表经常被⽤来解决⼤数据问题，也因此被⼴⼤的程序员所青睐。为了能够更加灵活地使⽤Hash来提⾼我们的代码效率，今天，我们就谈⼀谈Hash的那点事。
1. 哈希表的基本思想
  我们知道，数组的最⼤特点就是：寻址容易，插⼊和删除困难；⽽链表正好相反，寻址困难，⽽插⼊和删除操作容易。那么如果能够结合两者的优点，做出⼀种寻址、插⼊和删除操作同样快速容易的数据结构，那该有多好。这就是哈希表创建的基本思想，⽽实际上哈希表也实现了这样的⼀个“夙愿”，哈希表就是这样⼀个集查、插⼊和删除操作于⼀⾝的数据结构。
2. 哈希表的相关基本概念
  1.概念
  哈希表（Hash Table）：也叫散列表，是根据关键码值（Key-Value）⽽直接进⾏访问的数据结构，也就是我们常⽤到的map。
  哈希函数：也称为是散列函数，是Hash表的映射函数，它可以把任意长度的输⼊变换成固定长度的输出，该输出就是哈希值。哈希函数能使对⼀个数据序列的访问过程变得更加迅速有效，通过哈希函数数据元素能够被很快的进⾏定位。
  2.哈希表和哈希函数的标准定义
  若关键字为k，则其值存放在f(k)的存储位置上。由此，不需⽐较便可直接取得所查记录。称这个对应关系f为哈希函数，按这个思想建⽴的表为哈希表。
  设所有可能出现的关键字集合记为U(简称全集)。实际发⽣(即实际存储)的关键字集合记为K（|K|⽐|U|⼩得多）。
  散列⽅法是使⽤函数h将U映射到表-1]的下标上（m=O(|U|)）。这样以U中关键字为⾃变量，以h为函数的运算结果就是相应结点的存储地址。从⽽达到在O(1)时间内就可完成查。
  其中：
  ① h：U→{0，1，2，…，m-1} ，通常称h为哈希函数(Hash Function)。哈希函数h的作⽤是压缩待处理的下标范围，使待处理
的|U|个值减少到m个值，从⽽降低空间开销。
  ② T为哈希表(Hash Table)。
  ③ h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。
种子哈希转换链接  ④ 将结点按其关键字的哈希地址存储到哈希表中的过程称为散列(Hashing)
  1）冲突：
  两个不同的关键字，由于散列函数值相同，因⽽被映射到同⼀表位置上。该现象称为冲突(Collision)或碰撞。发⽣冲突的两个关键字称为该散列函数的同义词(Synonym)。
  2）安全避免冲突的条件：
  最理想的解决冲突的⽅法是安全避免冲突。要做到这⼀点必须满⾜两个条件：
  ①其⼀是|U|≤m
  ②其⼆是选择合适的散列函数。
  这只适⽤于|U|较⼩，且关键字均事先已知的情况，此时经过精⼼设计散列函数h有可能完全避免冲突。
  3）冲突不可能完全避免
  通常情况下，h是⼀个压缩映像。虽然|K|≤m，但|U|>m，故⽆论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的⽅法，使发⽣冲突的同义词能够存储到表中。
  4）影响冲突的因素
  冲突的频繁程度除了与h相关外，还与表的填满程度相关。
  设m和n分别表⽰表长和表中填⼊的结点数，则将α=n/m定义为散列表的装填因⼦(Load Factor)。α越⼤，表越满，冲突的机会也越⼤。通常取α≤1。
3. 哈希表的实现⽅法
  我们之前说了，哈希表是⼀个集查、插⼊和删除操作于⼀⾝的数据结构。那这么完美的数据结构到底是怎么实现的呢？哈希表有很多种不同的实现⽅法，为了实现哈希表的创建，这些所有的⽅法都离不开两个问题——“定址”和“解决冲突”。
  在这⾥，我们通过详细地介绍哈希表最常⽤的⽅法——取余法（定值）+拉链法（解决冲突），来⼀起窥探⼀下哈希表强⼤的优点。
  取余法⼤家⼀定不会感觉陌⽣，就是我们经常说的取余数的操作。
  拉链法是什么，“拉链”说⽩了就是“链表数组”。我这么⼀解释，⼤家更晕了，啥是“链表数组”啊？为了更好地解释“链表数组”，我们⽤下图进⾏解释：图中的主⼲部分是⼀个顺序存储结构数组，但是有的数组元素为空，有的对应⼀个值，有的对应的是⼀个链表，这就是“链表数组”。⽐如数组0的位置对应⼀个链表，链表有两个元素“496”和“896”，这说明元素“496”和“896”有着同样的Hash地址，这就是我们上边介绍的“冲突”或者“碰撞”。但是“链表数组”的存储⽅式很好地解决了Hash表中的冲突问题，发⽣冲突的元素会被存在⼀个对应Hash地址指向的链表中。实际上，“链表数组”就是⼀个指针数组，每⼀个指针指向⼀个链表的头结点，链表可能为空，也可能不为空。
  说完这些，⼤家肯定已经理解了“链表数组”的概念，那我们就⼀起看看Hash表是如何根据“取余法+拉链法”构建的吧。
  将所有关键字为同义词的结点链接在同⼀个链表中。若选定的散列表长度为m，则可将散列表定义为⼀个由m个头指针组成的指针数组-1]。凡是散列地址为i的结点，均插⼊到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因⼦α可以⼤于1，但⼀般均取α≤1。
  举例说明拉链法的执⾏过程，设有⼀组关键字为(26，36，41，38，44，15，68，12，6，51)，⽤取余法构造散列函数，初始情
况如下图所⽰：
  最终结果如下图所⽰：
  理解了Hash表的创建，那根据建⽴的Hash表进⾏查就很容易被理解了。
  查操作，如果理解了插⼊和删除，查操作就⽐较简单了，令待查的关键字是x，也可分为⼏种情况：
  1）x所属的Hash地址未被占⽤，即不存在与x相同的Hash地址关键字，当然也不存在x了；
  2）x所属的Hash地址被占⽤了，但它所存的关键不属于这个Hash地址，与1）相同，不存在与x相同H
ash地址的关键字；
  3）x所属的Hash地址被占⽤了，且它所存的关键属于这个Hash地址，即存在与x相同sHash地址的关键字，只是不知这个关键字是不是x，需要进⼀步查。
  由此可见，Hash表插⼊、删除和插⼊操作的效率都相当的⾼。
  思考⼀个问题：如果关键字是字符串怎么办？我们怎么根据字符串建⽴Hash表？
  通常都是将元素的key转换为数字进⾏散列，如果key本⾝就是整数，那么散列函数可以采⽤keymod tablesize（要保证tablesize是质数）。⽽在实际⼯作中经常⽤字符串作为关键字，例如⾝姓名、职位等等。这个时候需要设计⼀个好的散列函数进程处理关键字为字符串的元素。参考《数据结构与算法分析》第5章，有以下⼏种处理⽅法：
  ⽅法1：将字符串的所有的字符的ASCII码值进⾏相加，将所得和作为元素的关键字。设计的散列函数如下所⽰：
int hash(const string& key,int tablesize)
{
int hashVal = 0;
for(int i=0;i<key.length();i++)
hashVal += key[i];
return hashVal % tableSize;
}
  此⽅法的缺点是不能有效的分布元素，例如假设关键字是有8个字母构成的字符串，散列表的长度为10007。字母最⼤的ASCII码为127，按照⽅法1可得到关键字对
  ⽅法2：假设关键字⾄少有三个字母构成，散列函数只是取前三个字母进⾏散列。设计的散列函数如下所⽰：
int hash(const string& key,int tablesize)
{
//27 represents the number of letters plus the blank
return (key[0]+27*key[1]+729*key[2])%tablesize;
}
  该⽅法只是取字符串的前三个字符的ASCII码进⾏散列，最⼤的得到的数值是2851，如果散列的长度为10007，那么只有28%的空间被⽤到，⼤部分空间没有⽤到
  ⽅法3：借助Horner's 规则，构造⼀个质数（通常是37）的多项式，（⾮常的巧妙，不知道为何是37）。计算公式为:key[keysize-i-
1]*37i, 0<=i<keysize求和。设计的散列函数如下所⽰：
int hash(const string & key,int tablesize)
{
int hashVal = 0;
for(int i =0;i<key.length();i++)
hashVal = 37*hashVal + key[i];
hashVal %= tableSize;
if(hashVal<0) //计算的hashVal溢出
hashVal += tableSize;
return hashVal;
}
该⽅法存在的问题是如果字符串关键字⽐较长，散列函数的计算过程就变长，有可能导致计算的hashVal溢出。针对这种情况可以采
取字符串的部分字符进⾏计算，例如计算偶数或者奇数位的字符。
4. 哈希表“定址”的⽅法
  其实常⽤的“定址”的⼿法有“五种”：
  1）直接定址法
  很容易理解，key=Value+C；这个“C"是常量。Value+C其实就是⼀个简单的哈希函数。
  2）除法取余法
  key=value%C
  3）数字分析法
  这种蛮有意思，⽐如有⼀组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数⽐较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。
  4）平⽅取中法
  5）折叠法
  举个例⼦，⽐如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，然后去掉⾼位“1”，此时key=60，哈哈，这就是他们的哈希关系，这样做的⽬的就是key与每⼀位value都相关，来做到“散列地址”尽可能分散的⽬地。
  影响哈希查效率的⼀个重要因素是哈希函数本⾝。当两个不同的数据元素的哈希值相同时，就会发⽣冲突。为减少发⽣冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每⼀个表项中。
5. 哈希表“解决冲突”的⽅法
  Hash表解决冲突的⽅法主要有以下两种： 
  1）开放地址法 
  如果两个数据元素的哈希值相同，则在哈希表中为后插⼊的数据元素另外选择⼀个表项。当程序查哈希表时，如果没有在第⼀个对应的哈希表项中到符合查要求的数据元素，程序就会继续往后查，直到到⼀个符合查要求的数据元素，或者遇到⼀个空的表项。
  开放地址法包括线性探测、⼆次探测以及双重散列等⽅法。其中线性探测法⽰意图如下：
  散列过程如下图所⽰：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。