关于哈希算法

 先看这样一个问题。比如有一个大小为10的数组，我要把1-9放进去。那么有一种办法就是按顺序从数组的第一个一直放到最后一个。比如我这么放2,4,6,8,1,3,5,7,9 ,那么我要查找一个数在在这个数组的哪个位置时，我得用一个循环检测。当数组很大时，效率会很低。如果我这样做呢？将元素与9求余，得到一个结果，之后将元素放到该位置。比如，2%9 结果为2，那么数组的第2个位置放上2。每个元素都根据这样的一个函数处理后放到指定的位置。那么当查找该元素时，只需要将该元素利用之前的函数再处理一次，就可以得到其在哪个位置。如，我需要查找9的位置。那么我用9%9，知道9在数组的第一个位置。也就是说，此时查找不必循环数组的每一个元素了，而直接根据函数来得到元素位置。

 

上面的方法就是哈希算法，与9求余，就是一个哈希函数，而求余的结果就是一个哈希值，也称为哈希代码。

 

也许你会发现，如果我要放0进去，利用哈希函数，0%9，结果为0。可以知道它和9会在一个位置（都放在数组的第0个位置）。这也就产生了哈希冲突。那么，怎么解决这样的冲突呢？当9已经放在了数组的第一个位置时，如果有新的元素和它位置一样。那么就放在9的下面，如下图：

0就放在9的下面，如果继续有重复的，比如18，那么继续放在0的下面。这里的实现并不是数组，而是链表。