本文的学习是通过：现代魔法学院——散列表
1. 散列表
散列表区分于顺序表，顺序表的查找是依次遍历查询，而散列表是直接指向具体的位置。我们需要通过某个函数f，使 value = f(key) 。在java中，关于散列表如果想要深入理解可以看HashMap的源码。
2.如何查找
散列过程：1.通过散列函数计算某记录的散列地址，并在此地址存储该记录 2.查找的时候，通过同样的散列函数去计算散列地址，并依此访问数据。
散列技术并不像线性表、树、图，散列表没法用连线给图示出来，记录与记录之间不存在逻辑关系。记录只与关键字有关，是面向查找的。它的优势在于简化的比较过程，查的快，效率提升很大。缺点在于一一对应，并且无法给表中数据进行排序。而且，会有哈希冲突(碰撞)的可能性。我们无法保证每个关键字通过散列函数计算都能得到不同的结果，也就是 x≠y 但是f(x)=f(y)，此时就发生了冲突，我们可以通过一些技术去处理这种情况。
3.散列函数
只能去尽可能的避免冲突，无法完全规避。
设计原则：
1.计算简单 （时间）
2.散列地址均匀 （空间）
具体方法有两种比较典型：1.直接定址法 2.除留余数法
现在比较普遍的是DJBX33A，冲突少，效率高，PHP的Hash采用的这个。
a.直接定址法
取关键字的某个线性函数值为散列地址。 f(key) = a × key + b
这个方法优点在于不会产生冲突，而且分布均匀，但是！前提很苛刻，需要提前知道关键字的分布情况，适合查找表比较小且连续的情况。所以并不是特别常用。
b.除留余数法
此法为最常用的散列函数方法，公式为f(key)=key mod p (p<m)
m是容量，mod为求余，关键点在于选择合适的p，p选取不好冲突可能就比较频繁。
(在学习的原文中，有具体的例子，可以点击文章开头的链接跳过去看)
Q:如何合理取值呢？
A:如果表长为m，p取小于等于m的最小质数，或者是不包含小于20质因子的合数。
既然冲突是无法避免的，就要找到冲突的处理方法。
a.开放定址法
没什么是重新计算一次解决不了的，如果有，那就算两次。
此方法，一点冲突了，就去寻找下一个空的散列地址，只要散列表足够大，就一定能找到。
具体是使用一种探测技术在散列表形成一个探测序列，并以此逐个单元的查找，直到找到给定的关键字，或者碰到一个开放的地址为止。开放定址法是一种线性探测法。
公式：fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
这里的di是从1开始，也就是说，如果di=1重新计算之后发现还是不行，那么再次计算就di=2再算。
比如我们有个集合{12,56,67,16,25,37,22,29,15,47,48,34} (这里就用原文章里面的例子了)
用散列函数 f(key) =- key mod 12
直到25都是无冲突的，可以直接放进去
当我们key=37的时候，会发现 37 mod 12 = 1 ，这个时候与关键字25发生了冲突。
那么要用上面的公式去重新取值 f(37)=(f(37)+1) mod 12 = 2 好的，那么就把这个值放到下标为2的区域。
继续放置：
好的接下来是48，我们计算f(48)=0 很明显没法直接放置了，我们再算 f(48)=(f(48)+1)mod12 = 1 依然不行，我们就di加1继续算。f(48)=(f(48)+2)mod12 = 2 还不行，那就继续算，直到发现6这个位置。
现在应该理解这种方法了吧，这种方法的缺点也应该看出来了，很容易造成非同义词抢占同一个地址的情况，这种情况叫做堆积，效率因此下降。
开放定址法的基本思路，有很多围绕开放定址法的变形，这里归类于同一种。什么线性探查、平方探查、二次探测，很多名号。。。
b.链地址法 (拉链法)
这个方法和开放定址法差别特别大，所有我个人认为他才是第二种方法。有冲突，可以不换地方吗？就不能在原地给他处理了吗？？？当然可以！
将所有关键字为同义词的记录储存在单链表中，这个叫做同义词子表，在散列表中只存同义词子表的头指针即可。对于刚才的关键词集合，在这里表示就是这样的，我要去盗图了！！！
这个思路妙就妙在避免了冲突换址。解决冲突的方法就是将关键字同义词的节点链接在同一个链表里面。
如果选定的散列表长度为m，那么可以把散列表定义为一个由m个头指针组成的指针数组T[0...m-1]，凡是散列地址为i的节点，均插入到T[i]为头指针的单链表、这里可以拿HashMap进行举例，HashMap中有两个关键概念，initialCapacity 和 loadFactor。initialCapacity 是初始化容量，loadFactor是负载因子。
有一个公式：initailCapacity*loadFactor=HashMap的容量
所以出来，负载因子决定了散列表空间使用程度。负载因子越大，散列表的装填程度越高，能容纳更多的元素，但是索引效率就会降低，反之亦然。
拉链法的优点在于处理冲突的方式简单，并且没有堆积的情况出现，非同义词不会发生冲突。链表上的节点空间是动态申请的。拉链法中增加的指针域几乎可以忽略不计，节省空间。
删除节点的操作比较容易实现。这一点是开放定址法无法企及的。对于开放定址法来说，删除节点不能简单的把被删节点的空间置空，因为这样会截断在它之后填入散列表同义词节点的查找路径，也就是我们用同样的函数去查，发现查不到东西了，而数据再散列表中依旧是存在的，开放定址法里面空地址单元代表着查询失败。所以只能在被删节点上做标记，让我们以为节点空间清出来了。。。
拉链法的缺点几乎可以忽略，仅仅是指针需要一些额外的空间而已。
