第一节课数组加链表&时间复杂度的对比.md 3.5 KB
为什么重写equals方法还要重写hashcode方法
- Object 的 hashcode 方法是本地方法，也就是用 c 或 c++ 实现的，该方法直接返回对象的内存地址，让后再转换整数。
- Equals方法
- 两个对象的Hashcode值相等，但是两个对象的内容值不一定相等；---Hash冲突的问题
- 两个对象的值Equals比较相等的情况下，则两个对象的Hashcode值一定相等；
== 比较两个对象的内存地址是否相同、Equals默认的情况下比较两个对象的内存地址
- 【强制】关于 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(最不经常使用算法)缓存淘汰算法 ARC(自适应缓存替换算法)缓存淘汰算法 FIFO（先进先出算法）缓存淘汰算法 MRU(最近最常使用算法)缓存淘汰算法
实现LRU算法 插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序 执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序,false根据新增顺序
HashMap如何降低Hash冲突概率
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，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。