Java集合

阅读数: 次 2021-07-15

java集合也叫做容器，主要由Collection 和 Map 两大接口派生出来

Collection : 单列集合，存放单一元素；
Map : 双列集合，存放 key - value键值对；

其中 Collection接口继承自 Iterable 接口，并且主要派生出 List Queue Set 三个子接口，具体实现类如下图所示 :

List

List的特点主要就是 有序的 、可重复

主要实现类有 ArrayList、 LinkedList、Vector;

实现类	底层实现	特点
ArrayList	`Object[]`数组	查找快、增删慢
Vector	`Object[]`数组	底层方法由`synchronized`修饰，支持线程同步
LinkedList	双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)	查找慢、增删快，同时实现了`Deque` 接口可以当做栈及队列来使用

ArrayList

ArrayList 的底层是Object[]数组，与java基本的数组不同的是，ArrayList有扩容机制，在添加大量元素前，ArrayList扩容机制会先判断当前数组大小是否够用，如果不够用就进行扩容，这样就减少了数组因频繁创建拷贝而造成的资源浪费。

ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

public class ArrayList<E> extends AbstractList<E> 
    implements List<E>, RandomAccess, Cloneable, Serializable {
    
    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10; //默认初始容量大小
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0]; //空数组 -> 用于空参构造器
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    transient Object[] elementData; //实际存储数据的数组
    private int size; //全局变量 -> 数组的大小
    private static final int MAX_ARRAY_SIZE = 2147483639; //定义数组最大容量 -> 对数组扩容做限制
    
}

RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。数组天然支持随机访问，时间复杂度为O(1)，所以称为快速随机访问，RandomAccess仅仅起到标识作用，并不是说实现了它才具有的快速随机访问功能。
ArrayList 实现了 Cloneable 接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

LinkedList

LinkedList是一个实现了List接口和Deque接口的双向链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作。实现了Deque接口，使得LinkedList类也具有队列的特性;，同时LinkedList不是线程安全的

public class LinkedList<E> extends AbstractSequentialList<E> 
	implements List<E>, Deque<E>, Cloneable, Serializable {
    
    transient int size; //节点的数量
    transient LinkedList.Node<E> first; //全局变量--> 指向双向链表的头节点
    transient LinkedList.Node<E> last; //全局变量--> 指向双向链表的尾节点
    private static final long serialVersionUID = 876323262645176354L;
}

Node 内部私有类–> 链表的节点主要维护三个变量

private static class Node<E> {
    E item; //节点值
    LinkedList.Node<E> next; //后继指针 -> 指向后继节点
    LinkedList.Node<E> prev; //前驱指针 -> 指向前驱节点
	//构造方法
    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Set

Set的特点主要就是 无序的 、不可重复

实现类	底层实现	特点
`HashSet`	基于 `HashMap` 实现的，底层采用 `HashMap` 来保存元素	无序，唯一
`LinkedHashSet`	继承于 `HashSet`、又是基于 `LinkedHashMap` 来实现的	有序，唯一
`TreeSet`	红黑树(自平衡的排序二叉树)	支持自然排序和定制排序

Map

实现类	底层实现	特点
`HashMap`	JDK1.8 之前数组+链表; JDK1.8之后数组 + 链表 + 红黑树	允许有且仅有一个null键；可以有多个null值；
`LinkedHashMap`	`LinkedHashMap` 继承自 `HashMap`，并在其基础上增加了一条双向链表	有序
`HashTable`	数组+链表 (链表解决哈希冲突)	不允许有null键和null值；线程安全，全表锁
`ConcurrentHashMap`	JDK1.7 Segment 数组 + HashEntry 数组 + 链表； JDK1.8 同`HashMap` 数组+链表/红黑二叉树	线程安全，分段锁
`TreeMap`	红黑树	有序，支持自然排序和定制排序