HashMap的散列原理

为了速度而散列：

       散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈在于键的查询速度，因为解决方案之一就是保持键的排序状态。然后使用Collections.binarySearch()进行查询。 散列则更进一步，它将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以用它来表示键的信息 （请小心留意，这里说的是键的信息，而不是键本身）。但是因为数组不能调整容量，因此就有一个问题：我们希望在Map中保存数量不确定的值，但是如果键的数量被数组的容量限制了，该怎么办？

       答案就是：数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义在Object中的， 且可能由你的类覆盖的hashCode()方法（在计算机科学的术语中称为散列函数）生成。 为解决数组容量被固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突，因为数组多大就不重要了，任何键总能在数组中找到它的位置。 于是查询一个值的过程首先就是计算散列码，然后使用散列码查询数组（直接用散列码作为数组的下标）。如果能保证没有冲突，那就可能有了一个完美的散列函数，但是这种情况 只是特例。通常，冲突由外链接处理：数组并不直接保存值，而是保存值的List。然后对list的值使用equels()方法进行线性的查询。这部分的查询 自然会比较慢，但是，如果散列函数好的话，数组的每个位置就只有较少的值。因此，不是查询整个list，而是快速的跳到数组的某个位置，只对很 少的元素进行比较。这就是HashMap会如此快的原因。

由上可以推出：两个对象hashCode()的计算结果相等并不代表在Map的键存储中这两个对象是相等的，只有当hashCode和equals都相等时候才会表示相等。 反过来说，假如两个对象在Map的键存储中是相等的，那么这两个对象的hashCode和equals都相等。