第一节课数组加链表&时间复杂度的对比.md 3.5 KB

为什么重写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(最不经常使用算法)缓存淘汰算法 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,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。