Java——容器(单例集合)(上)

一 容器介绍

• 容器，是用来容纳物体、管理物体。生活中,我们会用到各种各样的容器。如锅碗瓢盆、箱子和包等

• 程序中的“容器”也有类似的功能，用来容纳和管理数据。比如，如下新闻网站的新闻列表、教育网站的课程列表就是用“容器”来管理

• 视频课程信息也是使用“容器”来管理

• 计算机当中能够存储数据的位置有两个——>一个是磁盘，一个是内存

  • 磁盘是通过文件的形式存储数据的——>(永久存储，不会受到计算机的关闭而影响数据的)
  • 内存是临时存储——>关闭计算机后内存中是没有数据的
  • 容器存储的数据在内存当中

开发和学习中需要时刻和数据打交道，如何组织这些数据是我们编程中重要的内容。 我们一般通过“容器”来容纳和管理数据。事实上，我们前面所学的数组就是一种容器，可以在其中放置对象或基本类型数据。

数组的优势：是一种简单的线性序列，可以快速地访问数组元素，效率高。如果从查询效率和类型检查的角度讲，数组是最好的。

数组的劣势：不灵活。容量需要事先定义好，不能随着需求的变化而扩容。比如：我们在一个用户管理系统中，要把今天注册的所有用户取出来，那么这样的用户有多少个？我们在写程序时是无法确定的。因此，在这里就不能使用数组。

基于数组并不能满足我们对于“管理和组织数据的需求”，所以我们需要一种更强大、更灵活、容量随时可扩的容器来装载我们的对象。 这就是我们今天要学习的容器，也叫集合(Collection)。

二 容器结构

(三大接口)

1 结构图

​ List和Set都是单例接口，Map是双例接口(k,v)

2 单例集合

​ List——>相当于动态数组，Set——>相当于数学里的集合

3 双例集合

​ Map——>相当于数学里的函数，(mapping——>映射)

(单例集合)

三 (*)Collection接口

(12个方法)

(定义了单例集合的基本行为)

(接口中的方法很重要，注意返回值，和返回值类型)

Collection 表示一组对象，它是集中、收集的意思。Collection接口的两个子接口是List、Set接口。

Collection接口中定义的方法

方法	说明
boolean add(Object element)	增加元素到容器中
boolean remove(Object element)	从容器中移除元素
boolean contains(Object element)	容器中是否包含该元素
int size()	容器中元素的数量
boolean isEmpty()	容器是否为空
void clear()	清空容器中所有元素
Iterator iterator()	获得迭代器，用于遍历所有元素
boolean containsAll(Collection c)	本容器是否包含c容器中的所有元素
boolean addAll(Collection c)	将容器c中所有元素增加到本容器
boolean removeAll(Collection c)	移除本容器和容器c中都包含的元素
boolean retainAll(Collection c)	取本容器和容器c中都包含的元素，移除非交集元素
Object[] toArray()	转化成Object数组

由于List、Set是Collection的子接口，意味着所有List、Set的实现类都有上面的方法。

JDK8之后，Collection接口新增的方法（将在JDK新特性和函数式编程中介绍）：

新增方法	说明
removeIf	作用是删除容器中所有满足filter指定条件的元素
stream parallelStream	stream和parallelStream 分别返回该容器的Stream视图表示，不同之处在于parallelStream()返回并行的Stream，Stream是Java函数式编程的核心类。
spliterator	可分割的迭代器，不同以往的iterator需要顺序迭代，Spliterator可以分割为若干个小的迭代器进行并行操作，可以实现多线程操作提高效率

四 (*)List接口

(6个方法)

(进一步细化了单例集合的存储特征)

(有序，可重复)

List接口特点

List是有序、可重复的容器。

有序：有序(元素存入集合的顺序和取出的顺序一致)。List中每个元素都有索引标记。可以根据元素的索引标记（在List中的位置）访问元素，从而精确控制这些元素。

可重复：List允许加入重复的元素。更确切地讲，List通常允许满足 e1.equals(e2) 的元素重复加入容器。

