散列以及在java集合类中的应用

        散列是无需查找，只用元素的查找键来确定元素索引的方法。散列函数就是一种用来实现散列的函数，它接受一个查找键，计算出该键的散列码，然后再将此散列码压缩到散列表的范围内。在用散列来实现某种数据结构的时候，往往会遇到冲突的情况（不同的查找键有相同的散列码）此时就需要我们去处理冲突，而处理冲突的方法有两种：

  第一种：使用散列表的另一个位置。这里又可以采用三种不同的方法：

        1 ： 线性探测开放定址法。此方法会导致一次聚集。

        2 ； 二次探测开放定址法。此方法会导致二次聚集。

        3 ： 双散列开放定址法 。使用次方时要保证散列表元素是素数。因为只有这样才能探测到散列表中的所有位置。并且可以使元素均匀的分布到散列表中，避免了聚集。

  第二种：利用桶来处理冲突

        此方法要用到桶这个东东，桶一般用链表来实现，因为这样可以节约内存。此时的方法也可以叫链地址法。JAVA中的HashMap就是用桶来处理冲突的。

        散列里还有一个重要的概念就是装填因子。它是一个浮点数。在具体实现中，它是所有元素的个数与散列表位置的比值。它主要是用来决定是否要再散列的。不过在具体实现中要尽量避免再散列。在散列的开销很大。装填因子它也从一个侧面表示了程序中速度相对于内存使用的重要性：如果值低就表示注重的是速度，如果值高就表示注重的是内存的使用。不过无论采用何种处理冲突的方法，装填因子都有一个限制，对于第一种来说，规定装填因子要小于0.5，而对于第二种要求装填因子要小于1.0.

        JAVA中的很多集合类使用了散列这种方法。HashMap就是其中之一。并且HashSet底层也是用HashMap来存储它的元素，因为用到了散列，所以这两种集合类都不能保证元素的添加顺序。此外在对HashMap和HashSet操作时，特别注意两个方法：equals()和hasCode()，List接口用equals()来判断两个元素是否相同。而HashSet首先用hasCode()来算出两个元素的哈希吗，如果哈希吗不同，则两元素不同。如果哈希吗相同，那么就要用equals()方法来判断两个元素是否相同，如果equals()返回真，则相同，否则不相同。这就要求当我们的equals()方法返回真时，一定要保证这两个对象有相同的哈希吗。