集合

类集设置的目的

对象数组有那些问题？普通的对象数组的最大问题在于数组中的元素个数是固定的，不能动态的扩充大小，所以最早的时候可以通过链表实现一个动态对象数组。但是这样做毕竟太复杂了，所以在 Java 中为了方便用户操作各个数据结构，所以引入了类集的概念，有时候就可以把类集称为 java 对数据结构的实现。

类集中最大的几个操作接口：Collection、Map、Iterator，这三个接口为以后要使用的最重点的接口。

所有的类集操作的接口或类都在 java.util 包中。

数据结构

数据存储的常用结构有：栈、队列、数组、链表和红黑树

栈

栈：stack，又称堆栈，栈（stack）是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为先进后出的线性表。

特点：

先进后出

栈的入口、出口的都是栈的顶端位置

压栈：存元素。

弹栈：取元素。

队列

队列：queue，简称队，队列是一种特殊的线性表，是运算受到限制的一种线性表，只允许在表的一端进行插入，而在另一端进行删除元素的线性表。队尾(rear)是允许插入的一端。队头(front)是允许删除的一端。空队列是不含元素的空表。

特点：

先进先出

队列的入口、出口各占一侧

数组

数组：Array，是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。

特点：

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢

链表

链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表结构有单向链表与双向链表。

特点：

多个结点之间，通过地址进行连接。

查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素

增删元素快

红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree）。

简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。

红黑树的约束:

节点可以是红色的或者黑色的
根节点是黑色的
叶子节点(特指空节点)是黑色的
每个红色节点的子节点都是黑色的
任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:

速度特别快，趋近平衡树，查找叶子元素最少和最多次数不多于二倍

链表

链表 [Linked List]：链表是由一组不必相连（不必相连：可以连续也可以不连续）的内存结构（节点），按特定的顺序链接在一起的抽象数据类型。

链表常用的有 3 类：单链表、双向链表、循环链表。

数组和链表的区别和优缺点：

数组是一种连续存储线性结构，元素类型相同，大小相等

数组的优点：

存取速度快

数组的缺点：

事先必须知道数组的长度

插入删除元素很慢

空间通常是有限制的

需要大块连续的内存块

插入删除元素的效率很低

链表是离散存储线性结构

n 个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

链表优点：

空间没有限制

插入删除元素很快

链表缺点：

存取速度很慢

单链表

