解决散列冲突之分离链接法和开放寻址法
散列及散列函数
http://www.wutianqi.com/?p=2419
散列及散列函数
http://www.wutianqi.com/?p=2419
散列表的缺点就是容易出现冲突（也叫碰撞），两个关键字可能映射到同一个槽中，然后就产生了冲突，解决冲突的方法有很多种，这里只集中讨论其中最简单的两种：
第一种是：分离链接法，就把散列到同一个槽中的所有元素都放在一个链表中，如果，槽 j 中有一个指针，它指向所有散列到j的元素构成的链表的头；如果不存在这样的元素，则j中为NIL
第二种是：开放寻址法，所有元素都存放在散列里，查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。不像在链接法中，这里没有链表，也没有元素存放在散列表外。 当要插入一个元素时，可以连续地检查散列表的个各项，直到找到一个空槽来放置这个元素为止。检查顺序可以是线性的，可以是二次平方的，也可以是双散列的，还有很多如：再散列，可扩散列等。
线性探测法：第一次冲突移动1个单位，再次冲突时，移动2个，再次冲突，移动3个单位，依此类推。
它的散列函数是：H(x) = (Hash(x) + F(i)） mod TableSize, 且F(0) = 0.
线性探测存在“一次聚集“的问题，就是在表中存放是全部挨着的。这样在后期的插入过程中，会造成开销很大。
平方探测 可以避免上边提到的一次聚集：第一次冲突时移动1个单位，再次冲突时，移动4（2的平方）个单位，还冲突，移动9个单位，依此类推。F(i) = i * i , 于是可以很快推出：实现函数是：F(i) = F( i – 1) + 2i + 1.（稍微化简一下便知），这样可以避免每次的乘法和除法，而用加法代替，是一种加速手段。
对于线性探测，如果几乎很满，后期插入时表的性能会降低，对于平方探测情况，情况更糟：一旦表被填满超过一半，当表的大小不是素数时甚至在表被填满一半之前，就不能保证一次找到一个空单元了。这是因为最多有表的一半可以用于解决冲突的备选位置（证明过程看书吧）。
另外，表的大小是素数也非常重要。如果表的大小不是素数，则备选单元的个数可能会锐减。例如，如果表的大小是16，那么备选单元只能在距散列值1,4或9距离处。
平方探测排除了一次聚集，但是散列到同一位置上的元素将探测相同的备选单元，这叫做二次聚集，二次聚集理论上是个小缺陷，它一般要引起另外的少于一半的探测。另外，双散列可以排除这个遗憾，不过要花费另外的一些乘法和除法。
双散列是：双重散列借用两个散列函数，F(i) = i * hash2(X)，这个公式意思是：我们将第二个散列函数应用到X并在距离hash2(X)，2 * hash2(X)等处探测。如果双散列正确实现，模拟表明：预期的探测次数几乎和随机冲突解决方法的情形相同，所以理论上双散列很有吸引力。它的散列函数是：h(k, i) = (h1(k) + ih2(k)) mod m，它的结果是不定的，有冲突时，移动随机个单位，但是确实可以很好的解决冲突。
