Hash

对于存储，主要是两种方式，一种是数组的有序存放，一种是链表形式的无序存放。各有各的优点，也各有各的缺点。

有序存放，比如List，可以按照索引很快查找到相应值，但是每次在前面或者中间插入数据时，就必须要把后面的所有数据都往后移，数据少的时候显现不出来，可当数据多的时候，这样插入数据就非常耗时了...

而对于无序存放，比如链表，不用关心前后有多少，只要在相应位置插入并在该处与两边的数据产生关联，就可以轻松插入数据了。但这种在每次查找时都要从头遍历，数据多的时候也就非常耗时了...

两种方法都各有各的优缺点，如果直接用某一种，一旦数据很大时，都会很花时间。那该怎么办呢？

这就要用到Hash算法了。首先创建一个数组，再在数组的每个空间下存放一个链表。让每一个要存放的值都产生一个与数组大小相关的键。这就有好几种方法得到这个键了。我用的是取余法。讲要存放的值除以数组的长度，得到的余数就作为存放在数组中地址的下标。如数组len[4]，存放6时，就放在6%4的位置，即len[1]处。显然，存放时会发生冲突，如再存入一个10，也要放在len[1]处，这时，就用链表形式来解决了。每存入一个值时，就产生一个结点，记录下一个值，并且与上一次存放在该位置的结点产生关联。这就像一个门帘一样，横放着一排挂链，这排挂链上每个挂勾下挂了一条链子。这样，当数据多的时候是不是查找起来就方便了很多呢.....

生成这样一个挂链的时候，我们希望数据规模能在一定范围之内，查找起来才快捷，能够尽可能平均的分配在每个挂钩下面。就像门帘的一排挂钩下都挂着相当的链长。总不会让一边是空空的，而另一边的链子又很长很长吧，这就牵涉到哈希算法的优化问题了。待续.....

 

 

我们不断的给这个数组下存放的各条链表添加数据，可未来不可预料，当初我们开辟数组空间时是按照我们预计的大小来进行的，可如果到后来发现数据规模越来越大了，要存放的数据不断地增大，增大到我们的有些链表快要达到阀值甚至已经达到阀值时，怎么办呢？显然必须要扩大数组空间了。那如何扩大数组空间大小比较节省时间而且比较方便呢？我想到一种方法是将数组长度扩大为原来的2倍。这样，相当于把之前每个数组元素下的链表放在两个元素下，将链表长度减半。如上面的6和10原来都放在len[1]处，现在将数组扩大2倍，那么数组长度就从4变成8，则6将放在len[5]处，10将继续放在len[2]处，这样我们重新存放数据时便少了一些计算步骤。

 

这个，一个测试Hashmap的算法，没传上去....