「实实在在面试」—List和Map集合面试合集【含讲解视频】

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第1张图片

前言

Tip:该笔记为B站面试讲解视频的配套文档,B站搜索”编程鹿“可以看到面试题讲解视频

视频地址如下:奥利给 编程人—2020年Java大厂面试题集锦(面试必备 持续更新)

https://www.bilibili.com/video/BV15i4y1L7Bt

什么是数组

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第2张图片

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

特点:

  1. 线性表 物理内存上连续还是逻辑上连续的数据结构都称之为线性表
  2. 连续的内存空间和相同类型的数据

优点:

  1. 按照下标访问快「随机访问」(直接访问 任意访问)

    假如:每个元素占据长度 为 3,第一个元素开始地址编号为 10

    那么只要知道下标 就可以快速计算出来运算的地址

    第三个元素位置为:10+2*3 =16

缺点:

  1. 数据插入 需要扩容和挪动元素
  2. 删除元素 也需要挪动元素

什么是链表

链表通过指针将一组零散的内存块串联在一起的线性数据结构,把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址,记录下个结点地址的指针叫作后继指针 next

如下图所示:

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第3张图片

特点:

  1. 线性表 通过“指针”将一组零散的内存块串联

优点:

  1. 增删快 不需要元素搬移

缺点:

  1. 查询慢 需要通过前结点 获取后结点的地址

其他链表:

  1. 循环链表

    「实实在在面试」—List和Map集合面试合集【含讲解视频】_第4张图片

  2. 双向链表 插入 删除更加高效 查询可以双向遍历

    「实实在在面试」—List和Map集合面试合集【含讲解视频】_第5张图片

ArrayList 和 LinkedList 的区别

数据结构实现

  • ArrayList 是数组的数据结构实现
  • LinkedList 是双向链表的数据结构实现。

访问效率

  • ArrayList 比LinkedList 在下标访问的时候效率要高
  • LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。

增加和删除效率

  • 在非首尾的增加和删除操作,LinkedList 要比ArrayList效率要高,因为ArrayList增删操作要影响数组内的其他数据的下标。.

综合来说,在需要频繁读取集合中的元素时,更推荐使用ArrayList,而在插入和删除操作较多时,更推荐使用LinkedList。

ArrayList 初始化长度多少

ArrayList 底层是数组,ArrayList 初始长度为 10

  • 1.8 之前 ArrayList 初始长度为 10
  • 1.8 之后

    • 通过无参构造方法第一次创建集合的时候不会创建底层长度为10的数组
    • 在第一次添加的元素的时候 创建底层数组 长度为10

      「实实在在面试」—List和Map集合面试合集【含讲解视频】_第6张图片

ArrayList 如何添加元素

按照下标添加,每次添加都会判断集合的容量

  • 第一次添加 会创建长度为10的底层数组
  • 后续添加 如果容量不足 会扩容

ArrayList 如何扩容

什么时候发生扩容:

  1. 每次添加的时候 会检查要不要扩容 执行ensureCapacityInternal 确保内部容量

    「实实在在面试」—List和Map集合面试合集【含讲解视频】_第7张图片

  2. ensureCapacityInternal 会判断数组长度够不够 不够就扩容

扩容流程:

  1. 判断数组长度够不够添加新元素

    「实实在在面试」—List和Map集合面试合集【含讲解视频】_第8张图片

  2. 不够就触发扩容 grow方法

    //真正的扩容
     private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
       //新的容量是在原有的容量基础上+50% 右移一位就是二分之一
            int newCapacity = oldCapacity + (oldCapacity >> 1);
       //如果新容量小于最小容量,按照最小容量进行扩容
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
       //这里是重点 调用工具类Arrays的copyOf扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    • 扩容 1.5 倍
    • 扩容需要赋值数据

创建集合的时候如果能够预估长度,最好指定集合大小

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第9张图片

ArrayList 和 Vector 的区别

ArrayList 线程不安全

Vector 线程安全 Vector几乎所有的方法都加了锁

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第10张图片

除了 Vector 还有什么线程安全的List

CopyOnWriteArrayList 读不加锁写加锁

复制写:复制一个新数组 将元素添加新数组中

public boolean add(E e) {
    创建锁对象
    final ReentrantLock lock = this.lock;
    加锁
    lock.lock();
    try {
        获取现有数组
        Object[] elements = getArray();
        获取现有数组长度
        int len = elements.length;
        根据现有数组得到一个长度+1的新数组 【复制】
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        将要添加的元素 写入新数组中
        newElements[len] = e;
        用新数组替换老数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

HashMap的底层结构

1.7 数组+链表

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第11张图片

1.8 数组+链表+红黑树

如果链表的长度大于8 链表就会处理为树结构

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第12张图片

HashMap 默认初始化大小是多少?

默认初始值 16

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第13张图片

HashMap的主要参数都有哪些?

默认初始值(数组的长度):16

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第14张图片

负载因子:0.75

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第15张图片

扩容的条件:当底层数组 四分之三 的位置有了元素 就扩容

HashMap是怎么处理hash碰撞的?

hash碰撞,两个key计算的结果都是同一个下标

  • 链表
  • 链表+树

HashMap 新的Entry节点在插入链表的时候,是怎么插入的

Entry

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第16张图片

  • 在JDK8之前是头插法,新的值会取代原有的值,原有的值会被推到链表上
  • 在JDK8之后是尾插法

    • 头插法可能出现循环链表的问题
    • 使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。
    • Java7在多线程操作 HashMap 时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。

HashMap的扩容机制?

  1. 什么时候扩容?(risize)

    HashMap的底层是数组,数组的容量有限,到达一定的数量就会进行扩容。

    影响扩容时机的因素有两个:

    • Capacity:HashMap当前长度
    • LoadFactor:负载因子,默认值0.75f

什么意思呢?当数组中75%的位置满了的时候,就会进行扩容。想要晚的触发扩容就只能调高负载因子。

  1. 怎么扩容?

    扩容分为两步

    1. 扩容:创建一个新的Entry空数组,长度是原数组的2倍
    2. ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组

      进行重新Hash的原因:Hash的计算和数组的长度有关(对长度位运算)HashCode(Key) & (Length - 1)。所以长度改变了,所有的元素复制到新数组中需要重新计算位置

HashMap 线程安全吗?

不是

有哪些线程安全的 Map

Hashtable

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第17张图片

ConcurrentHashMap

ConcurrentHashMap 基本原理

1.7 分段锁

「实实在在面试」—List和Map集合面试合集【含讲解视频】_第18张图片

1.8 CAS 无锁算法(乐观锁)

加不加锁为条件进行分类

  • 悲观锁 确实加锁了 一个线程操作的时候会持有锁对象 其他线程需要等到拿到锁对象的时候才能操作元素
  • 乐观锁 算法控制 逻辑锁

    原子性 Integer AtomicInteger 实现原子性的自增

HashSet

HashSet 底层是HashMap 只使用HashMap的key 不使用value

Queue

Queue ---》线程池

「❤️ 帅气的你又来看了我」

如果你觉得这篇内容对你挺有有帮助的话:

  1. 点赞支持下吧,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
  2. 欢迎在留言区与我分享你的想法,也欢迎你在留言区记录你的思考过程。

你可能感兴趣的