什么是哈希表（Hash Table）

理解Hash
       哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。
       映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素。但反过来，集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素，这样的映射被称为一一映射。这样的对应关系在现实生活中很常见，比如：

          A  -> B      

          人 -> 身份证号

          日期 -> 星座
       上面两个映射中，人 -> 身份证号是一一映射的关系。在哈希表中，上述对应过程称为hashing。A中元素a对应B中元素b，a被称为键值(key)，b被称为a的hash值(hash value)。
       映射在数学上相当于一个函数f(x):A->B。比如 f(x) = 3x + 2。哈希表的核心是一个哈希函数(hash function)，这个函数规定了集合A中的元素如何对应到集合B中的元素。比如：
          A: 三位整数    hash(x) = x % 10    B: 一位整数

          104                               4

          876                               6

          192                               2
       上述对应中，哈希函数表示为hash(x) = x % 10。也就是说，给一个三位数，我们取它的最后一位作为该三位数的hash值。
       哈希表在计算机科学中应用广泛。比如在git中，文件内容为键值，并用SHA算法作为hash function，将文件内容对应为固定长度的字符串(hash值)。如果文件内容发生变化，那么所对应的字符串就会发生变化。git通过比较较短的hash值，就可以知道文件内容是否发生变动。
       再比如计算机的登陆密码，一般是一串字符。然而，为了安全起见，计算机不会直接保存该字符串，而是保存该字符串的hash值(使用MD5、SHA或者其他算法作为hash函数)。当用户下次登陆的时候，输入密码字符串。如果该密码字符串的hash值与保存的hash值一致，那么就认为用户输入了正确的密码。这样，就算黑客闯入了数据库中的密码记录，他能看到的也只是密码的hash值。上面所使用的hash函数有很好的单向性：很难从hash值去推测键值。因此，黑客无法获知用户的密码。(之前有报道多家网站用户密码泄露的时间，就是因为这些网站存储明文密码，而不是hash值.)

       注意，hash只要求从A到B的对应为一个映射，它并没有限定该对应关系为一一映射。因此会有这样的可能：两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)或者hash 冲突。比如网络协议中的checksum就可能出现这种状况，即所要校验的内容与原文并不同，但与原文生成的checksum(hash值)相同。再比如，MD5算法常用来计算密码的hash值。已经有实验表明，MD5算法有可能发生碰撞，也就是不同的明文密码生成相同的hash值，这将给系统带来很大的安全漏洞。(参考hash collision）

Hash函数
　　Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。
1.Hash表的设计思想
　　对于一般的线性表，比如链表，如果要存储联系人信息：　
       张三 13980593357
       李四 15828662334
       王五 13409821234
       张帅 13890583472
　　那么可能会设计一个结构体包含姓名，手机号码这些信息，然后把4个联系人的信息存到一张链表中。当要查找”李四 15828662334“这条记录是否在这张链表中或者想要得到李四的手机号码时，可能会从链表的头结点开始遍历，依次将每个结点中的姓名同”李四“进行比较，直到查找成功或者失败为止，这种做法的时间复杂度为O(n)。即使采用二叉排序树进行存储，也最多为O(logn)。假设能够通过”李四“这个信息直接获取到该记录在表中的存储位置，就能省掉中间关键字比较的这个环节，复杂度直接降到O(1)。Hash表就能够达到这样的效果。
　　Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址。比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可。下面讨论一下Hash表设计中的几个关键问题。
2. Hash函数的设计
　　Hash函数设计的好坏直接影响到对Hash表的操作效率。下面举例说明：
　　假如对上述的联系人信息进行存储时，采用的Hash函数为：姓名的每个字的拼音开头大写字母的ASCII码之和。
　　address(张三)=ASCII(Z)+ASCII(S)=90+83=173;
　   address(李四)=ASCII(L)+ASCII(S)=76+83=159;
　　address(王五)=ASCII(W)+ASCII(W)=87+87=174;
　　address(张帅)=ASCII(Z)+ASCII(S)=90+83=173;
　　假如只有这4个联系人信息需要进行存储，这个Hash函数设计的很糟糕。首先，它浪费了大量的存储空间，空间利用率只有4/174，不到5%；另外，根据Hash函数计算结果之后，address(张三)和address(张帅)具有相同的地址，这种现象称作冲突，对于174个存储空间中只需要存储4条记录就发生了冲突，这样的Hash函数设计是很不合理的。所以在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。通常有以下几种构造Hash函数的方法：
　　1)直接定址法
　　取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000作为Hash地址。
　　2)平方取中法
　　对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。
　　3)折叠法
　　将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
　　4)除留取余法
　　如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。
　　在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。
       典型的除留取余法Hash函数是time33算法。PHP的数组就是把这个作为哈希函数。time33算法的核心如下：