单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构(链尾除外），内存结构由数据域和 Next 指针域组成。

解析：

Data 数据 + Next 指针，组成一个单链表的内存结构；

第一个内存结构称为链头，最后一个内存结构称为链尾；

链尾的 Next 指针设置为 NULL [指向空]；

单链表的遍历方向单一（只能从链头一直遍历到链尾）

双向链表

双向链表 [Double Linked List]：由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构(链头没有前驱，链尾没有后继），内存结构由数据域、Prev 指针域和 Next 指针域组成。

解析：

Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构；

第一个内存结构称为链头，最后一个内存结构称为链尾；

链头的 Prev 指针设置为 NULL，链尾的 Next 指针设置为 NULL；

Prev 指向的内存结构称为前驱， Next 指向的内存结构称为后继；

双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定

义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向；

循环链表

单向循环链表 [Circular Linked List] : 由各个内存结构通过一个指针 Next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成。

双向循环链表 [Double Circular Linked List] : 由各个内存结构通过指针 Next 和指针Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、Prev 指针域和 Next 指针域组成。

解析：

循环链表分为单向、双向两种；

单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；

双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环；

循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；

二叉树

二叉树是树的一种，每个节点最多可具有两个子树，即结点的度最大为 2（结点度：结点拥有的子树数）。

一棵树至少会有一个节点(根节点)，而节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向 null)

斜树

所有结点都只有左子树，或者右子树。

满二叉树

所有的分支节点都具有左右节点。

完全二叉树

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

二叉查找树(binary search tree)

定义：当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。

二叉树的一些性质

二叉树第 i 层上的结点数目最多为 2^(i-1) (i≥1)

深度为 h 的二叉树至多有 2^h-1 个结点(h≥1)

包含 n 个结点的二叉树的高度至少为 log2 (n+1)

在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1

二叉树的遍历方式

二叉树的遍历方式，一般分为先序遍历，中序遍历，后序遍历。

先序遍历

先访问根节点，然后访问左节点，最后访问右节点(根->左->右)

中序遍历

先访问左节点，然后访问根节点，最后访问右节点(左->根->右)

后序遍历

先访问左节点，然后访问右节点，最后访问根节点(左->右->根)

Collection集合

集合概述

集合：集合是java中提供的一种容器，可以用来存储多个数据。

集合和数组既然都是容器，它们有啥区别呢？

1.数组的长度是固定的。集合的长度是可变的。

2.数组中存储的是同一类型的元素，可以存储基本数据类型值。集合存储的都是对象。而且对象的类型可以不一致。在开发中一般当对象多的时候，使用集合进行存储。

集合框架

JAVASE提供了满足各种需求的API，在使用这些API前，先了解其继承与接口操作架构，才能了解何时采用哪个类，以及类之间如何彼此合作，从而达到灵活应用。

集合按照其存储结构可以分为两大类，分别是单列集合 java.util.Collection 和双列集合java.util.Map 。

Collection：单列集合类的根接口，用于存储一系列符合某种规则的元素，它有两个重要的子接口，分别是 java.util.List 和 java.util.Set 。其中， List 的特点是元素有序、元素可重复。 Set 的特点是元素无序，而且不可重复。 List 接口的主要实现类有 java.util.ArrayList 和 java.util.LinkedList ， Set 接口的主要实现类有 java.util.HashSet 和 java.util.TreeSet 。

Collection常用功能

Collection是所有单列集合的父接口，因此在Collection中定义了单列集合(List和Set)通用的一些方法，此接口定义在 java.util 包中。

这些方法可用于操作所有的单列集合。

方法如下：

public Iterator<E> iterator()  为 Iterator 接口实例化

public boolean add(E e) ： 把给定的对象添加到当前集合中 。 public void clear() :清空集合中所有的元素。

public boolean remove(E e) : 把给定的对象在当前集合中删除。

public boolean contains(E e) : 判断当前集合中是否包含给定的对象。

public boolean isEmpty() : 判断当前集合是否为空。

public int size() : 返回集合中元素的个数。

public Object[] toArray() : 把集合中的元素，存储到数组中。

List集合

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地会将实现了List 接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

子类：ArrayList（95%）、Vector（4%）、LinkedList（1%）

常用方法：

public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。

public E get(int index) :返回集合中指定位置的元素。

public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。

public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新

public int indexOf(Object o)   根据对象查找指定的位置，找不到返回-1

ArrayList

java.util.ArrayList 集合数据存储的结构是数组结构，元素增删慢，查找快。由于日常开发中使用最多的功能为查询数据、遍历数据，所以 ArrayList 是最常用的集合。

许多程序员开发时非常随意地使用ArrayList完成任何需求，并不严谨，这种用法是不提倡的。

ArrayList<Integer> data = new ArrayList<>(); //在（）内定义初始容量

Vector

Vector ：使用的是数组结构，对于增加删除慢，查找快

Vector<Integer> data = new Vector<>(); //可以自定义增长的大小

LinkedList

java.util.LinkedList 集合数据存储的结构是双向链表结构。方便元素添加、删除的集合，查找慢。

实际开发中对一个集合元素的添加与删除经常涉及到首尾操作，而LinkedList提供了大量首尾操作的方法。

这些方法我们作为了解即可：

public void addFirst(E e) :将指定元素插入此列表的开头。
public void addLast(E e) :将指定元素添加到此列表的结尾。
public E getFirst() :返回此列表的第一个元素。
public E getLast() :返回此列表的最后一个元素。
public E removeFirst() :移除并返回此列表的第一个元素。
public E removeLast() :移除并返回此列表的最后一个元素。
public E pop() :从此列表所表示的堆栈处弹出一个元素。
public void push(E e) :将元素推入此列表所表示的堆栈。
public boolean isEmpty() ：如果列表不包含元素，则返回true。

LinkedList是List的子类，List中的方法LinkedList都是可以使用，这里就不做详细介绍，我们只需要了解LinkedList的特有方法即可。在开发时，LinkedList集合也可以作为堆栈，队列的结构使用。（了解即可）

LinkedList<Integer> data = new LinkedList<>();

Vector类和ArrayList类的区别

区别点	ArrayList	Vector
时间	是新的类，是在JDK 1.2之后推出的	是旧的类是在JDK 1.0的时候就定义的
性能	性能较高，是采用了异步处理	性能较低，是采用了同步处理
输出	支持Iterator、ListIterator输出	除了支持Iterator、Listlterator输出，还支持Enumeration输出

Iterator 迭代器

Iterator 接口也是Java集合中的一员，但它与 Collection 、 Map 接口有所不同， Collection 接口与 Map 接口主要用于存储元素，而 Iterator 主要用于迭代访问（即遍历）Collection 中的元素，因此 Iterator 对象也被称为迭代器。

Iterator遍历集合的整个过程：当遍历集合时，首先通过调用data集合的iterator()方法获得迭代器对象，然后使用hashNext()方法判断集合中是否存在下一个元素，如果存在，则调用next()方法将元素取出，否则说明已到达了集合末尾，停止遍历元素。

ArrayList<Integer> data = new ArrayList<>();
Iterator<Integer> iterator = data.iterator();
while(iterator.hasNext()){//判断是否存在下一个元素
    Integer i = iterator.next();//指向下一个元素
    System.out.println(i);
}

常用方法：

public E next() :返回迭代的下一个元素。

public boolean hasNext() :如果仍有元素可以迭代，则返回 true

迭代：即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续在判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。这种取出方式专业术语称为迭代。

在进行迭代输出的时候如果要想删除当前元素，则只能使用 Iterator 接口中的 remove()方法，而不能使用集合中的 remove()方法。否则将出现未知的错误。

ForEach

增强for循环(也称for each循环)是JDK1.5以后出来的一个高级for循环，专门用来遍历数组和Collection集合的。它的内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删操作。

for(数据类型变量名: 数组或集合){}

for(int data:arr){
    system.out.println(data);
}

Set集合

Set 接口并没有对 Collection 接口进行扩充，基本上还是与 Collection 接口保持一致。与 List 接口不同的是， Set 接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

因为此接口没有 List 接口中定义的 get(int index)方法，所以无法使用循环进行输出。

获取数据的方法：

使用toArray将Set变成数组

使用Iterator迭代器

注意：如果将可变对象用作set元素，以则必须非常小心。

那么在此接口中有两个常用的子类：HashSet、TreeSet

HashSet

java.util.HashSet 是 Set 接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持。

HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于： hashCode 与 equals 方法。

散列存放：哈希表，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

HashSet存储自定义类型元素

给HashSet中存放自定义类型元素时，需要重写对象中的hashCode()和equals()方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一。

LinkedHashSet

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？在HashSet下面有一个子类 java.util.LinkedHashSet ，它是链表和哈希表组合的一个数据存储结构。

TreeSet

与 HashSet 不同的是，TreeSet 本身属于排序的子类

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable

Collections

java.utils.Collections 是集合工具类，用来对集合进行操作。部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。

public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序。

public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。

public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。

TreeSet与Comparable接口

与 HashSet 不同的是，TreeSet 本身属于排序的子类

不实现comparable接口不能比较定义的对象

public int compareTo(Person o) {
//this 与o比较
//返回的数据:负数this小/零―样大/正数this大
    return o;
}

小结：

关于 TreeSet 的排序实现，如果是集合中对象是自定义的或者说其他系统定义的类没有实现 Comparable 接口，则不能实现 TreeSet 的排序，会报类型转换（转向 Comparable 接口）错误。换句话说要添加到 TreeSet 集合中的对象的类型必须实现了 Comparable 接口。

不过 TreeSet 的集合因为借用了 Comparable 接口，同时可以去除重复值，而 HashSet 虽然是 Set 接口子类，但是对于没有复写 Object 的 equals 和 hashCode 方法的对象，加入了 HashSet 集合中也是不能去掉重复值的。

Comparator比较器

public static <T> void sort(List<T> list，Comparator<? super T> ) 方法灵活的完成，这个里面就涉及到了Comparator这个接口，位于位于java.util包下，排序是comparator能实现的功能之一，该接口代表一个比较器，比较器具有可比性！顾名思义就是做排序的，通俗地讲需要比较两个对象谁排在前谁排在后，那么比较的方法就是：

public int compare(String o1, String o2) ：比较其两个参数的顺序。
两个对象比较的结果有三种：大于，等于，小于。
如果要按照升序排序，
则o1 小于o2，返回（负数），相等返回0，o1大于o2返回（正数）
如果要按照降序排序
则o1 小于o2，返回（正数），相等返回0，o1大于o2返回（负数）

ArrayList<Student> list = new ArrayList<>();
Collections.sort(list,new Comparator<Student>(){//使用Comparator排序
            public int compare(Student student1, Student student2){
                if (student1.score > student2.score){
                    return 1;
                }else if (student1.score == student2.score){
                    return 0;
                }else {
                    return -1;
                }
            }
        });

简述Comparable和Comparator两个接口的区别。

Comparable：强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo方法被称为它的自然比较方法。只能在类中实现compareTo()一次，不能经常修改类的代码实现自己想要的排序。实现此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序，对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

Comparator强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构（如有序set或有序映射）的顺序，或者为那些没有自然顺序的对象collection提供排序。

集合输出

只要是碰到了集合，则输出的时候想都不想就使用 Iterator 进行输出。

Map 映射

Map 接口里面的所有内容都按照 key->value 的形式保存，也称为二元偶对象

Map集合存储的是一个个键值对数据

Map集合中的键（Key）不可重复

public interface Map<K,V>

方法：

void clear()   清空 Map 集合中的内容

boolean containsKey(Object key)   判断集合中是否存在指定的 key 

boolean containsValue(Object value)   判断集合中是否存在指定的 value

Set<Map.Entry<K,V>> entrySet()   将 Map 接口变为 Set 集合 *

V get(Object key)   根据 key 找到其对应的 value *

boolean isEmpty()   判断是否为空

Set<K> keySet()   将全部的 key 变为 Set 集合 *

Collection<V> values()   将全部的 value 变为 Collection 集合 *

V put(K key,V value)    向集合中增加内容 *

V remove(Object key)    根据 key 删除内容 *

HashMap

对象：数组+链表

HashMap 是 Map 的子类，此类的定义如下：

public class HashMap<K,V> extends AbstractMap<K,V> 
implements Map<K,V>, Cloneable, Serializable
    
    
HashMap<数据类型1,数据类型2> 表名= new HashMap<>();

哈希桶中的数据量大于8时，从链表转换为红黑二叉树. 当哈希桶中的数据量减少到6时,从红黑二叉树转换为链表.

初始哈希桶的数量 16

散列因子 0.75

Hashtable

Hashtable 是一个最早的 key*value 的操作类，本身是在 JDK 1.0 的时候推出的。其基本操作与 HashMap 是类似的。

操作的时候，可以发现与 HashMap 基本上没有什么区别，而且本身都是以 Map 为操作标准的，所以操作的结果形式都一样。但是 Hashtable 中是不能向集合中插入 null 值的。

HashMap 与 Hashtable 的区别

区别点	HashMap	Hastable
推出时间	JDK 1.2之后推出的，新的操作类	JDK 1.0时推出的，旧的操作类
性能	异步处理，性能较高	同步处理，性能较低
null	允许设置为null	不允许设置，否则将出现空指向异常