HashCode

想了解HashCode,首先要知道什么是Hash。

1、Hash

• Hash中文翻译为散列，又成为“哈希”，是一类函数的统称，其特点是定义域无限，值域有限。把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

2、常用的Hash函数

• 直接寻址法
• 数字分析法
• 平方取中法
• 折叠法
• 随机数法
• 除留余数法（常用）：n mod size

3、HashCode

• hashcode就是通过hash函数计算得来的，在hash表中有对应的位置。

• 每个对象都有hashcode，通过把对象的物理地址转换成一个整数，然后该整数通过hash函数就得到了hashcode。

4、Hash冲突（碰撞）

• 由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可 能是相同的，这种情况，就叫作哈希冲突。
• 解决哈希冲突的方法主要有两种：

  • 开放寻址法

    开放寻址法的原理是当一个Key通过哈希函数获得对应的数组下标已被占用时，就寻找下一个空档 位置，在Java中，ThreadLocal所使用的就是开放寻址法

  • 链表法

    数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可，默认next指向null

5、HashCode作用

• HashCode确定了对象在散列存储结构中的存储地址，进而减少了查找次数，提高程序效率

• 例如hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表中8个位置会有很多数字了，1中可能有20个数字，存101个数字时，他先查hashcode值对应的位置，假设为1，那么就有20个数字和他的hashcode相同，他只需要跟这20个数字相比较(equals)，如果都不相同，那么就放在1这个位置

6、equals方法和hashcode的关系

• 判断两个对象是否相等，可以先通过hashcode来比较，如果hashcode相等，那么就用equals方法来比较两个对象是否相等。

• 用个例子说明：上面说的hash表中的8个位置，就好比8个桶，每个桶里能装很多的对象，对象A通过hash函数算法得到将它放到1号桶中，当然肯定有别的对象也会放到1号桶中，如果对象B也通过算法分到了1号桶，那么它如何识别桶中其他对象是否和它一样呢，这时候就需要equals方法来进行筛选了。

• 如果两个对象equals相等，那么这两个对象的HashCode一定也相同

• 如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置