ArrayList

LIst

ArrayList

基于数组实现，增删慢，查询快，线程不安全

  • ArrayList是使用最广泛的List实现类，其内部数据结构基于数组实现，提供了对List的增加（add）、删除（remove）和访问（get）功能。ArrayList的缺点是对元素必须连续存储，当需要在ArrayList的中间位置插入或者删除元素时，需要将待插入或者删除的节点后的所有元素进行移动，其修改代价较高，因此，ArrayList不适合随机插入和删除的操作，更适合随机查找和遍历的操作。ArrayList不需要在定义时指定数组的长度，在数组长度不能满足存储要求时，ArrayList会创建一个新的更大的数组并将数组中已有的数据复制到新的数组中。

ArrayList的扩容机制

Vector

基于数组实现，增删慢，查询快，线程安全

  • Vector的数据结构和ArrayList一样，都是基于数组实现的，不同的是Vector支持线程同步，即同一时刻只允许一个线程对Vector进行写操作（新增、删除、修改），以保证多线程环境下数据的一致性，但需要频繁地对Vector实例进行加锁和释放锁操作，因此，Vector的读写效率在整体上比ArrayList低。

基于双向链表实现，增删快，查询慢，线程不安全

  • LinkedList采用双向链表结构存储元素，在对LinkedList进行插入和删除操作时，只需在对应的节点上插入或删除元素，并将上一个节点元素的下一个节点的指针指向该节点即可，数据改动较小，因此随机插入和删除效率很高。但在对LinkedList进行随机访问时，需要从链表头部一直遍历到该节点为止，因此随机访问速度很慢。除此之外，LinkedList还提供了在List接口中未定义的方法，用于操作链表头部和尾部的元素，因此有时可以被当作堆栈、队列双向队列使用。

Q1：ArrList与LinkList的区别

底层数据结构的实现不一样，A的底层是基于数组实现的，L的底层是基于双向链表实现的

由于A的底层，所以规定他对于查询的操作会很快，但是对于删除或者新增的操作会很慢，原因是一旦发生改变，所有的数组下表都会发生改变，但是查询却可以利用下标。

A的线程不安全，分析源码可以知道，A的数组添加操作没有加锁

1
2
3
4
5
6
7
8
//Appends the specified element to the end of this list.
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

JAVA

解决思路：

  • 1.Vector
  • 2.Collections.synchronizedList()
  • 3.CopyOnWrite(写时复制)

Vector

运行后发现并没有出现线程不安全的问题(没有出现并发修改异常),我们查看Vector类的源码发现它的方法都用synchronized修饰，所以Vector是线程安全的，但是性能比较低

1
2
3
4
5
6
7
8
9
10
11
12
13
class VectorDemo{
    static Vector<String> vector=new Vector<>();
    public static void main(String[] args) {
        for (int i = 0; i <10 ; i++) {
            new Thread(()->{
                vector.add(UUID.randomUUID().toString().substring(0,8));
                System.out.println(vector);
            }).start();
        }
    }
}

JAVA

Collections.synchronizedList()

Collections.synchronizedList(list)，相当于Collections工具类提供了一个方法给原来没有加锁的集合加锁，当然类似的还有Collections.synchronizedMap(), Collections.synchronizedSet()等等

写时复制(重点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class CopyOnWriteDemo {
    static List<String> list = new CopyOnWriteArrayList<>();

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }).start();
        }
    }
}


//add源码
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

JAVA
  • CopyOnWriteArrayList就是写时复制的容器,每次添加Objcet对象时不是直接向原Object[]数组中添加,而是复制一个长度为原数组长度+1的新数组，把要添加的数据写到新数组上。
  • 写完之后在把原来的引用指向新数组setArray(newElements),最后再释放锁，让其他线程进行写操作。

image.png

image.png

  • 这样做的好处是在进行读操作的时候不用加锁，保证了并发性，同时这也是读写分离思想的体现。

L的底层数据结构是双向链表，所以L对于删除和新增很快，只需要前后指针的指向就可以添加，但是对于查询就会很慢，因为需要遍历整个数组才能够找到，LinkedList还提供了在List接口中未定义的方法，用于操作链表头部和尾部的元素，同是也是线程不安全的。

L的线程不安全是因为他的底层方法是直接调用的A的add方法。

Q2：ArrList与Vector的区别

线程安全的区别

Q3：Vector与LInkLIst的区别

数据结构和线程安全，L多一个操作头尾的方法

Queue

Queue是队列结构，Java中的常用队列如下。

  • ◎ ArrayBlockingQueue：基于数组数据结构实现的有界阻塞队列。
  • ◎ LinkedBlockingQueue：基于链表数据结构实现的有界阻塞队列。
  • ◎ PriorityBlockingQueue：支持优先级排序的无界阻塞队列。
  • ◎ DelayQueue：支持延迟操作的无界阻塞队列。
  • ◎ SynchronousQueue：用于线程同步的阻塞队列。
  • ◎ LinkedTransferQueue：基于链表数据结构实现的无界阻塞队列。
  • ◎ LinkedBlockingDeque：基于链表数据结构实现的双向阻塞队列。

Set

不可重复

JDK 7 中的 HashMap 是采用头插法的，即 [why技术] 在 [eat] 之前，JDK 8 中的 HashMap 采用的是尾插法。

Set核心是独一无二的性质，适用于存储无序且值不相等的元素。对象的相等性在本质上是对象的HashCode值相同，Java依据对象的内存地址计算出对象的HashCode值。如果想要比较两个对象是否相等，则必须同时覆盖对象的hashCode方法和equals方法，并且hashCode方法和equals方法的返回值必须相同。

