什么是容器
数组也是一种容器，可以存放对象或基本数据类型，数组的劣势在于不灵活，容器需要事先定义好，不能随着需求而改变而扩容。而容器则可以随时扩容来装对象，容器也称为集合。
容器的结构
单例集合
将数据一个一个的进行存储
双例集合
基于 key 和 value 的结构存储数据
Collection 接口
LIst接口：有序，可重复
ArrayList 容器类
是 List 接口的容器实现类，是 List 具体实现，ArrayList 底层用数组实现存储。1.8之前 ArrayList在 new 的时候就会创建默认长度为 10 的数组，而 1.8 则在 new 的时候会创建空数组，在添加的时候才进行长度创建，扩容是以 1.5 倍扩容。
特点：查询效率高，增删改查效率低，线程不安全（可以并行的调用）
Vector 容器类
使用和 ArrayList 相同，都实现 List 接口。底层是数组实现的，相关方法都加了同步检查，因此线程安全，效率低Vector 是立即初始化，容器扩容是 2 倍扩容。
LInkedList 容器类
底层使用的是双向链表实现的存储。特点是：查询效率低，增删效率高，线程不安全。双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前 一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到 所有节点。
ArrayLIst和 LinkedList的区别
ArrayList 底层是数组，查询效率高（通过索引获取元素），增删改效率低（增删的时候要做索引的移动，数组个数越多，移位个数也越多）
LikedList 底层是双向链表，查询效率低（查询时，节点越多需要查找该数据的节点就越多，因此节点越多查询的就越慢），增删效率高（增删不涉及元素移动，而是直接将元素放在节点上，进行双向链接即可）
set 接口：无序，不可重复
没有元素索引，只能遍历查找，不允许加入重复元素
Set 特点:无序、不可重复。无序指 Set 中的元素没有索引，我们只能遍历查找;不可 重复指不允许加入重复的元素。更确切地讲，新元素如果和 Set 中某个元素通过 equals() 方法对比为 true，则只能保留一个。
Set 常用的实现类有:HashSet、TreeSet 等，我们一般使用 HashSet。
HashSet 容器类
HashSet 是一个没有重复元素的集合，不保证元素的顺序。而且 HashSet 允许有 null 元 素。HashSet 是采用哈希算法实现，底层实际是用 HashMap 实现的(HashSet本质就是一个简化版的 HashMap)，因此，查询效率和增删效率都比较高。
HashSet 存储特征分析
HashSet 是一个不保证元素顺序，切不重复的集合，线程不安全，HashSet 允许有 null 元素（默认长度 16，下标 0-15）
- 无序
在 HashSet 中底层使用的是 HashMap 存储元素。HashMap 底层使用的是数组与链表实现元素的存储。元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。 - 不重复
当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的 equals() 方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素（单链表放在数组中）。
HashMap 源码分析
由于在 1.7还未引入链表转红黑树因此 1.8 引入当数组大于 64 时，节点个数大于 8 会转换为红黑树，转载其他作者博文进行参考
1.7 HashMap 源码分析
1.8 HashMap源码分析
TreeSet 容器类
TreeSet 是一个可以对元素进行排序的容器。底层实际是用 TreeMap 实现的，内部维持了一个简化版的 TreeMap，通过 key 来存储 Set 的元素。 TreeSet 内部需要对存储的元 素进行排序，因此，我们需要给定排序规则。
- 排序规则实现方式:
通过元素自身实现比较规则
在元素自身实现比较规则时，需要实现 Comparable 接口中的 compareTo 方法，该方法中用来定义比较规则。TreeSet 通过调用该方法来完成对元素的排序处理。
通过比较器指定比较规则
通过比较器定义比较规则时，我们需要单独创建一个比较器，比较器需要实现 Comparator 接口中的 compare 方法来定义比较规则。在实例化 TreeSet 时将比较器对象交给 TreeSet 来完成元素的排序处理。此时元素自身就不需要实现比较规则了。
案例
产生 1-10 之间的随机数([1,10]闭区间)，将不重复的 10 个随机数放到容器中。
使用list 容器进行实现
package com.container;
import java.util.ArrayList;
import java.util.List;
public class ListDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
while (true) {
int num = (int) (Math.random() * 10) + 1;//Math.random()返回 [0-1)之间的随机数
//判断当前元素在容器中是否存在
if (!list.contains(num)) {//不包含 num 元素就进行添加
list.add(num);
}
//结束循环
if (list.size() == 10) {
break;
}
}
for (Integer i : list) {
System.out.println(i);
}
}
}
使用 set 容器实现
package com.container;
import java.util.HashSet;
import java.util.Set;
public class SetDemo {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
while (true) {
int num = (int) (Math.random() * 10) + 1;
//将元素添加容器中，由于 set 类型容器是不允许重复元素，所以不需要进行判断
set.add(num);
if (set.size() == 10) {
break;
}
}
//hashCode在 Integer 方法时，返回的就是数值本身，因此看似排序了，实际只是凑巧
for (Integer i : set) {
System.out.println(i);
}
}
}
Map 接口
Map 接口的特点
Map 接口定义了双例集合的存储特征，它并不是 Collection 接口的子接口。双例集合的存储特 征是以 key 与 value 结构为单位进行存储。
Map 与 Collection 区别
- Collection 中的容器，元素是孤立存在的，向集合中存储元素采用一个
个元素的方式存储。 - Map 中的容器，元素是成对存在的k-V。每个元素由键与值两部分
组成，通过键可以找对所对应的值。 - Collection 中的容器称为单列集合，Map 中的容器称为双列集合。
- Map 中的集合不能包含重复的键，值可以重复;每个键只能对应一个值。
- Map 中常用的容器为 HashMap，TreeMap 等。
HashMap 容器
HashMap 是 Map 接口的接口实现类，它采用哈希算法实现，是 Map 接口最常用的 实现类。 由于底层采用了哈希表存储数据，所以要求键不能重复，如果发生重复，新的值 会替换旧的值。 HashMap 在查找、删除、修改方面都有非常高的效率。
HashMap 的底层存储
HashMap 底层实现采用了哈希表，这是一种非常重要的数据结构。
数据结构中由数组和链表来实现对数据的存储，他们各有特点。
(1) 数组:占用空间连续。寻址容易，查询速度快。但是，增加和删除效率非常低。
(2) 链表:占用空间不连续。寻址困难，查询速度慢。但是，增加和删除效率非常高。 那么，我们能不能结合数组和链表的优点(即查询快，增删效率也高)呢? 答案就是“哈希表”。 哈希表的本质就是“数组+链表”。需要注意的是
Hash 值得计算
Hash 值决定节点放在什么位置，也就是节点对象在数组当中的索引数
(1) 获得key对象的hashcode
首先调用 key 对象的 hashcode()方法，获得 key 的 hashcode 值。
(2) 根据 hashcode 计算出 hash 值(要求在[0, 数组长度-1]区间)
hashcode 是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的 hash 值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash 冲突”
- 一种极端简单和低下的算法是:
hash 值 = hashcode/hashcode;
也就是说，hash 值总是 1。意味着，键值对对象都会存储到数组索引 1
位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash
冲突”，HashMap 也退化成了一个“链表”。 - 一种简单和常用的算法是(相除取余算法):
hash 值 = hashcode%数组长度
这种算法可以让 hash 值均匀的分布在[0,数组长度-1]的区间。但是，这 种算法由于使用了“除法”，效率低下。JDK 后来改进了算法。首先约定数 组长度必须为 2 的整数幂，这样采用位运算即可实现取余的效果:hash 值 = hashcode&(数组长度-1)。
HashMap 底层源码分析
TreeMap 容器类
TreeMap 和 HashMap 同样实现了 Map 接口，所以，对于 API 的用法来说是没有区 别的。HashMap 效率高于 TreeMap;TreeMap 是可以对键进行排序的一种容器，在需要 对键排序时可选用 TreeMap。TreeMap 底层是基于红黑树实现的。
在使用 TreeMap 时需要给定排序规则:
- 元素自身实现比较规则（实现 Comparable<> 接口）
- 通过比较器实现比较规则（实现 Comparator<> 接口）
Iterator 迭代器接口
Collection接口继承了Iterable接口，在该接口中包含一个名为iterator的抽象方法，所 有实现了Collection接口的容器类对该方法做了具体实现。iterator方法会返回一个Iterator 接口类型的迭代器对象，在该对象中包含了三个方法用于实现对单例容器的迭代处理。
原理：通过接口定义的方法来判断元素是否存在，若有元素就获取当前游标的方法，并将游标移动到下一位，具体实现方法：
- boolean hasNext(); //判断游标当前位置是否有元素，如果有返回true，否则返
回false; - Objectnext(); //获取当前游标所在位置的元素，并将游标移动到下一个位置;
- void remove(); //删除游标当前位置的元素，在执行完next后该操作只能执行
一次;
Collections 工具类
Collections 是一个工具类，它提供了对 Set、List、Map 进行排序、填充、查找元素 的辅助方法。该类中所有的方法都为静态方法。
常用方法:
- void sort(List) //对 List 容器内的元素排序，排序的规则是按照升序进行排序。 void shuffle(List) //对 List 容器内的元素进行随机排列。
- void reverse(List) //对 List 容器内的元素进行逆续排列 。
- void fill(List, Object) //用一个特定的对象重写整个 List 容器。
- int binarySearch(List, Object)//对于顺序的 List 容器，采用折半查找的方法查找
特定对象。