Java集合类List、Set如何使用详解

Java集合框架URL图

List 列表

接口List 下的方法

ArrayList

ArrayList 是基于索引的数据接口， 它的底层是数组。 它可以以 O(1)时间复杂度对元素进行随机访问

ArrayList的几个重要属性

1、默认的容量，如果使用无参的构造器，则生成的数组的长度默认为10

private static final int DEFAULT_CAPACITY = 10; 

2、ArrayList 底层是用数组实现的 提供一个空的数组

private static final Object[] EMPTY_ELEMENTDATA = {}; 

3、size 表示的是底层数组内存储的元素的个数，而不是底层数组的长度，所以可以认为ArrayList是可变长的。

ArrayList的扩容机制、

1、首先，调用ArrayList的add方法时，先判断，添加元素后的长度是否超过了ElementData数组的长度

private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; } 

2、如果需要扩容 ，则调用grow 方法后，再进行赋值。

private Object[] grow() { return grow(size + 1); } 

接下来看一下啊真正实现扩容的方法，可以看到grow方法内调用ArraysSupport.newLength方法进行新长度的计算：newCapacity=oldCapacity+ oldCapacity >> 1 即新容量为旧容量的1.5倍。
则ArrayList新建一个数组，把旧的elementdata内的数组拷贝到新的数组中，完成扩容

int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); 

private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } } 

LinkedList

LinkedList 是以元素列表的形式存储它的数据， 每一个元素都和它的
前一个和后一个元素链接在一起， 在这种情况下， 查找某个元素的时间复杂度是 O(n)。

LinkedList的几个重要属性

1、size 表示的是链表内的数据的个数，
2、first 是头节点的指针，l
3、ast 是尾节点的指针。

transient int size = 0; /**
     * Pointer to first node.
     */ transient Node<E> first; /**
     * Pointer to last node.
     */ transient Node<E> last; 

构造器

除了无参构造器外，还提供一个可以直接传入其他集合类的对象，将对象转化为链表。

public LinkedList(Collection<? extends E> c) { this(); addAll(c); } 

LinkedList 的内部实现

LinkedList 是通过一个静态内部类Node来实现链表的，Node内主要有3个属性，item表示数据，prev 表示前一个节点的指针，next表示后一个节点的指针。

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 

针对List列表集合类，jdk还提供了一个特殊的迭代器ListIterator

提供的方法如下：

public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } 

lIterator 和 ListIterator 的区别如下：
Iterator 可用来遍历 Set 和 List 集合， 但是 ListIterator 只能用来遍历 List。Iterator 对集合只能是前向遍历， ListIterator 既可以前向也可以后向。
ListIterator 实现了 Iterator 接口， 并包含其他的功能， 比如： 增加元素， 替换元素， 获取前一个和后一个元素的索引， 等等。
Iterator 的安全失败是基于对底层集合做拷贝， 因此， 它不受源集合上修
改 的 影 响 。 java.util 包 下 面 的 所 有 的 集 合 类 都 是 快 速 失 败 的 ， 而java.util.concurrent 包下面的所有的类都是安全失败的。 快速失败的迭代器会抛出 ConcurrentModificationException 异常， 而安全失败的迭代器永远不会抛出这样的异常。

ArrayList， LinkedList 和 Vector 的区别

1、Vector 和ArrayList原理相似，但是线程安全。
2、底层实现 ArrayList的底层是数组，LinkedList的底层是链表，用内部类Node实现。
3、前者是动态数组，空参构造的默认容量为10，每次扩容为旧容量的1.5倍，而LinkedList不需要扩容。
4、应用场景,ArrayList基于数组，所以查询较快，而增删数据由于数组的拷贝而教满，LinkedList则插入、删除较快，查询较慢。

Set类

特点：无序 无下标 不能重复
Set接口提供的方法：

HashSet

底层实现

HashSet内部实现为一个HashMap，所以和HashMap类似。将数据保存在HashMap的key中，value处则为null。可以在构造器中传入其他集合类的对象，转换为HashSet对象。
HashSet提供了一个dummy对象PRESENT，所有HashSet的方法的调用都是间接的通过map对<key,PRESENT>键值对的操作。

// Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); private transient HashMap<E,Object> map; public HashSet() { map = new HashMap<>(); } public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } 

HashSet的方法都是间接调用底层的HashMap的方法实现的，具体内容可以参考HashMap的笔记。

• HashMap

TreeSet

底层实现

底层是基于NavigableMap ,可以实现数据的排序。可以自定义排序方式。

 private transient NavigableMap<E,Object> m; public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } public TreeSet(Collection<? extends E> c) { this(); addAll(c); } 

HashMap 和 HashSet的区别

本文地址：https://blog.csdn.net/cheendf/article/details/108021069