一、集合定义及特性
1.1集合和数组区别
- 长度区别：数组长度固定，集合长度不固定
- 元素区别：数组可以存储基本类型和引用类型，集合只能存储引用类型
- 内容区别：集合可存储不同类型元素，数组存储只可单一类型元素
1.2结合特性
1.Collection – 对象之间没有指定的顺序，允许重复元素。
2.Set – 对象之间没有指定的顺序，不允许重复元素
\3. List– 对象之间有指定的顺序，允许重复元素,并引入位置下标。
4.Map – 接口用于保存关键字（Key）和数值（Value）的集合，集合中的每个对象加入时都提供数值和关键字。Map 接口既不继承 Set 也不继承 Collection。
List、Set、Map共同的实现基础是Object数组
1.4位置
java.util.*;二、集合类别
2.1Collection体系
2.1.1Collection父接口
特点：代表一组任意类型的对象，无序、无下标、不能重复。
2.1.2Collection常用方法
| 方法 | 介绍 |
|---|---|
| add(E e) | 添加元素 |
| addAll(Collection<? extends E> c) | 将指定 collection 中的所有元素都添加到此 collection 中（可选操作）。 |
| remove() | 从此 collection 中移除指定元素的单个实例，如果存在的话（可选操作）。 |
| removeAll() | 移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。 |
| clear() | 移除此 collection 中的所有元素（可选操作）。 |
| contains(Object o) | 如果此 collection 包含指定的元素，则返回 true。 |
| containsAll(Collection<?> c) | 如果此 collection 包含指定 collection 中的所有元素，则返回 true。 |
| equals(Object o) | 比较此 collection 与指定对象是否相等。 |
| isEmpty() | 如果此 collection 不包含元素，则返回 true。 |
| size() | 返回此 collection 中的元素数。 |
| hashCode() | 返回此 collection 的哈希码值。 |
| toArray() | 返回包含此 collection 中所有元素的数组。 |
| toArray(T[] a) | 返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。 |
| retainAll(Collection<?> c) | 移除此 collection 中那些也包含在指定 collection 中的所有元素（并集）。 |
方法示例
import java.util.*;
public class CollectionToArray {
public static void main(String[] args) {
Collection collection1=new ArrayList();//创建一个集合对象
collection1.add("000");//添加对象到Collection集合中
collection1.add("111");
collection1.add("222");
System.out.println("集合collection1的大小："+collection1.size());
System.out.println("集合collection1的内容："+collection1);
collection1.remove("000");//从集合collection1中移除掉 "000" 这个对象
System.out.println("集合collection1移除 000 后的内容："+collection1);
System.out.println("集合collection1中是否包含000 ："+collection1.contains("000"));
System.out.println("集合collection1中是否包含111 ："+collection1.contains("111"));
Collection collection2=new ArrayList();
collection2.addAll(collection1);//将collection1 集合中的元素全部都加到collection2中
System.out.println("集合collection2的内容："+collection2);
collection2.clear();//清空集合 collection1 中的元素
System.out.println("集合collection2是否为空 ："+collection2.isEmpty());
//将集合collection1转化为数组
Object s[]= collection1.toArray();
for(int i=0;i<s.length;i++){
System.out.println(s[i]);
}
}
}
运行结果为：
集合collection1的大小：3
集合collection1的内容：[000, 111, 222]
集合collection1移除 000 后的内容：[111, 222]
集合collection1中是否包含000 ：false
集合collection1中是否包含111 ：true
集合collection2的内容：[111, 222]
集合collection2是否为空 ：true
111
2222.2List集合
前面我们讲述的Collection接口实际上并没有直接的实现类。而List是容器的一种，表示列表的意思。当我们不知道存储的数据有多少的情况，我们就可以使用List 来完成存储数据的工作。例如前面提到的一种场景。我们想要在保存一个应用系统当前的在线用户的信息。我们就可以使用一个List来存储。因为List的最大的特点就是能够自动的根据插入的数据量来动态改变容器的大小。下面我们先看看List接口的一些常用方法。
2.2.1List常用方法（除Collection接口外）
| 方法 | 介绍 |
|---|---|
| void add(int index, Object element) | 添加对象element到位置index上 |
| boolean addAll(int index, Collection collection) | 在index位置后添加容器collection中所有的元素 |
| Object remove(int index) | 删除index位置上的元素 |
| Object get(int index) | 取出下标为index的位置的元素 |
| int indexOf(Object element) | 查找对象element 在List中第一次出现的位置 |
| int lastIndexOf(Object element) | 查找对象element 在List中最后出现的位置 |
| Object set(int index, Object element) | 将index位置上的对象替换为element 并返回老的元素 |
| List subList(int fromIndex, int toIndex) | 返回一个子列表List ,元素存放为从 fromIndex 到toIndex之前的一个元素。 |
2.2.2ListIterator(列表迭代器)
- 通过List集合的listIterator()方法得到的,所以说它是List集合特有的迭代器（逆序或者正序）
- 用于允许程序员沿任意方向遍历列表的列表迭代器,在迭代期间修改列表,并获取列表中迭代器的当前位置
ListIterator it2 = list.listIterator(list.size());//下标
while(it2.hasPrevious()){
System.out.println("previous Index="+it2.previousIndex()+",Object="+it2.previous());
}加一个元素会导致新元素立刻被添加到隐式光标的前面。因此，添加元素后调用 previous() 会返回新元素，而调用 next() 则不起作用，返回添加操作之前的下一个元素。
2.2.3List子接口
| 实现 | 简述 | 操作特性 | 成员要求 |
|---|---|---|---|
| ArrayList | 提供基于索引的对成员的随机访问 | 提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好 | 成员可为任意Object子类的对象 |
| LinkedList | 提供基于索引的对成员的随机访问 | 对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差 | 成员可为任意Object子类的对象 |
2.3Array
2.3.1构造方法
ArrayList() 构造一个初始容量为 10 的空列表。 |
|---|
ArrayList(Collection[E](https://jdk6.net/util/ArrayList.html)> c)` 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。 |
ArrayList(int initialCapacity) 构造一个具有指定初始容量的空列表。 |
2.3.2常用方法（已知除外）
| 方法 | 介绍 |
|---|---|
| clone() | 返回此 ArrayList 实例的浅表副本 |
| ensureCapacity(int minCapacity) | 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。 |
| ensureCapacity(int minCapacity) | 删除index位置上的元素 |
| protected void removeRange(int fromIndex, int toIndex) | 移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。 |
| trimToSize() | 将此 ArrayList 实例的容量调整为列表的当前大小。 |
2.3.3ArrayList扩容机制（原理）
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。（不是原数组，而是新数组然后给予数组对象地址）。
默认情况下，新的容量会是原容量的1.5倍。 新容量=旧容量右移一位（相当于除于2）在加上旧容量
ArrayList 的底层是用动态数组来实现的。我们初始化一个ArrayList 集合还没有添加元素时，其实它是个空数组，只有当我们添加第一个元素时，内部会调用扩容方法并返回最小容量10，也就是说ArrayList 初始化容量为10。 当前数组长度小于最小容量的长度时（前期容量是10，当添加第11个元素时就就扩容），便开始可以扩容了，ArrayList 扩容的真正计算是在一个grow()里面，新数组大小是旧数组的1.5倍，如果扩容后的新数组大小还是小于最小容量，那新数组的大小就是最小容量的大小，后面会调用一个Arrays.copyof方法，这个方法是真正实现扩容的步骤。
2.4LinkedList
LinkedList类是一个继承于AbstractSequentialList的双向循环链表，它是非同步的，也是非线程安全的。
LinkedList实现了List接口，能对它进行队列操作。
LinkedList实现了Deque接口，能当作双端队列操作LinkedList实现了CloneClass接口，能进行克隆操作。
LinkedList实现了SerialiableClass接口，能进行序列化操作。
LinkedList 是非同步的。
2.4.1常用方法（已知除外）
| 方法 | 介绍 |
|---|---|
| addFirst(E e) | 将指定元素插入此列表的开头。 |
| addLast(E e) | 将指定元素添加到此列表的结尾。 |
| clone() | 返回此 LinkedList 的浅表副本。 |
| Iterator |
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 |
| E element() | 获取但不移除此列表的头（第一个元素）。 |
| getFirst() | 返回此列表的第一个元素。 |
| getLast() | 返回此列表的最后一个元素。 |
| boolean offer(E e) | 将指定元素添加到此列表的末尾（最后一个元素）。 |
| boolean offerFirst(E e) | 在此列表的开头插入指定的元素。 |
| boolean offerLast(E e) | 在此列表末尾插入指定的元素。 |
| E peek() | 获取但不移除此列表的头（第一个元素） |
| E peekFirst() | 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 |
| E peekLast() | 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 |
| E poll() | 获取并移除此列表的头（第一个元素） |
| E pollFirst() | 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 |
| E pollLast() | 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 |
| E pop() | 从此列表所表示的堆栈处弹出一个元素。 |
| void push(E e) | 将元素推入此列表所表示的堆栈。 |
| E removeFirst() | 移除并返回此列表的第一个元素。 |
| boolean removeFirstOccurrence(Object o) | 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时） |
| E removeLast() | 移除并返回此列表的最后一个元素。 |
| boolean removeLastOccurrence(Object o) | 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时） |
3.1Set接口
特点：无序、无下标、元素不可重复
方法：全部继承自Collection中的方法
增、删、遍历、判断与collection一致
3.1.1HashSet（重点）
存储结构：哈希表（数组+链表+红黑树）
存储过程（重复依据）
- 根据hashCode计算保存的位置，如果位置为空，直接保存，若不为空，进行第二步
- 再执行equals方法，如果equals为true，则认为是重复，否则形成链表
特点
- 不允许存储重复的元素
- 没有索引，没有带索引的方法，也不能使用普通的for循环遍历
- 是一个无序的集合，存储元素和取出元素的顺序有可能不一致
- 底层是一个哈希表结构，存储时依靠哈希值进行存储(查询的速度非常快)
- 基于HashCode计算元素存放位置
- 利用31这个质数，减少散列冲突
- 31提高执行效率
31 * i = (i << 5) - i转为移位操作
- 31提高执行效率
- 当存入元素的哈希码相同时，会调用equals进行确认，如果结果为true，则拒绝后者存入
- 利用31这个质数，减少散列冲突
HashSet使用的是相当复杂的方式来存储元素的，使用HashSet能够最快的获取集合中的元素，效率非常高（以空间换时间）。会根据hashcode和equals来庞端是否是同一个对象，如果hashcode一样，并且equals返回true，则是同一个对象，不能重复存放。
重写了hashCode()和equals()方法来区分同意对象后，就不能存放同以对象了
3.1.2TreeSet
特点
- 基于排列顺序实现，无序不可重复，但是可以按照元素的大小顺序自动排序
- 实现SortedSet接口，对集合元素自动排序
- 元素对象的类型必须实现Comparable接口，指定排序规则
- 通过CompareTo方法确定是否为重复元素
存储结构：红黑树
3.1.3常用方法（已知除外）
|
方法及介绍 |
|---|---|
E |
ceiling(Ee) 返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。 |
Object |
clone() 返回 TreeSet 实例的浅表副本。 |
Comparator[E](https://jdk6.net/util/TreeSet.html)>` |
comparator() 返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。 |
Iterator<E> |
descendingIterator() 返回在此 set 元素上按降序进行迭代的迭代器。 |
NavigableSet<E> |
descendingSet() 返回此 set 中所包含元素的逆序视图。 |
E |
first() 返回此 set 中当前第一个（最低）元素。 |
E |
floor(Ee) 返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。 |
SortedSet<E> |
headSet(EtoElement) 返回此 set 的部分视图，其元素严格小于 toElement。 |
NavigableSet<E> |
[headSet](https://jdk6.net/util/TreeSet.html#headSet(E, boolean))(EtoElement, boolean inclusive) 返回此 set 的部分视图，其元素小于（或等于，如果 inclusive 为 true）toElement。 |
E |
higher(Ee) 返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。 |
E |
last() 返回此 set 中当前最后一个（最高）元素。 |
E |
lower(Ee) 返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。 |
E |
pollFirst() 获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。 |
E |
pollLast() 获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。 |
NavigableSet<E> |
[subSet](https://jdk6.net/util/TreeSet.html#subSet(E, boolean, E, boolean))(EfromElement, boolean fromInclusive,EtoElement, boolean toInclusive) 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。 |
SortedSet<E> |
[subSet](https://jdk6.net/util/TreeSet.html#subSet(E, E))(EfromElement,EtoElement) 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。 |
SortedSet<E> |
tailSet(EfromElement) 返回此 set 的部分视图，其元素大于等于 fromElement。 |
NavigableSet<E> |
[tailSet](https://jdk6.net/util/TreeSet.html#tailSet(E, boolean))(EfromElement, boolean inclusive) 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。 |
3.1.4TreeSet底层原理
TreeSet/TreeMap底层都采用的是自平衡二叉树(TreeSet底层是TreeMap): 遵循左小右大的原则存放，存放的过程也就是排序的过程
遍历二叉树的三种方式: (note:左永远在右的左边)
前序遍历: 根左右
中序遍历:左根右 (满足自平衡二叉树的存放方式，中序遍历取出数据的时候就为自动排序好的数据)
后序遍历:左右根
TreeSet/TreeMap集合采用的是：中序遍历
二叉树的遍历均可以看成是递归的过程，也就是将一个树不断的划分成左子树、根、右子树的过程，直到不能再划分成一个子树
4.1Map集合
Map接口储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。
4.1.1常用方法
| 返回类型 | 介绍 |
|---|---|
| void | clear() 从此映射中移除所有映射关系（可选操作） |
boolean |
containsKey(Objectkey) 如果此映射包含指定键的映射关系，则返回 true。 |
boolean |
containsValue(Objectvalue) 如果此映射将一个或多个键映射到指定值，则返回 true。 |
Set<Map.Entry<K,V>> |
entrySet() 返回此映射中包含的映射关系的 Set 视图。 |
boolean |
equals(Objecto) 比较指定的对象与此映射是否相等。 |
V |
get(Objectkey) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 |
int |
hashCode() 返回此映射的哈希码值。 |
boolean |
isEmpty() 如果此映射未包含键-值映射关系，则返回 true。 |
Set<K> |
keySet() 返回此映射中包含的键的 Set 视图。 |
V |
[put](https://jdk6.net/util/Map.html#put(K, V))(Kkey,Vvalue) 将指定的值与此映射中的指定键关联（可选操作）。 |
void |
putAll(Map[K](https://jdk6.net/util/Map.html),? extends [V](https://jdk6.net/util/Map.html)> m)` 从指定映射中将所有映射关系复制到此映射中（可选操作）。 |
V |
remove(Objectkey) 如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 |
int |
size() 返回此映射中的键-值映射关系数。 |
Collection<V> |
values() 返回此映射中包含的值的 Collection 视图。 |
| default V replace(K key, V value) | 只有当目标映射到某个值时，才能替换指定键的条目l |
