前言
笔者以前对散列是什么？哈希又是什么？何谓散列表？散列函数又是个什么东东比较的迷惑。
通过看一些书，查找一些资料总算是有一些眉目了，现将相关的知识与体会记录下来。留待日后
的再学习!
基本概念
散列表(Hash table，也叫哈希表)，是根据关键字(key value)而直接进行访问的数据结构。
说的具体点就是它通过吧key值映射到表中的一个位置来访问记录，从而加快查找的速度。
实现key值映射的函数就叫做散列函数
存放记录的数组就就叫做散列表
实现散列表的过程通常就称为散列(hashing)，也就是常说的hash
散列
这里的散列的概念不仅限于数据结构了，在计算机科学领域中，散列-哈希是一种对信息的
处理方法，通过某种特定的函数/算法(散列函数/hash()方法)将要检索的项与用来检索的索引-
-( 散列值)关联起来，生成一种便于搜索的数据结构--散列表。
如今，由于散列算法所计算的散列值 具有不可逆(无法逆向演算会原来的数值)的性质，
因此散列算法广泛的运用于加密技术。
散列的运用：
1、加密散列
在信息安全领域使用
2、散列表
一种使用散列函数将键名和键值关联起来的数据结构
3、关联数组
一种常常使用散列表来实现的数据结构
4、几何散列
寻找相同或相似的几何形状的一种有效方法
散列函数
通过上面可以知道，散列技术的实现是基于散列函数的。这里对散列函数进行一个较深
入的理解。 前面就知道了散列函数--哈希函数就是完成key值与位置的映射。一般说来key
以字符 串的形式居多，位置也就是一个数值。
可以看出散列函数就像是实现信息的压缩，把消息字符 串压缩成数值摘要，是数据量
变小，格式得以固定下来。
散列函数的工作原理图：
不过需要注意的是key值和经过散列函数处理之后的散列值并不是唯一对应的，
这就造成了不同的key值具有相同的索引位置，这种现象叫做散列碰撞、也称其为哈希冲突。
对于hash冲突的解决办法，将在后面予以总结。
至于散列函数的具体实现，有很多加密技术都有十分nice的实现，这里我们看看java中
HashMap的hash()方法实现就可以了。HashMap采用的是内部哈希技术实现的，其中
hash()方法就是散列函数，完成key值到数组索引位置的映射。
/**上述代码就是HashMap中散列函数的具体实现。JDK1.7
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这里笔者对常用的散列算法做一个展示：
散列表
在理解了上述散列\散列函数的概念之后我们正式的进入到散列表的学习.
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列
的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为 W 的表中查找“王”姓的电
话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散
列函数的函数法则 F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
散列函数的构造
对于散列表这种数据结构来说，其散列函数的构造是十分关键的，散列函数实现了key的
映射,并且访问记录可以更快的被定位。
一般来说散列函数的构造基于两个标准:简单、均匀
简单指散列算法简单快捷，散列值生成简单。
均匀指对于key值集合中的任一关键字，散列函数能够以均与的概率映射到数组的任一一个
索引位置上，这样能够减少散列碰撞。
散列函数构造方法：
1、直接地址法：
直接取key值或者key值的某个线性函数值作为散列地址。即hash(k)=k
或者hash(k)=a*k+b。
Tips： 简单的思考一下这种方式就可以知道，这种方式基本不会存在哈希冲突，
不过事 先我们应该知道key集合的大小，而且使用线性函数值作为散列地址的话，
很大程度上造成了 空间的浪费。hash(k)=k这种方式更加的鸡肋没必要，以这种方式
散列还不如直接数组索引。
2、数字分析法：
所谓的数字分析法就是假设关键字key是以r为基的数，并且hash表中可能出现的
关键字都是事先知道的，则可取关键字的若干数位组成hash地址。
Tips：这种方式极度不灵活，限制太多。
3、平方取中法：
先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为
散列函数值。
Tips：这种方式中间的几位数都和关键字的没一位都有关，产生的散列地址较为的
均匀。
4、折叠法:
将关键字分割成相同的几位数(最后一位可不同)，然后去这几部分的叠加和。折叠法
一般是和除留余法一起使用的。
5、除留余法：
取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(k)
= k mod p, p < m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后
取模。对 p 的选择很重要，一般取素数或 m ，若 p 选择不好，容易产生碰撞。
6、随机法：
h(key)=random(key)
其中random为伪随机函数，但要保证函数值是在0到m-1之间。
总结:在上述的方法中，3、4、5三种方法的结合使用方式较好，在JDK以前的版本就是使用
的方法5。
哈希冲突
通过上面的学习中，我们知道散列函数得到的key - 索引位置 并不是唯一对应的，可能造成
不同的key值对应相同的索引位置。这是我们应该解决的问题。实际的解决方法一般如下：
1、分离连接法：
首先看看分离连接法，说白了这种方式就是链表数组的方式，将散列到同一个值得所有元素
保存在一个表中，产生相同的一个值在散列表中使用链表的形式存储。哈希冲突的位置就是链表
的开始位置。在JKD中HashMap就是这种方式解决哈希冲突的!
HashMap中冲突处理代码如下
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} 详细的情况可以看看笔者以前基于HashMap源码分析的文章：
http://blog.csdn.net/kiritor/article/details/8885961
这里我们定义一个填装因子L，它表示散列表中实际的元素个数和数组的大小之比，
由此我们可以很容易的得到查找一个元素的时间为计算散列值的常数时间+ 遍历链表
的时间。一次查找时间大约为1+2/L。由此说明，散列表的大小并不是影响查找的关键，
关键在于L，保证L近似为1是十分有效的。
2、开放地址法
分离连接法的缺点在于使用了链表，由于给新的单元分配地址耗费时间，造成算法速度
较慢，解决的方法就是开放地址法，在开放地址法中较为常用的有两种：
线性探测法、平方探测法。
开放地址法:
hash_i=(hash(key) + d(i)) mod m, i=1,2...k\,(k < m-1)，其中hash(key)为散列函数，
m为散列表长，d(i)为增量序列，i为已发生碰撞的次数。增量序列可有下列取法：
d(i)=1,2,3...(m-1) 称为 线性探测；即 d(i)=i ，或者为其他线性函数。相当于逐个探测
存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。
d(i)=1^2, 2^2,3^2... k^2 (k < m/2) 称为 平方探测。相对线性探测，相当于发生碰
撞时探测间隔 d(i)=i^2 个单元的位置是否为空，如果为空，将地址存放进去。
d(i)=伪随机数序列，称为 伪随机探测。
线性探测法
下面笔者将以一个实例演示线性探测的过程，进而分析线性探测的特点，引出平方探测
关键字为{89,18,49,58,69}插入到一个散列表中的情况。此时线性探测的方法是取d(i)=i。
并假定取关键字除以 10 的余数为散列函数法则。
1、开始时hash(89)=9无冲突，直接插入；
2、hash(18)=8无冲突，直接插入；
3、hash(49)=9冲突了，开放地址，将49放入下一个空闲地址0
4、hash(58) =8冲突了，开放地址，将58放入9冲突 ，放入0冲突、放入1
5、hash(69) =9冲突，开放地址，将69放入0冲突，放入1冲突，放入2
Tips：思考其缺点!
线性探测的方式十分简单，明白，每次插入总是能够找到一个地址，但是慢慢会
形成一个区块，其结果称为一次聚集。任何关键字需探测越来越多的次数才能解决
冲突，且完成之后由简介的增大了区块。当填装因子>0.5时，这种方式就不是个好
的方法了!
平方探测法：
使用平方探测法可以解决线性探测的一次聚集问题。一般选择d(i)=i^2.。
至于其具体的步骤读者可以按照上面的实例自行的模拟一下。
这种方式会出现二次聚集的情况：散列到同一位置的哪些元素将探测相同的备选
单元。
3、双散列、再散列
对于双散列和再散列的方式笔者这里就不在多提了。读者可以查阅下相关的资料。
总结：对于散列表的实现新手不必太过在意，关键在于理解散列相关的概念。了解并
掌握散列函数的作用及一般的实现方式。了解一般hash冲突和常用解决办法。
到这儿就结束了，希望大家看的开心，玩的愉快，端午节快乐。
By Kiritor
写于2013 端午