💂 个人主页: Java程序鱼

💬 如果文章对你有帮助，欢迎关注、点赞、收藏(一键三连)和订阅专栏

👤 微信号：hzy1014211086，想加入技术交流群的小伙伴可以加我好友，群里会分享学习资料、学习方法

序号	内容	链接地址
1	Java基础知识面试题	https://blog.csdn.net/qq_35620342/article/details/119636436
2	Java集合容器面试题	https://blog.csdn.net/qq_35620342/article/details/119947254
3	Java并发编程面试题	https://blog.csdn.net/qq_35620342/article/details/119977224
4	Java异常面试题	https://blog.csdn.net/qq_35620342/article/details/119977051
5	JVM面试题	https://blog.csdn.net/qq_35620342/article/details/119948989
6	Java Web面试题	https://blog.csdn.net/qq_35620342/article/details/119642114
7	Spring面试题	https://blog.csdn.net/qq_35620342/article/details/119956512
8	Spring MVC面试题	https://blog.csdn.net/qq_35620342/article/details/119965560
9	Spring Boot面试题	https://blog.csdn.net/qq_35620342/article/details/120333717
10	MyBatis面试题	https://blog.csdn.net/qq_35620342/article/details/119956541
11	Spring Cloud面试题	待分享
12	Redis面试题	https://blog.csdn.net/qq_35620342/article/details/119575020
13	MySQL数据库面试题	https://blog.csdn.net/qq_35620342/article/details/119930887
14	RabbitMQ面试题	待分享
15	Dubbo面试题	待分享
16	Linux面试题	待分享
17	Tomcat面试题	待分享
18	ZooKeeper面试题	待分享
19	Netty面试题	待分享
20	数据结构与算法面试题	待分享

文章目录

前言
一、List
- 1.ArrayList
- - 构造器
  - add()
  - addAll()
  - get()
  - remove()
  - 快速失败机制
  - ArrayList如何把元素序列化？
- 2.LinkedList
- - 双向链表数据结构
  - 插入元素的原理
  - 获取元素的原理
  - 删除元素的原理
- 3.Vector&Stack
二、Map
- 1.HashMap
- - 核心成员变量
  - 优化后的降低冲突概率的hash算法
  - put操作原理
  - JDK1.8红黑树优化
  - 基于数组扩容原理
  - get()
- 2.LinkedHashMap
- - newNode()
  - afterNodeInsertion
  - afterNodeAccess
- 3.TreeMap
三、Set
- 1.HashSet
- 2.LinkedHashSet
- 3.TreeSet

前言

为什么要学习JDK源码？
各种各样的系统或者技术，最底层、最最核心的一块，其实都是集合（在内存里面存放数据）、并发（分布式系统，底层都会开多个线程，并发的处理一些东西，这里会涉及到一些锁，同步，等等）、IO（读写磁盘上的文件里的数据，发起网络IO，通过网络读写数据）、网络（如何在分布式系统中，各个机器建立网络连接，互相发送请求进行通信），本期先给大家分享集合源码。

一、List

List 是有序的 Collection

List中的元素是有序的、可重复的，主要实现方式有动态数组和链表。

java中提供的List的实现主要有ArrayList、LinkedList、CopyOnWriteArrayList，另外还有两个古老的类Vector和Stack。

在这里插入图片描述

1.ArrayList

ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。
ArrayList实现了List，提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess，提供了随机访问的能力。
ArrayList实现了Cloneable，可以被克隆。
ArrayList实现了Serializable，可以被序列化。
AbstractCollection：主要实现了toString()、toArray()、contains()
AbstractList：主要实现了equals()、hashCode()

缺点：
①数组长度固定，java里面数组都是定长数组，比如数组大小设置为100，此时你不停的往ArrayList里面塞入这个数据，此时元素数量超过了100以后，此时就会发生一个数组的扩容，就会搞一个更大的数组，把以前的数组拷贝到新的数组里面去，这个数组扩容+元素拷贝的过程，相对来说会慢一些
②中间插入慢，数组来实现，数组你要是往数组的中间加一个元素，要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，性能比较差，会导致他后面的大量的元素挪动一个位置

优点：
①支持随机访问，通过索引访问元素极快，时间复杂度为O(1)

核心参数：

/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空数组，如果传入的容量为0时使用

*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 存储元素的数组
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* 集合中元素的个数
*/
private int size;