uint HashTable::hash(const char* key)
{
    uint hash=0;
    for (; *key; ++key)
    {
        hash=hash*33+*key;
    }
    return hash%HASHSIZE;
}

        5)数字分析法
        假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。       
        例如有某些人的生日数据如下：
          年. 月. 日
          75.10.03
          85.11.23
          86.03.02
          86.07.12
          85.04.21
          96.02.15
        经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好
       6)随机数法
       选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
       H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
3.Hash表大小的确定
　　Hash表大小的确定也非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。

哈希冲突解决办法

       如果遇到冲突，哈希表一般是怎么解决的呢？具体方法有很多，百度也会有一堆，最常用的就是开放定址法和链地址法。
1.开放定址法
　　如果遇到冲突的时候怎么办呢？就找hash表剩下空余的空间，找到空余的空间然后插入。就像你去商店买东西，发现东西卖光了，怎么办呢？找下一家有东西卖的商家买呗。
　　由于我没有深入试验过，所以贴上在书上的解释：

       
2.链地址法
 　 上面所说的开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1。
　　那有没有一种方法可以解决这种问题呢？链地址法可以，链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。我感觉业界上用的最多的就是链地址法。下面从百度上截取来一张图片，可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353...}，而我的哈希算法是H(key)=key mod 16，第一个数据1的哈希值f(1)=1，插入到1结点的后面，第二个数据12的哈希值f(12)=12，插入到12结点，第三个数据26的哈希值f(26)=10，插入到10结点后面，第4个数据337，计算得到哈希值是1，遇到冲突，但是依然只需要找到该1结点的最后链结点插入即可，同理353。哈希表的拉链法实现如下图所示：

　　下面解析一下如何用C++实现链地址法。
　　第一步。
　　肯定是构建哈希表。
　　首先定义链结点，以结构体Node展示，其中Node有三个属性，一个是key值，一个value值，还有一个是作为链表的指针。还有作为类的哈希表。

#define HASHSIZE 10
typedef unsigned int uint;
typedef struct Node
{
    const char* key;
    const char* value;
    Node *next;
}Node;


class HashTable
{
private:
    Node* node[HASHSIZE];
public:
    HashTable();
    uint hash(const char* key);
    Node* lookup(const char* key);
    bool insert(const char* key,const char* value);
    const char* get(const char* key);
    void display();
};

　　然后定义哈希表的构造方法

HashTable::HashTable()
{
    for (int i = 0; i < HASHSIZE; ++i)
    {
        node[i] = NULL;
    }
}

　　第二步。
　　定义哈希表的Hash算法，在这里我使用time33算法。

uint HashTable::hash(const char* key)
{
    uint hash=0;
    for (; *key; ++key)
    {
        hash=hash*33+*key;
    }
    return hash%HASHSIZE;
}

　　第三步。
　　定义一个查找根据key查找结点的方法，首先是用Hash函数计算头地址，然后根据头地址向下一个个去查找结点，如果结点的key和查找的key值相同，则匹配成功。

Node* HashTable::lookup(const char* key)
{
    Node *np;
    uint index;
    index = hash(key);
    for(np=node[index];np;np=np->next){
        if(!strcmp(key,np->key))
            return np;
    }
    return NULL;
}

　　定义一个插入结点的方法，首先是查看该key值的结点是否存在，如果存在则更改value值就好，如果不存在，则插入新结点。这里与示意图中有点区别，新结点插入到链表头。

bool HashTable::insert(const char* key,const char* value)
{
    uint index;
    Node *np;
    if(!(np=lookup(key))){
        index = hash(key);
        np = (Node*)malloc(sizeof(Node));
        if(!np) return false;
        np->key=key;
        np->next = node[index];
        node[index] = np;
    }
    np->value=value;
    return true;
}

    显示Hash表中的key和value。

void HashTable::display()
{
	Node* temp;
	for (int i = 0; i < HASHSIZE; ++i)
	{
		if(!node[i]){
			printf("[]n");
		}else{
			printf("[");
			for (temp=node[i]; temp; temp=temp->next)
			{
				printf("[%s][%s] ",temp->key,temp->value );
			}
			printf("]n");
		}
	}
}

#include "HashList3.h"

int main(int argc, char const *argv[])
{
	HashTable *ht = new HashTable();
	const char* key[]={"a","b"};
	const char* value[]={"value1","value2"};
	for (int i = 0; i < 2; ++i)
	{
		ht->insert(key[i],value[i]);
	}
	ht->display();
	return 0;
}

关于哈希表的性能

　　由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击（用兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击），一般也不会出现这种情况。哈希表退化成链表如下图所示：