<What's Hash>
Hash，一般翻译做“散列”，也有直接音译为“哈希”的。

我们通常说的Hash，其实指的是Hash算法（即散列算法）：把任意长度的输入，通过Hash算法，变换成固定长度的输出（即Hash值、散列值）。

Hash算法有多种实现形式，比如MD5、SHA1，这里就不对算法本身进行讨论了。重点谈谈Hash算法的特性和作用吧：
    1）Hash是一种压缩映射：散列值的长度通常远小于输入的长度（比如emule，任意大小是视频文件，都可以映射成一个固定长度的字符串，它就相当于这个文件的信息摘要）
    2）不同的输入可能会Hash成相同的输出：这是一个小概率事件，且采用安全性高的Hash算法时，两个不同的输入几乎不可能得到相同的Hash结果。
    3）与加密算法不同，Hash算法是一个不可逆的单向函数，不可能从散列值来唯一的确定输入值。



<What's Hash Table>
0. 在下面的讨论中，我们将用到三国这个例子：假设我们要做个存储结构，需要存储下来三国中的英雄，以及他们的详细信息。我们用他们的名字来作为存储的关键值，例如：刘备，关羽，张飞，曹操，孙权...n。

1. 一般的表
    name    age    身高    体重
    刘备    30    175    60
    关羽    28    190    80
    张飞    27    185    80
    ...n
这时，如果我们想要查找某个英雄，就需要一边遍历表，一边对名字进行比较。它的时间复杂度为O（n）--线性阶。

总结：记录在结构中的相对位置和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较，查找的效率与比较次数密切相关。

2. 数组
    1）通过地址的访问方式（数组）：Array[2]，这里2就是它的“物理”地址，找到2所对应的内容是通过“直接定位”，而不是“遍历比较”。所以，在所有的线性数据结构中，数组的定位速度最快。它的时间复杂度为O（1）--常熟阶。

    这时，我们会想，那我们把刘-关-张-...n，按照1-2-3-...n的顺序放在一个数组里（数组的内容就是这个英雄的对象）不就可以直接定位了？
    arrayid    （name    age    身高    体重）
    1            （刘备    30    175    60）
    2            （关羽    28    190    80）
    3            （张飞    27    185    80）
    ...n

    2）但是：
        a）可你凭什么说刘=1，关=2呢？（显然不是叫你用拼音或者笔画排序）
        b）我们查找的时候，不可能用arrayid作为查找条件（那还查个P呀），怎样通过name=关羽，“计算”得到arrayid=2呢？


3. 散列表：其主要目的是用于解决数据的快速定位问题，也即，怎样通过关键字，计算（而不是遍历比较）得到物理地址。

1）存放时
    Hash（刘备）=13
    Hash（关羽）=7
    Hash（张飞）=26
    ...n

    arrayid    （name    age    身高    体重）
    ...
    7            （关羽    28    190    80）
    ...
    13          （刘备    30    175    60）
    ...
    26          （张飞    27    185    80）
    ...n

    我们也可以看出：
    a）散列，数据并非紧凑的、按顺序存入的：我们可以先在13的位置存上刘备，再在7的位置存上关羽；有些位置还可能一直是空的。
    b）空间换时间：因为散列，显然数组的大小要大于实际实际数据的数量。比如，即使我们只存刘关张3个人，我们也需要一个至少26的数组。

2）查找时，就很简单了
    Aarry[Hash（关羽）]=Array[7]

3）当然实际的hash算法，要比上述复杂，比如
    “把Key通过Hash算法转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里；
    而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。”

4）Hash冲突：前面说了，不同的输入是有可能hash成相同的输出的
    如果Hash（关羽）=Hash（张飞）=250，我们岂不是在存储过程中会遇到麻烦，怎么安排他们二位的地方呢?（总不能让二位打一架，谁赢了谁呆在那吧），这就需要一个解决冲突的方法。
    先存储好了关羽，当张飞进入系统时会发现关羽已经是250了，那咱就加一位，251得了。我们查找张飞的时候也是，一看250不是张飞，那就加个1，就找到了。
    更极端地，如果这时Hash（赵云）=251，张飞已经早早占了他的地方，那就再加1存到252呗。呵呵，这时我们会发现，当哈希函数冲突发生的机率很高时，可能会有一群英雄在250这个值后面扎堆排队。要命的是查找的时候，时间算法复杂度早已不是O（1）了。所以我们说理想情况下哈希表的时间算法复杂度为O（1）。
    这就是说哈希函数的编写是哈希表的一个关键问题，会涉及到一个存储值在哈希表中的统计分布。如果哈希函数已经定义好了，冲突的解决就成为了改变系统性能的关键因素。其实还有很多种方法来解决冲突情况下的存储和查找问题，不一定非要线性向后排队，如果有好的哈希表冲突的解决方法也能很大程度上提高系统的效率。


FYI，比较书面化的定义：
    理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列法）。


参考：
http://calmness.javaeye.com/blog/184465
http://blog.163.com/xx_snoopy/blog/static/12577162008426731299/