## 为什么重写equals方法还要重写hashcode方法

1. Object 的 hashcode 方法是本地方法，也就是用 c 或 c++ 实现的，该方法直接返回对象的内存地址，让后再转换整数。
2.	Equals方法
	1.	两个对象的Hashcode值相等，但是两个对象的内容值不一定相等；---Hash冲突的问题
	2.	两个对象的值Equals比较相等的情况下，则两个对象的Hashcode值一定相等；

 == 比较两个对象的内存地址是否相同、Equals默认的情况下比较两个对象的内存地址
1. 【强制】关于 hashCode 和 equals 的处理，遵循如下规则：
1） 只要覆写 equals，就必须覆写 hashCode。
2） 因为 Set 存储的是不重复的对象，依据 hashCode 和 equals 进行判断，所以 Set 存储的对象必须覆写这两个方法。
3） 如果自定义对象作为 Map 的键，那么必须覆写 hashCode 和 equals。
4）为了避免内存泄漏----强引用
说明：String 已覆写 hashCode 和 equals 方法，所以我们可以愉快地使用 String 对象作为 key 来使用。

## HashMap底层实现原理

### 1. 基于Arraylist集合方式实现

优点：不需要考虑hash碰撞的问题 缺点：时间复杂度为O(n)

### 2. 基于数组+链表方式实现(Jdk1.7)

单向链表
数组初始容量：16
元素头插法
hashmap中key如果没有发生碰撞的问题，get查询时间复杂度是O(1)，直接根据下标查询。
如果发生hash碰撞问题（hashcode值相同，内容不同），复杂度为O(n)

### 3. 基于数组+链表方式+红黑树(Jdk1.8)

## HashMap底层是有序存放的吗？

无序、散列存放
元素尾插法
遍历的时候从数组0开始遍历每个链表，遍历结果存储顺序不保证一致。
如果需要根据存储顺序保存，可以使用LinkedHashMap底层是基于双向链表存放
LinkedHashMap基于双向链表实现
HashMap基本单向链表实现

## LinkedHashMap实现缓存淘汰框架

有序的HashMap集合 存放顺序 双向链表
效率比HashMap低，
原理：将每个index链表实现关联

LRU(最近少使用)缓存淘汰算法 -- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；当链表满的时候，将链表尾部的数据丢弃。
LFU(最不经常使用算法)缓存淘汰算法 -- LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。
ARC(自适应缓存替换算法)缓存淘汰算法
FIFO（先进先出算法）缓存淘汰算法
MRU(最近最常使用算法)缓存淘汰算法

实现LRU算法
插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。

其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序,false根据新增顺序

## HashMap如何降低Hash冲突概率

```java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
为什么n-1变成一个奇数？
每次扩容都扩容成2的幂，不是奇数hash碰撞概率较大

1、保证不会发生数组越界
首先我们要知道的是，在HashMap，数组的长度按规定一定是2的幂。因此，数组的长度的二进制形式是：10000…000, 1后面有偶数个0。 那么，length - 1 的二进制形式就是01111.111, 0后面有偶数个1。最高位是0, 和hash值相“与”，结果值一定不会比数组的长度值大，因此也就不会发生数组越界。一个哈希值是8，二进制是1000，一个哈希值是9，二进制是1001。和1111“与”运算后，结果分别是1000和1001，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。