Hash表

【引入】

网上看到的比喻
我们有很多的小猪，每个的体重都不一样，假设体重分布比较平均(我们考虑到公斤级别)，我们按照体重来分,划分成100个小猪圈。 
然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。

好了，如果我们要找某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？ 
当然不需要了。

我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。 
在这个猪圈里的小猪的数量就相对很少了。 
我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。

对应于hash算法。 
就是按照hashcode分配不同的猪圈，将hashcode相同的猪放到一个猪圈里。 
查找的时候，先找到hashcode对应的猪圈，然后在逐个比较里面的小猪。

所以问题的关键就是建造多少个猪圈比较合适。

如果每个小猪的体重全部不同（考虑到毫克级别)，每个都建一个猪圈，那么我们可以最快速度的找到这头猪。缺点就是，建造那么多猪圈的费用有点太高了。

如果我们按照10公斤级别进行划分，那么建造的猪圈只有几个吧，那么每个圈里的小猪就很多了。我们虽然可以很快的找到猪圈，但从这个猪圈里逐个确定那头小猪也是很累的。

所以，好的hashcode，可以根据实际情况，根据具体的需求，在时间成本(更多的猪圈，更快的速度)和空间本(更少的猪圈，更低的空间需求)之间平衡。

【哈希表】

定义

哈希表（Hash Table）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。因为它独有的特点，Hash表经常被用来解决大数据问题，也因此被广大的程序员所青睐。

哈希表的基本思想

　　我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构。这就是哈希表创建的基本思想，而实际上哈希表也实现了这样的一个“夙愿”，哈希表就是这样一个集查找、插入和删除操作于一身的数据结构。

哈希表的相关基本概念

　　在介绍Hash之前，首先我们要搞明白几个概念：

　　哈希表（Hash Table）：也叫散列表，是根据关键码值（Key-Value）而直接进行访问的数据结构，也就是我们常用到的map。

　　哈希函数：也称为是散列函数，是Hash表的映射函数，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。哈希函数能使对一个数据序列的访问过程变得更加迅速有效，通过哈希函数数据元素能够被很快的进行定位。

　　哈希表和哈希函数的标准定义：

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为哈希函数，按这个思想建立的表为哈希表。

　　设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。

　　散列方法是使用函数h将U映射到表T[0..m-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)

　冲突：

　　两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。

　　2）安全避免冲突的条件：

　　最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：

　　①其一是|U|≤m

　　②其二是选择合适的散列函数。

　　这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。

　　3）冲突不可能完全避免

　　通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。

　　4）影响冲突的因素

　　冲突的频繁程度除了与h相关外，还与表的填满程度相关。

设m和n分别表示表长和表中填入的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。

5)解决方法

处理冲突的方法

哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希造表不可缺少的另一方面。
假设哈希表的地址集为0～(n-1)，冲突是指由关键字得到的哈希地址为j(0≤j≤n-1)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi , i=1，2，…，k， ( Hi∈[0,n-1])。即在处理哈希地址的冲突时，若得到的另一个哈希地址H1仍然发生冲突，则再求下一个地址H2，若H2仍然冲突，再求得H3。依次类推，直至Hk不发生冲突为止，则Hk为记录在表中的地址。通常用的处理冲突的方法有下列几种：
   

 1．开放定址法

    Hi=(H(key)+di)MOD m         i=1，2，…，k (k≤m-1) (9-25)
    其中：H(key)为哈希函数；m为哈希表表长；di为增量序列，可有下列三种取法：
        (1)di=1，2，3，…，m-1，称线性探测再散列；
        (2)di=12，-12，22，-22，33，…，±k2，(k≤m/2)称二次探测再散列；
        (3)di=伪随机数序列，称伪随机探测再散列。

[例如]，在长度为11的哈希表中已填有关键字分别为17，60，29的记录(哈希函数 H(key)=key MOD11)，现有第四个记录，其关键字为38


    从上述线性探测再散列的过程中可以看到一个现象：当表中i，i+1，i+2位置上已填有记录时，下一个哈希地址为i、i+1，i+2和i+3的记录都将填入j+3的位置，这种在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象称作“二次聚集”，即在处理同义词的冲突过程中又添加了非同义词的冲突，显然，这种现象对查找不利。

