散列是什么？哈希又是什么？何谓散列表？散列函数又是个什么东东。散列表是一种设计特别牛逼的数据结构。
什么是散列表
散列表（Hash table，也叫哈希表），是存储Key-Value映射的集合。可根据键(key)实现近O(1)的时间内对内存中数据进行读写的数据结构。
需要说明的是这里所说的 散列表 或 哈希表 或 Hash Table ，以及对应的函数 散列函数、哈希算法、Hash算法指的都是同一个概念，之所以会有这几个名字，纯属是由于中文翻译的差别。
散列表是 一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
这里再说一下哈希（hash）表的定义：哈希表是一种根据关键码去寻找值的数据映射结构，该结构通过把关键码映射的位置去寻找存放值的地方，说起来可能感觉有点复杂，我想我举个例子你就会明白了，最典型的的例子就是字典，大家估计小学的时候也用过不少新华字典吧，如果我想要获取“按”字详细信息，我肯定会去根据拼音an去查找 拼音索引（当然也可以是偏旁索引），我们首先去查an在字典的位置，查了一下得到“安”，结果如下。这过程就是键码映射，在公式里面，就是通过key去查找f(key)。其中，按就是关键字（key），f（）就是字典索引，也就是哈希函数，查到的页码4就是哈希值。
散列函数
通过上面可以知道，散列技术的实现是基于散列函数的。这里对散列函数进行一个较深入的理解。前面就知道了散列函数--哈希函数就是完成key值与位置的映射。一般说来key以字符串的形式居多，位置也就是一个数值。
可以看出散列函数就像是实现信息的压缩，把消息字符 串压缩成数值摘要，是数据量变小，格式得以固定下来。
散列函数的工作原理图：
不过需要注意的是key值和经过散列函数处理之后的散列值并不是唯一对应的，这就造成了不同的key值具有相同的索引位置，这种现象叫做散列碰撞、也称其为哈希冲突。对于hash冲突的解决办法，将在后面予以总结。
哈希冲突
但是问题又来了，我们要查的是“按”，而不是“安，但是他们的拼音都是一样的。也就是通过关键字按和关键字安可以映射到一样的字典页码4的位置，这就是哈希冲突（也叫哈希碰撞），在公式上表达就是key1≠key2，但f(key1)=f(key2)。冲突会给查找带来麻烦，你想想，你本来查找的是“按”，但是却找到“安”字，你又得向后翻一两页，在计算机里面也是一样道理的。
但哈希冲突是无可避免的，为什么这么说呢，因为你如果要完全避开这种情况，你只能每个字典去新开一个页，然后每个字在索引里面都有对应的页码，这就可以避免冲突。但是会导致空间增大（每个字都有一页）。
既然无法避免，就只能尽量减少冲突带来的损失，而一个好的哈希函数需要有以下特点：
- 尽量使关键字对应的记录均匀分配在哈希表里面（比如说某厂商卖30栋房子，均匀划分ABC3个区域，如果你划分A区域1个房子，B区域1个房子，C区域28个房子，有人来查找C区域的某个房子最坏的情况就是要找28次）。
- 关键字极小的变化可以引起哈希值极大的变化。
比较好的哈希函数是time33算法。PHP的数组就是把这个作为哈希函数。
核心的算法就是如下：
unsigned long hash(const char* key){
unsigned long hash=0;
for(int i=0;i<strlen(key);i++){
hash = hash*33+str[i];
}
return hash;
}哈希冲突的解决
开放寻址法：当出现散列冲突时，便重新探测一个空闲位置，将其插入。
链表法：当出现散列冲突时，则在冲突位置以链表的形式存储Hash值相同的数据。该结构由数组+链表的形式组成，如下图所示：
关于哈希表的性能
由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击（用兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击），一般也不会出现这种情况。