List接口中的常用方法

除了Collection接口中的方法，List多了一些跟顺序(索引)有关的方法，参见下表：

方法	说明
void add (int index, Object element)	在指定位置插入元素，以前元素全部后移一位
Object set (int index,Object element)	修改指定位置的元素
Object get (int index)	返回指定位置的元素
Object remove (int index)	删除指定位置的元素，后面元素全部前移一位
int indexOf (Object o)	返回第一个匹配元素的索引，如果没有该元素，返回-1.
int lastIndexOf (Object o)	返回最后一个匹配元素的索引，如果没有该元素，返回-1

五(ArrayList)

1 ArrayList容器的基本操作

(Collection里面的方法——>添加，删除，转数组，长度，判空，清除)

(是List接口的实现类。是List存储特征的具体实现)

(底层是用数组实现的——>查询效率高，增删效率低，线程不安全)

(数组是有索引的查询快，但是插入和删除都要移动后面所有的数据慢)

(建议如果没有用到Arraylist里面的方法，最好用List接口类型定义引用)

实例化

​ 三种定义方式都可以

• 但是ArrayList继承了List接口和Collection接口，可以用包括自己的所有的方法（缺点就是以后换容器时候代码会作废）
• 用List虽然方法少，但是以后换容器的时候不用担心
• 用Collection定义方法太少，一般不会用

建议如果没有用到Arraylist里面的方法，最好用List接口类型定义引用

示例

public class ArrayListTest {public static void main(String[] args) {//实例化ArrayList容器List<String> list = new ArrayList<>();//添加元素boolean flag1 = list.add("xiaojia");boolean flag2 = list.add("xiaoliu");boolean flag3 = list.add("jia");boolean flag4 = list.add("jia");System.out.println(flag1+"\t"+flag2+"\t"+flag3+"\t"+flag4);//将ArrayList转换为数组——>Collextion里面的方法，和数组里面的方法Object[] objects = list.toArray();System.out.println(Arrays.toString(objects));//删除元素——>可以选择删除数据，或者位置boolean flag4 = list.remove("oldlu");System.out.println(flag4);//获取容器中元素的个数int size = list.size();System.out.println(size);//判断容器是否为空boolean empty = list.isEmpty();System.out.println(empty);//容器中是否包含指定的元素boolean value = list.contains("itbz");System.out.println(value);//清空容器list.clear();Object[] objects1 = list.toArray();System.out.println(Arrays.toString(objects1));}
}

2 ArrayList容器的索引操作

(6个操作)

(指定位置添加元素，获取元素，元素替换，删除指定位置，查找元素在容器(第一次)(最后一次)出现位置)

public class ArrayListTest2 {public static void main(String[] args) {//实例化容器List<String> list = new ArrayList<>();//添加元素list.add("jia");list.add("jiajia");//向指定位置添加元素list.add(0,"xiao");System.out.println("获取元素");String value1 = list.get(0);System.out.println(value1);System.out.println("获取所有元素方式一");//使用普通for循环for(int i=0;i<list.size();i++){System.out.println(list.get(i));}System.out.println("获取所有元素方式二");//使用Foreach循环for(String str:list){System.out.println(str);}System.out.println("元素替换");list.set(1,"kevin");for(String str:list){System.out.println(str);}System.out.println("根据索引位置删除元素);String value2 = list.remove(1);System.out.println(value2);System.out.println("----------------");for(String str:list){System.out.println(str);}System.out.println("查找元素第一次出现的位置");int value3 = list.indexOf("jjj");System.out.println(value3);System.out.println("查找元素最后一次出现的位置");list.add("jjj");for(String str:list){System.out.println(str);}int value4 = list.lastIndexOf("jjj");System.out.println(value4);}
}

3 ArrayList并集、交集、差集

(Collection里面的3个方法)

(addAll，retainAll，removeAll)

并集