（1）DEFAULT_CAPACITY 默认容量为10，也就是通过new ArrayList()创建时的默认容量。
（2）EMPTY_ELEMENTDATA 空的数组，这种是通过new ArrayList(0)创建时用的是这个空数组。
（3）DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组，这种是通过new ArrayList()创建时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY（10）个元素。
（4）elementData 真正存放元素的地方，使用transient是为了不序列化这个字段。至于没有使用private修饰，后面注释是写的“为了简化嵌套类的访问”，但是楼主实测加了private嵌套类一样可以访问。 private表示是类私有的属性，只要是在这个类内部都可以访问，嵌套类或者内部类也是在类的内部，所以也可以访问类的私有成员。
（5）size 真正存储元素的个数，而不是elementData数组的长度。

核心方法：

构造器

（1）不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，会在添加第一个元素的时候扩容为默认的大小，即10。

public ArrayList() {
      // 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
      // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

（2）ArrayList(int initialCapacity)构造方法，传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常

public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
       }
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组，这种是通过new ArrayList()创建时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY（10）个元素。

（3）ArrayList(Collection c)构造方法

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为0，则初始化为EMPTY_ELEMENTDATA空数组。

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

根据业务预测初始化的数组的大小，避免数组太小，往里面塞入数据的时候，导致数据不断的扩容，不断的搞新的数组

add()

（1）默认添加

添加元素到size+1位置，平均时间复杂度为O(1)。

public boolean add(E e) {
       // 检查是否需要扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       // 把元素插入到最后一位
       elementData[size++] = e;
       return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 判断是否需要扩容：size + 1 - 当前数组长度 > 0时扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

补充：当前数组长度10，添加第11个元素时才扩容

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新容量是老容量的1.5倍（oldCapacity + (oldCapacity >> 1)）
        // 老的大小 + 老的大小 >> 1（相当于除以2）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果加了这么多容量发现比需要的容量还小，则以需要的容量为准
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建新容量的数组并把老数组拷贝到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
}

补充：空参构造器，第一次初始化时，就需要以需要的容量为准，因为0+(0>>1)=0

（2）添加到指定位置

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 把插入索引位置后的元素都往后挪一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在插入索引位置放置插入的元素
        elementData[index] = element;
        size++;
}

addAll()

public boolean addAll(Collection<? extends E> c) {

    Object[] a = c.toArray();
    int numNew = a.length;

    ensureCapacityInternal(size + numNew);  // Increments modCount

    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

}

①将集合C转化为数组a
②获取数组a长度
③判断是否需要扩容

get()

获取指定索引位置的元素，时间复杂度为O(1)。

public E get(int index) {

    rangeCheck(index);
    return elementData(index);

}