但另一方面，用线性探测再散列处理冲突可以保证做到：只要哈希表未填满，总能找到一个不发生冲突的地址Hk，而二次探测再散列只有在哈希表长m为形如 4j+3(j为整数)的素数时才可能，随机探测再散列，则取决于伪随机数列。

2．再哈希法

    Hi=RHi(key) 
    RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

3．链地址法

将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间[0..m-1]上，则设立一个指针型向量Chain ChainHash[m]；其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中的插入位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。

    [例9-3] 已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)则按哈希函数H(key)=key MOD13和链地址法处理冲突构造所得的哈希表如图9.26所示。

4．建立一个公共溢出区

这也是处理冲突的一种方法。假设哈希函数的值域为[0..m-1]，则设向量 HashTable[0..m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

哈希表的实现方法

　　我们之前说了，哈希表是一个集查找、插入和删除操作于一身的数据结构。那这么完美的数据结构到底是怎么实现的呢？哈希表有很多种不同的实现方法，为了实现哈希表的创建，这些所有的方法都离不开两个问题——“定址”和“解决冲突”。

取余法（定值）+拉链法（解决冲突），来一起窥探一下哈希表强大的优点。

　　取余法大家一定不会感觉陌生，就是我们经常说的取余数的操作。

　　拉链法是什么，“拉链”说白了就是“链表数组”。我这么一解释，大家更晕了，啥是“链表数组”啊？为了更好地解释“链表数组”，我们用下图进行解释：图中的主干部分是一个顺序存储结构数组，但是有的数组元素为空，有的对应一个值，有的对应的是一个链表，这就是“链表数组”。比如数组0的位置对应一个链表，链表有两个元素“496”和“896”，这说明元素“496”和“896”有着同样的Hash地址，这就是我们上边介绍的“冲突”或者“碰撞”。但是“链表数组”的存储方式很好地解决了Hash表中的冲突问题，发生冲突的元素会被存在一个对应Hash地址指向的链表中。实际上，“链表数组”就是一个指针数组，每一个指针指向一个链表的头结点，链表可能为空，也可能不为空。

一

　　说完这些，大家肯定已经理解了“链表数组”的概念，那我们就一起看看Hash表是如何根据“取余法+拉链法”构建的吧。

　　将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..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相同Hash地址的关键字；

　　3）x所属的Hash地址被占用了，且它所存的关键属于这个Hash地址，即存在与x相同sHash地址的关键字，只是不知这个关键字是不是x，需要进一步查找。

由此可见，Hash表插入、删除和插入操作的效率都相当的高。

. 哈希表“定址”的方法（哈希函数的构造方法）

    1．直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即：
H(key)=key 或 H(key)=a·key+b
    其中a和b为常数(这种哈希函数叫做自身函数)。

    [例如]：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。这样，若要询问25岁的人有多少，则只要查表的第25项即可。

    [又如]：有一个解放后出生的人口调查表，关键字是年份，哈希函数取关键字加一常数 H(key)=key+(-1948)，若要查1970年出生的人数，则只要查第(1970-1948)=22项即可。

 

由于直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突。但实际中能使用这种哈希函数的情况很少。

   2．数字分析法

假设关键字是以r为基的数(如：以10为基的十进制数)，若哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

    [例如],有80个记录，其关键字为8位十进制数。假设哈希表的表长为10010，则可取两位十进制数组成哈希地址。取哪两位?原则是使得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。
 

对关键字全体的分析中我们发现：第①②位都是“8 1”，第③位只可能取1、2、3或4，第⑧位只可能取2、5或7，因此这四位都不可取。由
 

于中间的四位可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

3．平方取中法

取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。

    通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

    [例如]：为BASIC源程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母，或一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字，假设表长为512=29，则可取关键字平方后的中间9位二进制数为哈希地址。例如，图9.23(b)列出了一些标识符及它们的哈希地址。 
 

  4．折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址，这方法称为折叠法(folding)。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希地址。如国际标准图书编号0-442-20586-4的哈希地址分别如
 

5．除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即
H(key)=key MOD p p≤m
    这是一种最简单，也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模(MOD)，也可在折迭、平方取中等运算之后取模。值得注意的是，在使用除留余数法时，对p的选择很重要。若p选的不好，容易产生同义词。

    由经验得知：一般情况下可以选p为质数或不包含小于20的质因素的合数。

 

6．随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random (key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。

    实际工作中需视不同的情况采用不同的哈希函数。通常，考虑的因素有：
    (1)计算哈希函数所需时间(包括硬件指令的因素)；
    (2)关键字的长度； 
    (3)哈希表的大小； 
    (4)关键字的分布情况； 
    (5)记录的查找频率。 
 

 代码实现

/*
Author:Ibsen
Data:2015.12.21
*/
//哈希表的创建、插入、查找、删除(保留余数法建表,线性探查法解决哈希冲突哈希冲突)
#include <iostream>
using namespace std;
const int M=1000; //定义哈希表最大长度
const int P=13; //保留余数法的除数
typedef struct node
{
    int key; //关键字
    int count; //探查次数
}HashTable[M];
int len=13,m=0; //哈希表的长度和元素个数
int A[M]={16,74,60,43,54,90,46,31,29,88,77},n=11;
//定义空关键字为-1,被删除的关键字为-2.
int Search_HT(HashTable ha,int k)
{//查找元素
    int post=k%P;
    for(int i=0;ha[post].key!=-1&&ha[post].key!=k;i++)
        post=(post+1)%P;
    if(ha[post].key==k) return post; //查找成功
    else return -1; //查找失败
}
int Delete_HT(HashTable ha,int k)
{//删除元素
    int post=Search_HT(ha,k);
    if(post!=-1)
    {
        ha[post].key=-2;
        m--;
        return 1; //删除成功
    }
    else return 0; //删除失败(未找到关键字)
}
void Insert_HT(HashTable ha,int k)
{//插入关键字
    int post=k%P;
    if(ha[post].key==-1||ha[post].key==-2)
    {
        ha[post].key=k;
        ha[post].count=1;
    }
    else //发生哈希冲突时采用线性探查法解决冲突
    {
        int cnt=1; //插入k时发生冲突的次数
        do
        {
            post=(post+1)%P;
            cnt++;
        }while(ha[post].key!=-1&&ha[post].key!=-2);
        ha[post].key=k;
        ha[post].count=cnt;
    }
    m++;
}
void Creat_HT(HashTable ha,int A[],int n)
{//创建哈希表
    for(int i=0;i<M;i++)
    {
        ha[i].key=-1;
        ha[i].count=0;
    }
    for(int i=0;i<n;i++)
        Insert_HT(ha,A[i]);
}
void Display_HT(HashTable ha)
{//打印哈希表
    cout<<"The unmber of keys in HashTable is:"<<m<<endl;
    for(int i=0;i<len;i++)
        cout<<ha[i].key<<"   "<<ha[i].count<<endl;
    cout<<endl;
}
int main()
{
    HashTable ha;
    Creat_HT(ha,A,n);
    Display_HT(ha);
    int k;
    cout<<"Search in HashTable:"<<endl;
    while(cin>>k&&k)
    {
        int pos=Search_HT(ha,k);
        if(pos>-1) cout<<"The postion of the key is:"<<pos<<endl;
        else cout<<"Search Fail(No key exit)!"<<endl;
    }
    cout<<"Insert keys to HashTable:"<<endl;
    while(cin>>k&&k)
    {
        Insert_HT(ha,k);
        Display_HT(ha);
    }
    cout<<"Delete keys in HashTable:"<<endl;
    while(cin>>k)
    {
        if(Delete_HT(ha,k))
        {
            cout<<"Delete Succeed!";
            Display_HT(ha);
        }
        else cout<<"Display Fail(No key exit)!"<<endl;
    }
    return 0;
}