 //并集操作：将另一个容器中的元素添加到当前容器中List<String> a = new ArrayList<>();a.add("a");a.add("b");a.add("c");List<String> b = new ArrayList<>();b.add("a");b.add("b");b.add("c");//a并集ba.addAll(b);for(String str :a){System.out.println(str);}

交集

 //交集操作：保留相同的，删除不同的List<String> a1 = new ArrayList<>();a1.add("a");a1.add("b");a1.add("c");List<String> b1 = new ArrayList<>();b1.add("a");b1.add("d");b1.add("e");//交集操作a1.retainAll(b1);for(String str :a1){System.out.println(str);}

差集

//差集操作：保留不同的，删除相同的List<String> a2 = new ArrayList<>();a2.add("a");a2.add("b");a2.add("c");List<String> b2= new ArrayList<>();b2.add("b");b2.add("c");b2.add("d");a2.removeAll(b2);for(String str :a2){System.out.println(str);}

4 ArrayList源码分析

数组的初始化和扩容——>最开始数组长度为10，然后以1.5倍扩容，jdk1.8之后在操作数组时才初始化，节省内存

1

2

3

4

六 (Vector)

1 Vector容器的使用

(方法都加了同步检查——>“线程安全,效率低”)

(方法就增加了synchronized同步标记——>为了多线程的时候线程安全)

(单线程——>串型，多线程——>并型)

(使用容器的时候如果对线程安全有要求，大部分都使用ArrayList)

Vector(向量)的使用

Vector的使用与ArrayList是相同的，因为他们都实现了List接口，对List接口中的抽象方法做了具体实现。

public class VectorTest {public static void main(String[] args) {//实例化VectorList<String> v = new Vector<>();v.add("a");v.add("b");v.add("a");for(int i=0;i<v.size();i++){System.out.println(v.get(i));}System.out.println("----------------------");for(String str:v){System.out.println(str);}}
}

2 Vector源码分析

(和ArrayList底层都是数组，区别就是线程安全和效率)

(数组初始化方式，ArrayList1.8之后是延迟初始化(调用时初始化)，在Vector中是立即初始化，长度也是10)

(ArrayList数组扩容1.5倍，Vector2倍扩容)

成员变量

/*** The array buffer into which the components of the vector are* stored. The capacity of the vector is the length of this array buffer,* and is at least large enough to contain all the vector's elements.** <p>Any array elements following the last element in the Vector are null.** @serial*/
protected Object[] elementData;/*** The number of valid components in this {@code Vector} object.* Components {@code elementData[0]} through* {@code elementData[elementCount-1]} are the actual items.** @serial*/protected int elementCount;/*** The amount by which the capacity of the vector is automatically* incremented when its size becomes greater than its capacity.  If* the capacity increment is less than or equal to zero, the capacity* of the vector is doubled each time it needs to grow.** @serial*/protected int capacityIncrement;

构造方法

public Vector() {this(10);
}

添加元素

/*** Appends the specified element to the end of this Vector.** @param e element to be appended to this Vector* @return {@code true} (as specified by {@link Collection#add})* @since 1.2*/
public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;
}

数组扩容

/*** This implements the unsynchronized semantics of ensureCapacity.* Synchronized methods in this class can internally call this* method for ensuring capacity without incurring the cost of an* extra synchronization.** @see #ensureCapacity(int)*/
private void ensureCapacityHelper(int minCapacity) {// overflow-conscious code
//判断是否需要扩容，数组中的元素个数-数组长度，如果大于0表明需要扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;
//扩容2倍int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);
}

七 (LinkedList)

1 LinkedList容器介绍

(底层用双向链表实现的存储——>查询效率低，增删效率高，线程不安全)

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

每个节点都应该有3部分内容：

class Node<E> {Node<E> previous;   //前一个节点E element;     //本节点保存的数据Node<E> next;        //后一个节点
}

List实现类的选用规则

如何选用ArrayList、LinkedList、Vector?

1. 需要线程安全时，用Vector。
2. 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）
3. 不存在线程安全问题时，增加或删除元素较多用LinkedList

2 LinkedList容器的使用

(LinkedList实现了List接口，所以LinkedList是具备List的存储特征的(有序，元素有重复))

(自己独有的8个方法)

list标准

public class LinkedListTest {public static void main(String[] args) {//实例化LinkedList容器List<String> list = new LinkedList<>();//添加元素boolean a = list.add("a");boolean b = list.add("b");boolean c = list.add("c");list.add(3,"a");System.out.println(a+"\t"+b+"\t"+c);for(int i=0;i<list.size();i++){System.out.println(list.get(i));}}
}

非list标准——>自己独有的方法

方法	说明
void addFirst(E e)	将指定元素插入到开头
void addLast(E e)	将指定元素插入到结尾
getFirst()	返回此链表的第一个元素
getLast()	返回此链表的最后一个元素
removeFirst()	移除此链表中的第一个元素，并返回这个元素
removeLast()	移除此链表中的最后一个元素，并返回这个元素
E pop()	从此链表所表示的堆栈处弹出一个元素,等效于removeFirst
void push(E e)	将元素推入此链表所表示的堆栈 这个等效于addFisrt(E e)

public class LinkedListTest2 {public static void main(String[] args) {System.out.println("-------LinkedList-------------");//将指定元素插入到链表开头LinkedList<String> linkedList1 = new LinkedList<>();linkedList1.addFirst("a");linkedList1.addFirst("b");linkedList1.addFirst("c");for (String str:linkedList1){System.out.println(str);}System.out.println("----------------------");//将指定元素插入到链表结尾LinkedList<String> linkedList = new LinkedList<>();linkedList.addLast("a");linkedList.addLast("b");linkedList.addLast("c");for (String str:linkedList){System.out.println(str);}System.out.println("---------------------------");//返回此链表的第一个元素System.out.println(linkedList.getFirst());//返回此链表的最后一个元素System.out.println(linkedList.getLast());System.out.println("-----------------------");//移除此链表中的第一个元素，并返回这个元素linkedList.removeFirst();//移除此链表中的最后一个元素，并返回这个元素linkedList.removeLast();for (String str:linkedList){System.out.println(str);}System.out.println("-----------------------");linkedList.addLast("c");//从此链表所表示的堆栈处弹出一个元素,等效于removeFirstlinkedList.pop();for (String str:linkedList){System.out.println(str);}System.out.println("-------------------");//将元素推入此链表所表示的堆栈  这个等效于addFisrt(E e)linkedList.push("h");for (String str:linkedList){System.out.println(str);}}
}

3 LinkedList源码分析

1 添加元素

节点类

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;}
}

成员变量

transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*       (first.prev == null && first.item != null)*/
transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*       (last.next == null && last.item != null)*/
transient Node<E> last;

添加元素

/*** Appends the specified element to the end of this list.** <p>This method is equivalent to {@link #addLast}.** @param e element to be appended to this list* @return {@code true} (as specified by {@link Collection#add})*/
public boolean add(E e) {linkLast(e);return true;
}/*** Links e as last element.*/
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;elsel.next = newNode;size++;modCount++;
}//创建新节点，头尾指针指向

2 头尾添加元素

addFirst

/*** Inserts the specified element at the beginning of this list.** @param e the element to add*/
public void addFirst(E e) {linkFirst(e);
}/*** Links e as first element.*/
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;elsef.prev = newNode;size++;modCount++;
}

addLast

/*** Appends the specified element to the end of this list.** <p>This method is equivalent to {@link #add}.** @param e the element to add*/
public void addLast(E e) {linkLast(e);
}/*** Links e as last element.*/
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;elsel.next = newNode;size++;modCount++;
}

3 获取元素——>返回的不是对象是元素

/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/
public E get(int index) {checkElementIndex(index);return node(index).item;
}

private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/*** Tells if the argument is the index of an existing element.*/
private boolean isElementIndex(int index) {return index >= 0 && index < size;
}

/*** Returns the (non-null) Node at the specified element index.*/
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;}
}