1.HashSet：HashTable实现，无序

HashSet存放的是散列值，它是按照元素的散列值来存取元素的。元素的散列值是通过元素的hashCode方法计算得到的，HashSet首先判断两个元素的散列值是否相等，如果散列值相等，则接着通过equals方法比较，如果equls方法返回的结果也为true，HashSet就将其视为同一个元素；如果equals方法返回的结果为false，HashSet就不将其视为同一个元素。

2.TreeSet：二叉树实现

TreeSet基于二叉树的原理对新添加的对象按照指定的顺序排序（升序、降序），每添加一个对象都会进行排序，并将对象插入二叉树指定的位置。Integer和String等基础对象类型可以直接根据TreeSet的默认排序进行存储，而自定义的数据类型必须实现Comparable接口，并且覆写 其 中 的 compareTo 函 数 才 可 以 按 照 预 定 义 的 顺 序 存 储 。 若 覆 写
compare 函 数 ， 则 在 升 序 时 在 this. 对 象 小 于 指 定 对 象 的 条 件 下 返回-1，在降序时在this.对象大于指定对象的条件下返回1。

3.LinkHashSet：HashTable实现数据存储，双向链表记录顺序

LinkedHashSet 在 底 层 使 用 LinkedHashMap 存 储 元 素 ， 它 继 承 了HashSet，所有的方法和操作都与HashSet相同，因此LinkedHashSet的实现比较简单，只提供了 4个构造方法，并通过传递一个标识参数调用父类的构造器，在底层构造一个LinkedHashMap来记录数据访问，其他相关操作与父类HashSet相同，直接调用父类HashSet的方法即可。

Map

1.HashMap：数组+链表存储数据，线程不安全

HashMap基于键的HashCode值唯一标识一条数据，同时基于键的
HashCode值进行数据的存取，因此可以快速地更新和查询数据，但其
每次遍历的顺序无法保证相同。HashMap的key和value允许为null。
HashMap 是 非 线 程 安 全 的 ， 即 在 同 一 时 刻 有 多 个 线 程 同 时 写
HashMap时将可能导致数据的不一致。如果需要满足线程安全的条件，
则可以用Collections的synchronizedMap方法使HashMap具有线程安全
的能力，或者使用ConcurrentHashMap。
HashMap的数据结构如图 2-2所示，其内部是一个数组，数组中的
每个元素都是一个单向链表，链表中的每个元素都是嵌套类Entry的实
例，Entry实例包含4个属性：key、value、hash值和用于指向单向链
表下一个元素的next。
图2-2
HashMap常用的参数如下。◎ capacity：当前数组的容量，默认为 16，可以扩容，扩容后
数组的大小为当前的两倍，因此该值始终为2 。
n
◎ loadFactor：负载因子，默认为0.75。
◎ threshold：扩容的阈值，其值等于capacity×loadFactor。
HashMap在查找数据时，根据HashMap的Hash值可以快速定位到数
组的具体下标，但是在找到数组下标后需要对链表进行顺序遍历直到
找到需要的数据，时间复杂度为O( )。
n
为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据
结构修改为数组+链表或红黑树。在链表中的元素超过 8个以后，
HashMap会将链表结构转换为红黑树结构以提高查询效率，因此其时间
复杂度为O(log )。Java 8 HashMap的数据结构如图2-3所示。
N
图2-3

2.ConcurrentHashMap：分段锁实现，线程安全

与HashMap不同，ConcurrentHashMap采用分段锁的思想实现并发操 作 ， 因 此 是 线 程 安 全 的 ConcurrentHashMap 由 多 个 Segment 组 成（ Segment 的 数 量 也 是 锁 的 并 发 度 ） ， 每 个 Segment 均 继 承 自ReentrantLock并单独加锁，所以每次进行加锁操作时锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全
局的线程安全。ConcurrentHashMap的数据结构如图2-4所示。在 ConcurrentHashMap 中 有 个 concurrencyLevel 参 数 表 示 并 行 级别，默认是 16，也就是说ConcurrentHashMap默认由 16个Segments组成，在这种情况下最多同时支持 16个线程并发执行写操作，只要它们的操作分布在不同的Segment上即可。并行级别concurrencyLevel可以在初始化时设置，一旦初始化就不可更改。ConcurrentHashMap的每个Segment内部的数据结构都和HashMap相同。

Java 8在ConcurrentHashMap中引入了红黑树，具体的数据结构

3.HashTable：线程安全

HashTable是遗留类，很多映射的常用功能都与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，同一时刻只有一个线程能写HashTable，并发性不如ConcurrentHashMap。

4.TreeMap：基于二叉树数据结构

TreeMap基于二叉树数据结构存储数据，同时实现了SortedMap接口以保障元素的顺序存取，默认按键值的升序排序，也可以自定义排序比较器。
TreeMap常用于实现排序的映射列表。在使用TreeMap时其key必须实 现 Comparable 接 口 或 采 用 自 定 义 的 比 较 器 ， 否 则 会 抛 出java.lang.ClassCastException异常。

5.LinkedHashMap：基于HashTable数据结构，使用链表保存插入顺序

LinkedHashMap为HashMap的子类，其内部使用链表保存元素的插入顺序，在通过Iterator遍历LinkedHashMap时，会按照元素的插入顺序访问元素。

Java
#Java
ArrayList
https://lfrok.top/2022/11/27/Java/集合/
作者
B612🚀
发布于
2022年11月27日
许可协议