概念：对象的容器，定义了对多个对象进行操作的常用方法。可实现数组的功能。
整体结构图
List集合
ArrayList扩容机制
- 当new一个ArrayList时，实际是调用了ArrayList的无参构造，这时其初始容量为0
- 在添加第一个元素时，会将
DEFAULT_CAPACITY的值作为第一次扩容的容量 为10 - 如果再添加元素，超过了所扩容的容量，则会进入
grow()方法int newCapacity = oldCapacity + (oldCapacity >> 1);这句代码进行扩容，每次都是原来数组长度的1.5倍 也就是说，第二次扩容后长度为15
//源码分析：
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小空实例的共享空数组实例。
//我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所包含的元素个数
*/
private int size;
/**
* 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果传入的参数大于0，创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果传入的参数等于0，创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//其他情况，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*默认无参构造函数
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Set
image.png
HashSet 如何检查重复
- 当你把对象加入
HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较 - 如果没有相符的
hashcode，HashSet会假设对象没有重复出现。 - 但是如果发现有相同
hashcode值的对象，这时会调用equals()方法来检查hashcode相等的对象是否真的相同。 - 如果
equals()返回true，则HashSet就不会让加入操作成功。 - 如果
equals()返回false，则形成链表
Map
image.png
HashMap
类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 加载因子
final float loadFactor;
}
HashMap的创建过程
- HashMap刚创建时，table为null（为了节省空间），当添加第一个元素的时候，table容量调整为16
- 当元素的个数大于阈值（16*0.75=12）时，会进行扩容，扩容大小为原来的2倍。目的是减少调整元素的个数。
- jdk1.8 当链表的长度大于8（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，会将链表转化为红黑树，以减少搜索时间。
- jdk1.8 当链表长度小于6时，调整为链表
- jdk1.8之前，链表为头插入；jdk1.8之后，链表为尾插入
HashMap 和 Hashtable 的区别
-
线程是否安全：HashMap是非线程安全的，HashTable是线程安全的,因为HashTable内部的方法基本都经过synchronized修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap吧！）； -
效率：因为线程安全的问题，HashMap要比HashTable效率高一点。另外，HashTable基本被淘汰，不要在代码中使用它； -
对 Null key 和 Null value 的支持：HashMap可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出NullPointerException。 -
初始容量大小和每次扩充容量大小的不同 ：
① 创建时如果不指定容量初始值，Hashtable默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而HashMap会将其扩充为 2 的幂次方大小（HashMap中的tableSizeFor()方法保证，下面给出了源代码）。也就是说HashMap总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。 -
底层数据结构：JDK1.8 以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制
hashCode()与 equals() 的相关规定：
- 如果两个对象相等，则 hashcode 一定也是相同的
- 两个对象相等,对两个 equals() 方法返回 true
- 两个对象有相同的 hashcode 值，它们也不一定是相等的
- 综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。
- 参考文章
ArrayList 到底是如何进行扩容的
