目录
一、HashCode() 与 equals()
1、默认情况
2、重写后
3、HashCode 与 equals 返回结果的关系总结
4、HashCode 与 equals 未被统一重写情况
【经典面试题】：为什么重写对象的 equals 方法时，要重写 HashCode 方法？
二、HashCode 在 HashMap 中的应用
1、为什么 HashMap 先比较 hash 值而不是直接用 equals？
2、关于 HashMap 的几个小点：
为什么HashMap线程不安全？
什么导致 HashMap 出现死循环？
三、一致性Hash
1、通过一致性 Hash 构建分布式缓存服务器
2、Hash 环常见问题：数据倾斜、缓存雪崩
3、节点缩扩容常见问题
解决扩容延时
解决缩容延时
四、Hash 算法的其他应用
一、HashCode() 与 equals()
对于没有重写 HashCode 和 equals 方法的引用对象，默认继承 Object 类中的 HashCode 和 equals 方法。
1、默认情况
equals：比较两个对象是否为同一个对象，即内存地址是否一样；
HashCode：返回该对象的 Hash 值，是一个整型数据（int，32位，4个字节），这个值可以是内存地址，也可以不是内存地址，这取决于 HashCode 的生成策略，可以通过 jvm 的启动参数来配置不同的 HashCode 生成算法，Java 一共提供了 6 种生成策略。默认生成策略不是内存地址，并且不能保证不发生Hash冲突。
hashCode真的是内存地址吗_wuychn的博客-CSDN博客_hashcode是内存地址吗本文内容基于 JAVA 8 HotSpothttps://blog.csdn.net/qmqm011/article/details/117928412Object 类中也对这两种方法做了解释：
注意：
1）hashcode 的一般约定：equals 为 true，hashcode 一定相等；equals 为 false，hashcode 最好是不相等，这样的效率最高，但32位的 hashcode 唯一性毕竟有限，总会不可避免的出现相等，即产生了hash冲突。
2）重写 hashCode 方法时，通常都需要重写 equals 方法，以便维护 hashCode 方法的一般约定，即相同的对象必须具有相同的 hash 值。
2、重写后
自动重写生成的 HashCode 和 equals 方法，都是依赖对象属性生成的。
equals：先通过 == 判断是否为同一对象，若不是，则判断两个对象是否来自同一个类，如果是，则继续比较两个对象的成员变量是否相等。
HashCode：按照成员变量的值计算出一个32位的hash值输出，这种方式会有较大概率发生 hash 冲突。
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Test test = (Test) o;
if (a != test.a) return false;
if (b != test.b) return false;
return c == test.c;
}
@Override
public int hashCode() {
int result = a;
result = 31 * result + (int) (b ^ (b >>> 32));
result = 31 * result + c;
return result;
}
3、HashCode 与 equals 返回结果的关系总结
前提：按照 hashCode 约定，统一被重写，或者都未被重写。
HashCode 相等 ---> equals 不一定（考虑是否存在hash冲突）
HashCode 不相等 ---> equals 一定为 false
equals 为 true ---> HashCode 一定相等（都是同一个对象了，一定相等）
equals 为 false ---> HashCode 可能相等（考虑是否存在hash冲突）
4、HashCode 与 equals 未被统一重写情况
只重写了 equals （从判断对象是否为同一对象，重写为，判断对象内容是否相等）：
【没变】 HashCode 相等 ---> equals 不一定（仍要考虑是否存在hash冲突）
【变了】 HashCode 不相等 ---> equals 不一定
（equals 返回 true：是同类，对象内容一样，但不是同一对象，hashCode 不一样
equals 返回 false：不是同类，hashCode 不一样）
【变了】 equals 为 true ---> HashCode 不一定
（hashCode 相等：是同一对象
hashCode 不相等：是同类，对象内容一样，但不是同一对象）
【没变】 equals 为 false ---> HashCode 可能相等（仍要考虑是否存在hash冲突）
只重写了 HashCode（从由指定策略生成 HashCode，变为根据对象内容生成 HashCode）：
【没变】 HashCode 相等 ---> equals 不一定
【没变】 HashCode 不相等 ---> equals 一定为 false
【没变】 equals 为 true ---> HashCode 一定相等
【没变】 equals 为 false ---> HashCode 可能相等
只重写 HashCode，无意义，相当于改变了 HashCode 生成策略，对结果无影响，重写只会增加 hash 冲突的可能。
【经典面试题】：为什么重写对象的 equals 方法时，要重写 HashCode 方法？
答：违反 Object.hashCode 的通用约定，从而导致该类无法结合所有基于散列的集合一起正常运作，这样的集合包括 HashMap、HashSet 和 Hashtable。如：一个类有两个对象A1，A2，他们的A1.equals(A2) 为 true，但 A1.hashcode 和 A2.hashcode 不一样，当将 A1 和 A2 都作为 HashMap 的 key 时，HashMap 会认为它两不相等，会同时作为 key 存入。
二、HashCode 在 HashMap 中的应用
以 HashMap 的插入操作为例，插入步骤如下：
1、由 HashCode 获取插入对象的 hash 值；
2、对 hash 值按 map 容量取模，计算插入对象在数组中的存储位置；
3、该存储位置无其他对象，直接插入；有其他对象，则遍历该位置中的对象，比较 hash 值是否相等；
4、无相等的对象，则直接插入；有 hash 值相等的对象，则调用 equals 比较对象内容；
5、内容不相等，则直接插入；内容相等，则更新 val。
1、为什么 HashMap 先比较 hash 值而不是直接用 equals？
如果 Map 已有 1000 个 key，在插入第 1001 个 key 时，直接用 equals，就需要比较 1000 次；而通过 hash 值先计算存储位置，则只需要单独比较当前存储位置的 key 即可，提高效率。
2、关于 HashMap 的几个小点：
1、JDK7 中的底层实现是数组+链表，JDK8 中使用的是数组+链表+红黑树；
2、在 JDK8 之前，HashMap 等其他基于 Map 类都是用链地址法解决冲突，它们使用单向链表来存储相同索引值的元素，最坏的情况下，这种方法会使得 HashMap 的 get 方法的性能从 O(1) 降低到 O(n)。为了提高性能，JDK8 中使用平衡树来替代链表存储冲突的元素，那么最坏的性能从O(n) 提高到 O(logn)；
3、JDK7 中使用 Entry 来代表每个 HashMap 中的数据节点，JDK8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。
4、JDK8 中 HashMap 默认容量为16，若当前容量大于等于了扩容的阈值时会自动进行扩容；
5、HashMap 的扩容机制是很影响效率的，所以如果事先能确定有多少个元素需要存储，那么建议在初始化 HashMap 时对数组的容量也进行初始化，防止扩容。
详见：
Java开发面试官终结者！HashMap高频面试题总结，必拿下！https://baijiahao.baidu.com/s?id=1703973277855654462
Java 8中HashMap和linkedHashMap如何解决冲突_木霖森77的博客-CSDN博客什么时候会产生冲突??HashMap中调用hashCode()方法来计算hashCode。由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。解决：在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。从Java 8开始，HashMap，Concurr...https://blog.csdn.net/mulinsen77/article/details/84879833
为什么HashMap线程不安全？
1、如果多个线程同时使用 put 方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖；
2、如果多个线程同时检测到元素个数超过阈值，这样就会发生多个线程同时对数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组，也就是说其他线程的都会丢失。
什么导致 HashMap 出现死循环？
因为多线程会导致 HashMap 的节点形成环链，这样当遍历集合时 Entry 的 next 节点用于不为空，从而形成死循环。
三、一致性Hash
一致性 Hash 通过构建环状的 Hash 空间代替线性 Hash 空间，解决集群的数量 N 发生变化时，之前的所有 Hash 映射就会全部失效的问题。环形 Hash 空间由 2^32 个点组成，称为 Hash 环。
1、通过一致性 Hash 构建分布式缓存服务器
步骤如下：
1、首先求出memcached服务器（节点）的哈希值，并将其配置到 0～2^32 的圆上。
2、然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
3、然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过 2^32 仍然找不到服务器，就会保存到第一台memcached服务器上。
若要新增节点，则会影响到新增节点的顺时针方向上的下一个节点的保存内容。删除节点同理。
2、Hash 环常见问题：数据倾斜、缓存雪崩
数据倾斜：指分布式节点在环上分布不均匀，导致某些节点需要负责更多的 key，大量请求到来时，导致超负荷。
缓存雪崩：删除节点时，当前节点负责的 key，全部交给顺时针方向上的下一个节点处理，以此类推，若删除过多节点，会导致某些节点超负荷，造成缓存雪崩。
解决方案：引入虚拟节点，一个实际节点映射出多个虚拟节点，能够在 Hash 环上分布更加均匀；且在删除节点时，能够更加均匀的将自身所负责的 key 分配给其他节点。
3、节点缩扩容常见问题
缩扩容过程存在延时，在缩扩容数据准备过程中，可能会出现访问不到某些缓存，缓存击穿等问题。
缓存穿透：指缓存和数据库中都没有的数据，而用户不断发起请求，如发起为id为“-1”的数据或id为特别大不存在的数据。
缓存击穿：指缓存中没有但数据库中有的数据，这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大。
解决扩容延时
1、新节点提前预热高频 Key，但预热也需要时间，高频 Key 有效时间短，此时容易出现脏读。
2、保留旧 Hash 环，在扩容完成前，存在两个 Hash 环，新 Hash 环是扩容后的，旧 Hash 换是扩容前的，如果在新环找不到数据，就会转而访问旧环。该方案可以随意扩容多台机器，而不会产生大面积的缓存失效，但增加了缓存读取时间。
解决缩容延时
1、熔断机制，作为兜底方案，给每个节点设立对应熔断机制来保护服务的稳定性，防止删除节点后某些节点因为压力陡增而宕机。
2、节点已经删除，但负载均衡服务器没有来得及更新，导致请求转发给被删除的节点上，出现缓存击穿，解决这个问题主要有以下几种思路：
（a）缓慢缩容，等到Hash环完全同步后再操作。可以通过监听退出集群的访问QPS来实现这一点，等到该集群几乎没有QPS时再将其撤下。
（b）手动删除，如果Hash环上对应的节点找不到了，就手动将其从Hash环上删除，然后重新进行调度，这个方式有一定的风险，对于网络抖动等异常情况兼容的不是很好。
（c）主动拉取和重试，当Hash环上节点失效时，主动从ZK上重新拉取集群状态来构建新Hash环，在一定次数内可以进行多次重试。
一致性 hash 主要参考以下两篇文章：
面试必问的一致性Hash在负载均衡中的应用 - 云+社区 - 腾讯云一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为...https://cloud.tencent.com/developer/article/1798049一致性哈希算法原理 - lpfuture - 博客园一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致https://www.cnblogs.com/lpfuture/p/5796398.html
四、Hash 算法的其他应用
HashMap、HashSet 和 Hashtable 是 Hash 算法在 散列集合 的应用；
一致性 Hash 是 Hash 算法在 负载均衡 的应用；
除此之外，还有：
安全加密
MD5 算法 : Message Digest Algorithm MD5消息摘要算法
SHA 算法 : Secure Hash Algorithm 安全散列算法
DES 算法 : Data Encryption Standard 数据加密标准
AES 算法 : Advanced Encryption Standard 高级加密标准
对用于加密的哈希算法，有两个特别重要的要求: 1、很难通过Hash值推导出原始的字符串；2、散列冲突的概率要很小。
唯一标识
例如可以把每个图片的唯一标识，图片的路径都存储到散列表中，要查看什么图片的时候可以根据唯一标识去查到对应的图片。
数据校验
检验一个文件是否被修改过，可以通过对比 Hash 值是否变化，来校验数据的完整性和正确性。
数据分片
对海量数据的存储场景，比如，分布式缓存（Redis），判断该条数据分配在哪台 Redis 中。