private void rangeCheck(int index) {

    if (index >= size)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

E elementData(int index) {

    return (E) elementData[index];

}

remove()

（1）通过索引删除
删除指定索引位置的元素，时间复杂度为O(n)。

public E remove(int index) {

    rangeCheck(index);
    modCount++;

    E oldValue = elementData(index);

    int numMoved = size - index - 1;

    // 如果index不是最后一位，则将index之后的元素往前挪一位
    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;

}

private void rangeCheck(int index) {

    if (index < 0 || index >= this.size)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

（2）通过元素删除

删除指定元素值的元素，时间复杂度为O(n)。

public boolean remove(Object o) {

    if (o == null) {

        for (int index = 0; index < size; index++)

            if (elementData[index] == null) {

                fastRemove(index);
                return true;
            }

    } else {

        for (int index = 0; index < size; index++)

            if (o.equals(elementData[index])) {

                fastRemove(index);
                return true;
            }

    }
    return false;

}

private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // clear to let GC do its work

}

①找到第一个等于指定元素值的元素；
②快速删除；

fastRemove(int index)相对于remove(int index)少了检查索引越界的操作，可见jdk将性能优化到极致。

6.迭代器

private class Itr implements Iterator<E> {

    ...
}
private class ListItr extends Itr implements ListIterator<E> {

    ...
}

ListItr继承了Itr和ListIterator，ListIterator有插入和修改删除方法，同时还具有向前遍历的方法，所以ListIterator就具备了增删改查的功能，比Itr的功能更加齐全

快速失败机制

假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast。
在这里插入图片描述

检查modCount标识符

final void checkForComodification() {

    if (modCount != expectedModCount)

        throw new ConcurrentModificationException();

}

无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值（都是modCount+1）。

ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常！

ArrayList如何把元素序列化？

elementData设置成了transient，那ArrayList是怎么把元素序列化的呢？

一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。（用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程）

Serializable：一个对象序列化的接口，一个类只有实现了Serializable接口，它的对象才是可序列化的。
Serializeble的作用仅仅是一个标识这个类是可序列化的

什么情况下需要序列化？（应用场景）
①将内存对象保存到磁盘中或数据库中（持久化）。
②最常见的用法，web客服端连接服务器的时候，假如连接的客服端比较多，这时服务端压力比较大（内存不足），为了解决这些问题，把一些Session序列化，存入硬盘用的时候拿出来。
③在跨平台环境下，通过网络传输对象的时候需要序列化，例如WebService SOAP

transient：表示方法和属性等成员变量是透明的，不参与序列化。
static：静态变量不能序列化

什么是序列化和反序列化？
序列化机制：将内存Java 对象通过字节输出流写入硬盘（大部分是乱码，因为是二进制）。
反序列化机制：通过字节输入流从硬盘中文件中把对象读到内存中。（字节序列转换成Java对象）
为什么要有序列号？

如果没有给序列号，会根据属性和方法算出序列号，若属性和方法改变会报错，因为序列号不同，若加了序列号，可以添删属性，改变toString都不会报错
elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

总结：
（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；

2.LinkedList

LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用
在这里插入图片描述
ArrayList+Deque

因为ArrayList代表了List的典型实现，LInkedList代表了Deque的典型实现，同时LinkedList也实现了List，通过这两个类一首一尾正好可以把整个集合贯穿起来。

优点：
①插入性能高，不管是从末尾插入还是中间插入

缺点：
随机读性能差，例如LinkedList.get(10)，这种操作，性能就很低，因为他需要遍历这个链表，从头开始遍历这个链表，直到找到index = 10的这个元素为止

使用场景

（1）ArrayList：一般场景，都是用ArrayList来代表一个集合，只要别频繁的往里面插入和灌入大量的元素就可以了，遍历，或者随机查，都可以

（2）LinkedList：适合，频繁的在list中插入和删除某个元素，然后尤其是LinkedList他其实是可以当做队列来用的，这个东西的话呢，我们后面看源码的时候，可以来看一下，先进先出，在list尾部怼进去一个元素，从头部拿出来一个元素。如果要在内存里实现一个基本的队列的话，可以用LinkedList

我们之前在电商系统开发的时候，在第一个版本中，用到了内存队列，用的就是LinkedList，他里面基于链表实现，天然就可以做队列的数据结构，先进先出，链表来实现，特别适合频繁的在里面插入元素什么的，也不会导致数组扩容

其实在工作中使用的时候，都是用的是java并发包下面的一些线程安全的集合，这个东西等到讲java并发包的时候，我们可以再来看一下

LinkedList作为队列使用
offer()，就是在队列尾部入队，将一个元素插入队列尾部
poll()，从队列头部出队
peek()，获取队列头部的元素，但是头部的元素不出队
offerFirst()
offerLast()

双向链表数据结构

item是元素
prev、next是指针
在这里插入图片描述

插入元素的原理

（1）尾部插入

add()，默认就是在队列的尾部插入一个元素，在那个双向链表的尾部插入一个元素
addLast()，跟add()方法是一样的，也是在尾部插入一个元素

在这里插入图片描述

public boolean add(E e) {
     linkLast(e);
     return true;
}

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}

（2）队列中间插入

add(index, element)，是在队列的中间插入一个元素

在这里插入图片描述

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
}

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}

（3）头部插入

在这里插入图片描述

addFirst()，在队列的头部插入一个元素

public void addFirst(E e) {
     linkFirst(e);
}

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
}

获取元素的原理

（1）获取头部元素

getFirst() 获取头部的元素，他其实就是直接返回first指针指向的那个Node他里面的数据，他们都是返回头部的元素。getFirst()如果是对空list调用，会抛异常；peek()对空list调用，会返回null

（2）获取尾部元素

getLast()：获取尾部的元素，他其实就是直接返回last指针指向的那个Node他里面的数据

public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
 }

（3）获取中间的元素

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

Node<E> node(int ind

网络知识

我把面试问烂了的⭐Java集合⭐总结了一下（带答案，万字总结，精心打磨，建议收藏）

文章目录

前言

一、List

1.ArrayList

构造器

add()

addAll()

get()

remove()

快速失败机制

ArrayList如何把元素序列化？

2.LinkedList

双向链表数据结构

插入元素的原理

获取元素的原理

文章目录

前言

一、List

1.ArrayList

构造器

add()

addAll()

get()

remove()

快速失败机制

ArrayList如何把元素序列化？

2.LinkedList

双向链表数据结构

插入元素的原理

获取元素的原理

相关文章

央媒谈“文盲演员”引发饭圈甩锅大战

野生大熊猫深夜遛达 镜头前呆萌打卡

张萌谈演员到底需不需要有文化

情人节多地迎领证高峰

婚房烂尾10年业主住进毛坯房

多地首套房贷利率降至4%以下 为什么急于提前还贷

野生大熊猫深夜遛达镜头前呆萌打卡

多地首套房贷利率降至4%以下为什么急于提前还贷