什么是Java集合？
一般我们在碰到多个数据或者对象的问题时，需要一个容器来存储多个对象或者数据，为了解决这一问题首先想到的是数组，但是数组有一些缺点，比如初始化之后存储长度就确定了，一个数组只能存储一种类型的对象，数组提供的属性和方法比较少，数组存储的数据是有序的，可以重复的。当我们在解决问题之前并不确定需要存储对象的个数和类型时，数组并不能很好的解决这一问题。但是集合可以，集合可以用于存储数量不等的多个对象。
集合的特点：
- 集合只能存储对象。
- 集合存储的都是对象的引用。
- 集合可以存放不同类型，不限数量的数据类型。
Java集合框架
从上面这个框架图可以看出来Java集合核心部分就是Collection接口和Map接口。
1.Collection接口是高度抽象出来的集合，它包含了集合的基本操作和属性，Collection接口又可以分为List接口和Set接口，List接口和Set接口继承Collection接口。
- List是一个有序的队列，每个元素都有自己的索引，第一个索引值为0，List的实现类有LinkedList、ArrayList、Vector和Stack。
- Set是一个不允许有重复元素的集合，有点像数学上的集合，Set的实现类有HastSet和TreeSet。HashSet依赖于HashMap，它实际上是通过HashMap实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。
2.Map接口是一个映射接口，即key-value键值对。
3.Iterator迭代器接口主要用于遍历Collection集合中的元素。
4.Arrays和Collections。它们是操作数组、集合的两个工具类。
Collection接口
Collection接口是高度抽象出来的集合，它包含了集合的基本操作和属性，比如一些添加元素、清空、获取元素个数、删除、获取hash值等。
LIst接口
- List接口是Collection接口的子接口之一，之前也说到数组处理数据存在一些局限性，所以通常用List替代数字。
- List集合类中元素有序，可重复，集合中每个元素都有其对应的索引，可以根据索引实现对元素的访问。
- List的常用实现类包括：ArrayList、LinkedList和Vector
（1）ArrayList类是List接口的典型实现类、主要实现类，本质上ArrayList是一个动态数组，它允许任何符合规则的元素插入甚至包括null。ArrayList创建时，默认容量是0，如果要添加元素时，将容量增加到10，该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作，ArrayList可以进行随机访问，但是是非同步的。
以下情况适合使用ArrayList：
- 频繁访问列表中的某一个元素。
- 只需要在列表末尾进行添加和删除操作。
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
添加元素：add()方法
import java.util.ArrayList;
public class RunoobTest { public static void main(String[] args) { ArrayList<String> sites = new ArrayList<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Weibo"); System.out.println(sites); } }
访问元素：get()方法
import java.util.ArrayList;
public class RunoobTest { public static void main(String[] args) { ArrayList<String> sites = new ArrayList<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Weibo"); System.out.println(sites.get(1)); // 访问第二个元素 } }
修改元素：set()方法
import java.util.ArrayList;
public class RunoobTest {
public static void main(String[] args) {
ArrayList<String> sites = new ArrayList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
sites.set(2, "Wiki"); // 第一个参数为索引位置，第二个为要修改的值
System.out.println(sites);
}
}
删除元素：remove()方法
import java.util.ArrayList;
public class RunoobTest {
public static void main(String[] args) {
ArrayList<String> sites = new ArrayList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
sites.remove(3); // 删除第四个元素
System.out.println(sites);
}
}
迭代数组列表：for-each
import java.util.ArrayList;
public class RunoobTest {
public static void main(String[] args) {
ArrayList<String> sites = new ArrayList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
for (String i : sites) {
System.out.println(i);
}
}
}
排序：Collections 类也是一个非常有用的类，位于 java.util 包中，提供的 sort() 方法可以对字符或数字列表进行排序。
import java.util.ArrayList;
import java.util.Collections; // 引入 Collections 类
public class RunoobTest {
public static void main(String[] args) {
ArrayList<String> sites = new ArrayList<String>();
sites.add("Taobao");
sites.add("Wiki");
sites.add("Runoob");
sites.add("Weibo");
sites.add("Google");
Collections.sort(sites); // 字母排序
for (String i : sites) {
System.out.println(i);
}
}
}
（2）LinkedList类与ArrayList不同，LinkedList是一个链表，所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
以下情况适合使用LinkedList：
- 需要通过循环迭代来访问列表中的某些元素。
- 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素的操作。
- LinkedList 继承了 AbstractSequentialList 类。
- LinkedList 实现了 Queue 接口，可作为队列使用。
- LinkedList 实现了 List 接口，可进行列表的相关操作。
- LinkedList 实现了 Deque 接口，可作为队列使用。
- LinkedList 实现了 Cloneable 接口，可实现克隆。
- LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。
添加元素：add()、addFirst()、addLast()
import java.util.LinkedList;
public class ListTest {
public static void main(String[] args) {
LinkedList<String> s = new LinkedList<>();
s.add("admin");
s.add("root");
s.addFirst("first");
s.addLast("last");
System.out.println(s);
}
}
//输出结果：[first, admin, root, last]
（3）Vector与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。在各种list中最好吧ArrayList作为缺省选择，当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。
（4）Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
Set接口
Set接口是Collection接口的子接口，set接口没有提供额外的方法，Set集合不允许包含相同的元素，如果试着把两个相同元素加入到同一个Set集合中，则添加失败。需要注意的是虽然Set中元素没有顺序，但是元素在set中的位置是由该元素的HashCode决定的，其具体位置其实是固定的。Set判断两个元素是否相同不是用“==”，而是用equals()。Set接口有三个具体实现类：HashSet、LinkedHsahSet和TreeSet。
（1）HashSet
- 不能保证元素排列顺序
- 线程不安全
- 集合元素可以是null
Map接口
- Map和Collection接口并列存在的，，用于保存具有映射关系的数据：key-value，key和value可以是任何引用类型的数据。
- Map接口的常用实现类有：HashMap、TreeMap、LinkedHashMap和Properties，其中HashMap是Map接口使用频率最高的实现类。
常用方法：
put():
//添加元素 put(K key, V value); //将此映射中的指定值与指定键关联，如果映射以前包含该键的映射，则旧值将被指定的值替换。 //如果键是第一次存储，就直接存储元素，返回null //如果键不是第一次存在，就用值把以前的值替换掉，返回以前的值
get():
//根据键获取值 V get(Object key)
下面这块代码主要演示了get()和put()的使用：
remove()：使用remove(key)方法来删除key对应的键值对key-value
import java.util.HashMap;
public class RunoobTest {
public static void main(String[] args) {
// 创建 HashMap 对象 Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");
Sites.put(2, "Runoob");
Sites.put(3, "Taobao");
Sites.put(4, "Zhihu");
Sites.remove(4);
System.out.println(Sites);
}
}
//输出结果：{1=Google, 2=Runoob, 3=Taobao}
迭代HashMap
使用for-each来迭代HashMap中的元素，如果你只想获取 key，可以使用 keySet() 方法，如果你只想获取 value，可以使用 values() 方法。
import java.util.HashMap;
public class RunoobTest {
public static void main(String[] args) {
// 创建 HashMap 对象 Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");
Sites.put(2, "Runoob");
Sites.put(3, "Taobao");
Sites.put(4, "Zhihu");
// 输出 key 和 value
for (Integer i : Sites.keySet()) {
System.out.println("key: " + i + " value: " + Sites.get(i));
}
}
}
/*输出结果
key: 1 value: Google
key: 2 value: Runoob
key: 3 value: Taobao
key: 4 value: Zhihu
*/
除了这些方法还有其他方法：
实现类一：HashMap
在JDK1.7以及以前的版本中，HashMap的存储结构是数组+链表
JDK1.8版本HashMap的存储结构是数组+链表+红黑树
当一个值中要存储到 HashMap 中的时候会根据 Key 的值来计算出他的 hash，通过 hash 值来确认存放到数组中的位置，如果发生 hash 冲突就以链表的形式存储，当数组上的某个索引位置上的元素以链表形式存在的数据个数 > 8且当前数组的长度 > 64时，HashMap 会把这个链表转换成红黑树来存储。
源码解析：
DEFAULT_INITIAL_CAPACITY属性：表示初始容量为16
MAXIMUM_CAPACITY属性:HashMap支持的最大容量为30
DEFAUILT_LOAD_FACTOR属性：默认的负载因子为0.75，和扩容相关，主要表示当前hashmap的填充度
put():调用putVal()方法，放入键值对
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断当前hash表是否为空，如若为空，则需要进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据当前key的hash算出当前元素应该放到hash表中的下标，如果该位置为null，则放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//更新修改次数，防止多线程冲突
//如果当前节点数大于阈值，那么进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put的流程：
首先根据要放入的key计算hash，然后根据hash获取table中的放入位置，如果当前table为空，则进行初始化
判断放入位置是否为空，为空则直接放入，否则判断是否为红黑树节点，不是则为链表，则遍历链表查找是否存在相同的key，没找到则放入链表尾部并判断是否需要转为红黑树(TREEIFY_THRESHOLD)
判断当前节点数是否大于阈值，如果大于阈值则需要进行扩容
resize()：扩充当前容量
HashMap 每次扩容都是建立一个新的 table 数组，长度和容量阈值都变为原来的两倍，然后把原数组元素重新映射到新数组上，具体步骤如下：
1. 首先会判断 table 数组长度，如果大于 0 说明已被初始化过，那么按当前 table 数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍
2. 若 table 数组未被初始化过，且 threshold(阈值)大于 0 说明调用了 HashMap(initialCapacity, loadFactor) 构造方法，那么就把数组大小设为 threshold
3. 若 table 数组未被初始化，且 threshold 为 0 说明调用 HashMap() 构造方法，那么就把数组大小设为 16，threshold 设为 16*0.75
4. 接着需要判断如果不是第一次初始化，那么扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去，如果节点是红黑树类型的话则需要进行红黑树的拆分。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果容量大于最大容量，那么就将阈值设置为2的31次方-1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//容量小于最大容量，那么将容量扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧的容量扩大一倍小于2的30次并且旧的容量大于默认的初始化容量大小16，阈值也变为原来的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阈值为0，则重新计算阈值=表容量*负载因子
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap在JDK1.8较之前版本的变化：
1.HashMap map = new HashMap();//默认情况下，先不创建创度为16的数组
2.档首次调用map.put()时，创建长度为16的数组
3.数组为Node类型，在JDK7中成为Entry类型
4.形成链表结构时，新添加的kay-value从尾部插入
5.当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。
实现类二：LinkedHashMap
- LinkedHashMap是HashMap的子类
- 在HashMap的存储结构基础上，使用一对双向链表来记录添加元素的顺序
- 在accessOrder为true的情况下（默认为false，即默认不按访问顺序排序），put，get方法取完的节点放到链表尾部，按照Lru(最近最长时间未使用的方法进行排列,也便于删除最老的节点)，保证遍历顺序和插入顺序一致(后插入的一定在后面遍历到，先插入的先遍历)
实现类三：TreeMap
- TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于 有序状态。
- TreeSet底层使用 红黑树结构存储数据
实现类四：HashTable
HashTable是线程安全的
与HashMap不同的是，HashTable不允许使用null作为key和value
与HashMap一样的是，HashTable也不能保证key-value对的顺序
HashTable判断两个key或value相等的标准和HashMap一样
参考
https://www.javazhiyin.com/64568.html
https://www.liaoxuefeng.com/wiki/1252599548343744/1265118019954528