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

散列是无需查找，只用元素的查找键来确定元素索引的方法。它使得我们可以快速的查找和添加元素。如果散列函数以及处理冲突的方法设计好，性能一般都是O(1)的。散列函数就是一种用来实现散列的函数，它接受一个查找键，计算出该键的散列码，然后再将此散列码压缩到散列表的范围内。在用散列来实现某种数据结构的时候，往往会遇到冲突的情况（不同的查找键有相同的散列码）此时就需要我们去处理冲突，而处理冲突的方法有两种：

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

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

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

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

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

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

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

     JAVA中的很多集合类使用了散列这种方法。HashMap就是其中之一。并且HashSet底层也是用HashMap来存储它的元素，因为用到了散列，所以这两种集合类都不能保证元素的添加顺序。理解了散列我们在使用java类库中的set以及Map时，就要记得同时重写equals()和hasCode()方法。hasCode()确定了我们要操作的对象的散列码值对应的在散列表中的索引值，当遇到冲突时，通过equals()方法来在桶中进行查找。