[数据结构与算法]HashMap添加元素用到hashCode

hashCode()是定义在Object类中的一个方法，用于计算并返回对象的哈希码值，这个方法是为了支持哈希表。类可以重写hashCode()自定义哈希值的计算方法。

为啥要有哈希值？这里先引出一个东西：哈希表，这个哈希值就代表在哈希表中的位置。

在集合中这个hashCode()方法的用处就很大了，比如HashMap<k，v>的添加元素的原理，HashMap不能存储key一样的元素，key一样则替换成后者来的value，HashMap底层采用数组+链表+红黑树的数据结构存储数据，当数组上某一个索引的位置上以链表形式存在的数据个数超过8个，且数组长度超过64，则这个索引位置上的数据改用红黑树存储。倘若已经添加了100个元素，要添加101个元素时，则要与前100个元素遍历比较key是否相等，那太麻烦了。于是HashMap就利用hashCode()来存储数据：

HashMap添加元素put（key1，value1）时，会计算key1所在类的hashCode()方法计算哈希值，然后对这个哈希值根据某个算法计算出key1-value1在数组中的存储位置，

判断这个位置上没没有元素：

? ? ? ? 没有元素则直接添加成功--成功1

? ? ? ? 有元素，key1哈希值则和这个位置上所有元素的key的哈希值比较：

? ? ? ? ? ? ? ? 都没有相等的，则元素添加成功--成功2

? ? ? ? ? ? ? ? 有相等的，key1和key进行equals比较：

? ? ? ? ? ? ? ? ? ? ? ? 返回false，则添加成功-成功3

? ? ? ? ? ? ? ? ? ? ? ? 返回true，则用value1替换value

有了哈希值计算位置，哈希值不一样位置肯定不一样，哈希值不一样key肯定不一样，所以没必要和位置不一样的元素比较，只需要和同一个位置上的元素进行比较即可，不用遍历比较。

为了保证以上原理的成功，所以equals和hashCode需要保证以下原则重写。

从上面集合添加元素来看，一般重写equals（）的话，也一定要重写hashCode（），而且要按照以下的约定重写。

1. equals返回true，hashCode一定相等
2. equals返回false，hashCode可能相等
3. hashCode相等，equals不一定true
4. hashCode不相等，equals一定不true