集合
之前，我们保存多个数据使用的是数组，使用数组进行数据的保存存在明显的不足性
- 数组的长度在开始时必须指定，而且一旦指定，后续就不能修改了（灵活性较差）
- 数组保存的必须是同一类型的元素
- 使用数组进行增加/删除元素的代码实现比较麻烦
因此，引出了集合（多种数据存放在一起的数据结构）的概念来解决数组在保存数据时存在的缺陷：
- 集合可以动态保存任意多个对象，使用比较方便
- 集合提供了一系列方便操作对象的方法，如：
add、remove、set、get等 - 使用集合进行添加和删除元素实现方式比较简洁
我们需要理解集合的底层机制和了解集合的源代码
集合的框架体系图
集合主要分为两组，单列集合和双列集合
单列集合：
Collection接口有两个重要的子接口：List和Set，它们在集合中放的是单个单个的元素javaArrayList arrayList = new ArrayList(); arrayList.add("jlc"); arrayList.add("jack");继承体系图：
Collection接口继承了Iterable接口，其下面有两个重要的子接口：List和SetSet接口下面常用的子类主要为TreeSet类和HashSet类List接口下面常用的子类为：Vector类、ArrayList类和LinkedList类双列集合：
Map接口实现的子类都是双列集合，存放的是键值对类型的数据javaHashMap hashMap = new HashMap(); hashMap.put("No1", "北京"); // 以键值对的形式存放 hashMap.put("No2", "上海");继承体系图：
Collection接口
Collection接口继承了Iterable接口：
public interface Collection<E> extends Iterable<E>
接口特点
Collection接口实现类的特点：
collection实现子类可以存放多个元素，每个元素可以是Object- 有些
collection的实现类，可以存放重复的元素，有些不可以 - 有些
collection的实现类，有的的有序的(List)，有的不是有序的(Set)（存放进去的元素和取出的元素顺序并不是完全一样的） collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的
常用方法
collection接口的常用方法：以ArrayList来演示下面的方法：List list = new ArrayList();
add：添加单个元素java// 可以传入任何的Object对象 list.add("jlc"); list.add(25); // 本质为 list.add(new Integer(10)) list.add(true); System.out.println(list); // [jlc, 25, true]addAll：添加多个元素java// 可以直接传入集合进行元素的添加 ArrayList list2 = new ArrayList(); list2.add("tom"); lsit2.add(18); System.out.println(list.addAll(list2)); // [jlc, 25, true, tom, 18]remove：删除指定元素（可以通过索引进行删除，也可以通过具体内容进行删除）java// 根据索引进行删除，返回的是一个布尔类型，说明删除是否成功了 list.remove(0); // 删除第一个元素 System.out.println(list); // [25, true] // 指定删除某个元素，返回的是一个对象，即被删除的这个对象 list.remove(25); // 删除内容为25的这个元素 System.out.println(list); // [true]removeAll：删除多个元素java// 可以直接传入集合进行元素的删除 System.out.println(list.removeAll(list2)); // [jlc, 25, true]contains：查找元素是否存在java// 查找元素是否存在，返回的是一个布尔值，说明查找的元素是否存在 System.out.println(list.contains("jlc")); // truecontainsAll：查找多个元素是否都存在java// 可以直接传入集合判断该集合中的所有元素是否存在 System.out.println(list.containsAll(list2)); // truesize：获取元素个数javaSystem.out.println(list.size()); // 3isEmpty：判断是否为空javaSystem.out.println(list.sEmpty()); // falseclear：清空，将集合中的元素全部清除：list.clear();
这些Collection方法，后续的List和Set子接口都可以使用
遍历
collection接口有两种常用的遍历元素方式
使用Iterator迭代器
Iterator是Iterable中迭代对象的方法，也就是说实现了collection接口的子接口，都可以使用Iterator迭代器进行集合元素的迭代遍历
Iterator对象称为迭代器，主要用于遍历Collection集合中的元素- 所有实现了
Collection接口的集合类都有一个iterator()方法，用于返回一个实现了iterator接口的对象，即可以返回一个迭代器 iterator仅用于遍历集合，Iterator本身并不存放对象
迭代器的执行原理：
通过Iterator iterator = coll.iterator();（coll是一个集合）得到一个集合的迭代器，每次调用iterator.next()方法，就会将指针往下移动一次，并且将数据取出来，移动的时候还需要判断是否还有下一个元素，通过hasNext()方式进行判断，如果下面还有元素则返回true
迭代器基本使用语法：
while(iterator.hasNext()) {
// 使用next()方法 1.指针下移 2.将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}在调用
iterator.next()方法之前必须要先调用iterator.hasNext()进行检测，如果不调用且下一条记录无效，直接使用iterator.next()会抛出NoSuchElementException异常
使用案例：
Collection col new ArrayList();
col.add("jlc");
col.add(25);
col.add(true);
// 遍历col集合
// 1.先得到col对应的迭代器
Iterator iterator = coll.iterator();
// 2.使用while循环遍历集合
while(iterator.hasNext()) {
// 使用next()方法 1.指针下移 2.将下移以后集合位置上的元素返回
// 返回下一个元素，类型是Object
Object obj = iterator.next();
System.out.println(obj);
}
// 当退出while循环后，这时iterator迭代器指向的是最后的元素，如果希望再次遍历，需要重置迭代器（即将最后的指针重新指向到最开始）
iterator = coll.iterator(); // 重置迭代器指针到最开始可以使用快捷键
itit，回车，快速的得到迭代器while循环的代码片段
for循环增强
for循环增强是遍历集合的第二种方法，增强for循环可以代替iterator迭代器，增强for是简化版的iterator，底层还是迭代器。只能用于遍历集合和数组
基本语法：
for(元素类型 元素名: 集合名或数组名) {
访问元素
}使用案例：
Collection col new ArrayList();
col.add("jlc");
col.add(25);
col.add(true);
// 使用for循环增强来遍历col集合
for(Object obj: col) {
System.out.println(obj);
}
// 增强for也可以直接在数组中使用
int[] nums = {1, 8, 12, 23};
for(int i: nums) {
System.out.println(i);
}可以使用快捷键
I，回车，得到增强for的代码片段
List接口
List接口是Collection接口的子接口
接口特点
List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复javaList list = new ArrayList(); list.add("jlc"); list.add(25); // 本质为 list.add(new Integer(10)) list.add(true); list.add("jlc"); // 可重复 System.out.println(list); // [jlc, 25, true, jlc] 取出的顺序和传入的顺序一致List集合中的每个元素都有其对应的顺序索引，即支持索引List容器中的元素都对应一个整数型的序号（索引）记载其在容器中的位置，可以根据序号存取容器中的元素java// 索引是从0开始的 System.out.println(list.get(2)); // trueList接口常用的实现子类有：ArrayList、LinkedList和Vector
常用方法
List集合里添加了一些根据索引来操作集合元素的方法
List list = new ArrayList();
list.add("jlc");
list.add("tom");void add(int index, Object ele)：在index位置插入ele元素java// 在索引为1的位置插入一个对象 list.add(1, "frank"); // 如果不加索引，默认是加到最后的，这和Collection的add方法一致 System.out.println(list); // [jlc, frank, tom]boolean addAll(int index, Collection eles)：从index位置开始将eles集合中的所有元素加进来javaList list2 = new ArrayList(); list2.add("jlc2"); list2.add("tom2"); list.addAll(1, list2); System.out.println(list); // [jlc, jlc2, tom2, tom]Object get(int index)：获取指定index索引位置的元素javaSystem.out.println(list.get(0)); // jlcint indexOf(Object obj)：返回obj内容在集合中首次出现的位置javaSystem.out.println(list.indexOf("jlc")); // 0int lastIndexOf(Object obj)：返回obj内容在集合中最后一次出现的位置Object remove(int index)：移除指定index索引位置的元素，并返回此元素javalist.remove(0); // 移除集合中的第一个元素Object set(int index, Object ele)：替换指定位置索引index的元素为elejavalist.set(1, "JLC"); // 将索引位置为1的地方，将内容替换为JLC System.out.println(list); // [jlc, JLC]List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合，toIndex索引的元素是取不到的javalist.add("jlc"); List resList = list.subList(1, 2); System.out.println(resList); // [tom]
遍历
List有三种遍历方式：
List list = new ArrayList(); // 这里的ArrayList可以换成Vector和LinkedList，遍历一样
list.add("jlc");
list.add("tom");方式一：使用
iterator迭代器java// 1.先得到col集合对应的迭代器 Iterator iterator = list.iterator(); // 2.使用while循环遍历集合 while(iterator.hasNext()) { // 使用next()方法 1.指针下移 2.将下移以后集合位置上的元素返回 // 返回下一个元素，类型是Object Object obj = iterator.next(); System.out.println(obj); }方式二：使用增强
forjavafor(Object obj: list) { System.out.println(obj); }方式三：使用普通
forjavafor(int i = 0; i < list.size(); i++) { Object obj = list.get(i); System.out.println(obj); }
对集合进行排序
对集合进冒泡排序，我们一般编写一个静态方法
public static void sort(List list) {
int listSize = list.size();
for(int i = 0; i < listSize - 1; i++) {
for(int j = 0; j < listSize - 1 - i; j++) {
// 取出对象Book
Book book1 = (Book) list.get(j);
Book book2 = (Book) list.get(j + 1);
// 根据对象中的价格进行排序
if(book1.getPrice() > book2.getPrice()) {
list.set(j, book2);
list.set(j + 1, book1);
}
}
}
}ArrayList类
ArrayList类实现了List接口
ArrayList类集合，可以存放所有的元素，甚至可以存放null；并且可以存放多个一样的元素javaArrayList arrayList = new ArrayList(); arrayList.add("jlc"); arrayList.add(null); arrayList.add(null); System.out.println(arrayList); // [jlc, null, null]ArrayList类是由数组来实现数据存储的ArrayList类基本等同于Vector，除了ArrayList类是线程不安全的（但执行效率高），在多线程下，不建议使用ArrayList类
底层源码
ArrayList类的底操作机制和源码是非常重要的，以下是几个重要的结论：
ArrayList中维护了一个Object类型的数组elementData，用于存放实际的数据，数组的类型是Object[]，因此可以存放所有类型的数据transient Object[] elementData;transient表示属性不会被序列化当创建
ArrayList对象时，如果使用的是无参构造器ArrayList()，则初始elementData的容量为0，第一次添加时，则扩容为10，其元素的内容都存放null，如果需要再次扩容，则扩容为1.5倍，以此类推java// 小案例来debug源码的执行过程 ArrayList list = new ArrayList(); // 使用无参构造器创建ArrayList对象 for(int i = 1; i <=10; i++) { list.add(i); } for(int i = 11; i <=15; i++) { list.add(i); } list.add(100); list.add(200); list.add(null);
集合空间扩容过程：
集合的扩容每次都会去检测，但不是每次都扩容，只有容量不足时，才会进行扩容
先将数组的大小赋值给
oldCapacity，第一次为0，则oldCapacity为0oldCapacity + (oldCapacity >> 1)表示原先数组加上原先数组的一半（向右移动一位），即扩容1.5倍，在第一次是没有使用1.5倍的扩容机制，因为newCapacity的值也是0，那么集合的容量就使用我们最小的容量10如果新的容量比最大值还要大，我们使用
hugeCapacity()方法进行处理使用
Arrays.copyOf()方式进行扩容，可以保障原先的数据不丢失，后面在是扩容的空间，使用null进行填充IDEA代码编辑器在默认情况下，Debug显示的数据是简化后的，如果我们需要看到完整的数据，我们需要进行设置修改
取消勾选：
Enable alternative...选项如果使用的是指定大小的构造器
ArrayList(int)，则初始elementData容量为指定大小，如果需要扩容，则直接扩容为1.5倍，以此类推
Vector类
定义：
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.SerializableVector底层也是一个对象数组：protected Objectp[] elementData;Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized
LinkedList类
LinkedList类底层实现了双向链表和双端队列的特点，可以添加任意元素（元素可以重复），包括null
LinkedList类的线程不安全，没有实现同步
基本概念
LinkedList底层维护了一个双向链表，维护了两个属性first和last，分别指向首节点和尾节点
每个节点（Node对象），里面维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点，最终实现双向链表
LinkedList类的元素的添加和删除，不是通过数组完成的，只是将该对象的前面节点的next属性指向该对象的后面节点；该对象后面节点的prev属性指向该对象前面的节点，即可实现该对象的删除，相对来说效率较高（不涉及到数组的扩容）
模拟一个简单的双向链表：
public class LinkedList01 {
public static void main(String[] args) {
// 拟一个简单的双向链表
// 创建三个节点，此时的三个节点孤零零的，没有任何关系
Node jlc = new Node("jlc");
Node tom = new Node("tom");
Node jac = new Node("jac");
// 连接三个节点，形成双向链表
// 前向指向
jlc.next = tom;
tom.next = jac;
// 反向指向
jac.pre = tom;
tom.pre = jlc;
Node first = jlc; // 让first引用指向jack，就是双向链表的头节点
Node last = jac; // 让last引用指向jac，就是双向链表的尾节点
// 从头到尾进行遍历输出
while(true) {
if(first == null) {
break;
}
// 输出信息
System.out.println(first);
first = first.next; // 指向下一个节点
}
// 后续如果需要进行重新遍历，需要让first重新指向第一个节点：first = jlc;
// 从尾到头进行遍历输出
while(true) {
if(last == null) {
break;
}
// 输出信息
System.out.println(last);
last = last.next; // 指向下一个节点
}
// 后续如果需要进行重新遍历，需要让last重新指向最后一个节点：last = jac;
// 链表添加对象/数据
// 要求在tom和jac之间插入一个对象smith
Node smith = new Node("smith");
smith.next = jac;
smith.pre = tom;
tom.next = smith;
jac.pre = smith;
}
}
// 定义一个Node类，该类的对象表示双向链表的一个节点
class Node {
public Object item; // 真正存放数据的地方
public Node next; // 指向后一个节点
public Node pre; // 指向前一个节点
public Node(Object name) {
this.item = name;
}
public String toString() {
return "Node name=" + item;
}
}底层源码
LinkedList类的增删改查案例和底层源码分析：
增加节点
public class LinkedListCRUD {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
System.out.println(linkedList); // [1, 2]
}
}源码解读：
/* 源码解读
1. LinkedList linkedList = new LinkedList();
进入无参构造器 public LinkedList() {}
2. 这时linkedList的属性 first = null last = null
3. 执行
public boolean add(E e) {
linkLast(e);
return true;
}
*/- 将新的节点，加入到双向链表的最后：
一开始
first和last都指向null这个时候节点
l指向的也是空之后创建新的节点，将
add添加的内容放入因此，第一个节点，
first、last和newNode都指向这个节点，这个节点的next和pre为null，只有一个节点，前面没有指向，后面也没有指向
对于linkedList.add(2);
new Node<>(l, e, null)：将l赋值给pre，也就是说第二个节点（新增的节点）的pre属性指向第一个节点
last = newNode：将last的指向，从原先的第一个节点指向了现在这个新增的节点
l.next = newNode：将第一个节点的next属性指向第二个节点
这个时候，可以看出
first还是指向第一个节点，而last指向了最后一个元素
size++：表示节点的数量加一，size表示目前节点的数量
modCount++：表示修改了多少次
删除节点
public class LinkedListCRUD {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 删除节点
linkedList.remove(); // 表示删除第一个节点，本质上调用removeFirst()
// remove(int index)表示删除指定索引位置的节点
System.out.println(linkedList); // [2, 3]
}
}源码解读：
执行：
javapublic E remove() { return removeFirst(); // 本质上调用removeFirst() }执行
removeFirst()方法：javapublic E removeFirst() { final Node<E> f = first; if(f == null) { throw new NoSuchElementException(); } return unlinkFirst(f); }执行
unlinkFirst(f);方法进行双向链表中第一个节点元素的删除：
final E element = f.item;表示将第一个节点的内容拿出来赋值给element，这个是作为删除函数的返回值，其实不是关键final Node<E> next = f.next;表示将next指向下一个节点f.item = null;和f.next = null;将第一个节点的内容和next属性指向nullfirst = next;将first指向第二个元素，同时next.prev = null;将第二个节点的pre属性指向null，即于原先的第一个节点断开，这时第一个节点没有任何的链接的，就成为一个垃圾了，最后就会被垃圾回收机制给回收掉
修改节点
public class LinkedListCRUD {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 修改节点
linkedList.set(1, 10); // 将索引为1的节点的内容，修改为10
System.out.println(linkedList); // [1, 10, 3]
}
}查找节点
public class LinkedListCRUD {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 查找节点
System.out.println(linkedList.get(1)); // 查找索引为1的节点的内容 2
}
}遍历
LinkedList类是实现的List接口，遍历方式与List类似，可以使用迭代器和增强for循环，因为LinkedList类可以拿到具体的索引，因此也可以使用普通的for循环进行遍历
各种有序集合的使用选择
Vector类和ArrayList类进行比较：
- 在开发中，需要线程同步安全时，考虑使用
Vector
ArrayList类和LinkedList类的比较：
- 如果我们改查的操作多，推荐选择
ArrayList - 如果我们增删的操作多，推荐使用
LinkedList - 一般来说，在程序中，大多数都是使用查询，因此使用
ArrayList类为主 - 在项目中也可以将这两者穿插的使用，更加灵活
- 两者都是线程不安全的，在单线程中推荐使用
Set接口
Set接口的基本介绍
- 无序（添加和取出的顺序不一致），没有索引
- 不允许重复元素，所以做多包含一个
null JDK中实现Set接口的常用类有：HashSet和TreeSet
常用方法：和List接口一样，Set接口也是Collection的子接口，因此，常用方法和Collection接口一样
public class SetMethod {
public static void main(String[] args) {
// Set接口的实现类的对象（Set接口对象）
Set set = new HashSet();
set.add("join");
set.add("lucy");
set.add("join"); // 重复
set.add(null);
set.add(null); // 再次添加null
// 对指定的元素进行删除 set.remove(null);
// 输出的结果是无序的（即添加的顺序和取出的顺序不一致）（但是取出的顺序是固定的，每一次取出的内容顺序是一样的），且不能存放重复的对象，同时可以添加一个null，重复的元素只会输出一次
System.out.println(set); // [null, john, lucy, jack]
}
}遍历方式：和Collection接口一样，因为Set接口是Collection接口的子接口，因此可以使用迭代器进行遍历，同时还可以使用增强for进行循环，但是不能使用索引的方式来获取元素，因此不能使用普通的for循环
// 使用迭代器进行遍历
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Object obj = iterator.next();
System.out.println(obj);
}
// 使用增强for循环
for(Object o: set) {
System.out.print(o);
}HashSet类
基本说明
HashSet类实现了Set接口HashSet的底层其实是HashMap，HashMap的底层是数组+链表+红黑树java// 源码解读 public HashSet() { map = new HashMap<>(); }模拟一个简单的数据+链表结构（这样的方式可以使数据存储高效，如果链表的长度大于8个，且数组表的大小大于64，这时就会将其结构变成红黑树，树的效率更高）：
java// 一个数组中，其元素中存放的是节点Node，Node可以指向下一个Node，形成一个链表结构 public class HashSetStructure { public static void main(String[] args) { // 模拟一个HashSet的底层（实际上就是HashMap的底层结构） // 创建一个数组，数组的类型是Node[]，有些地方直接将Node[]数组称为表 Node[] table = new Node[16]; // table的大小为16 // 创建节点 Node john = new Node("john", null); // 下一个节点为空 // 将节点放到索引为2的数组表位置 table[2] = john; // 再创建一个节点，并挂载到john节点后面，形成了链表的结构 Node jack = new Node("jack", null); john.next = jack; // 继续创建一个节点 Node rose = new Node("Rose", null); jack.next = rose; // 将rose节点挂载到jack节点后面 } } // 节点类，存储数据，可以指向下一个节点，从而形成链表 class Node { Object item; // 存储数据 Node next; // 指向下一个节点 public Node(Object item, Node next) { this.item = item; } }HashSet可以存放null值，但是只能有一个null，即元素不能重复（元素/对象不能重复）java// 元素/对象不能重复 public class HashSetMethod { public static void main(String[] args) { Set set = new HashSet(); // lucy字符串指向的是同一个常量池中的常量 set.add("lucy"); // 返回的是true 表示添加成功 set.add("lucy"); // 不能添加重复的元素，返回的是false，表示添加失败 // new 的对象，虽然name属性相同，但是两个对象不是同一个对象 set.add(new Dog("tom")); // 返回true，表示添加成功 set.add(new Dog("tom")); // 返回true，表示添加成功 // 经典面试题，需要看源码具体分析 set.add(new String("jlc")); // true set.add(new String("jlc")); // false 加入失败 } } class Dog { private String name; public Dog(String name) { this.name = name; } @Override public String toString() { return "Dog{" + "name='" + name + '\'' + '}'; } }HashSet不能保证元素是有序的（即不保证存放元素的顺序和取出的顺序一致），取决于hash后，再确定索引的结果
扩容机制
HashSet底层的扩容机制，其结论如下：
HashSet的底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）为0.75 = 12，临界值作为缓冲空间，防止大量数据进入导致的阻塞- 如果
table数组使用到了临界值12，就会扩容到16*2 = 32，新的临界值就是32*0.75=24，依次类推 - 添加一个元素时，先得到这个元素
hash值（哈希值通过特定的方式进行运算，其值实际上就是数字），之后会将哈希值转换成索引值（决定元素具体存放到哪个索引的位置） - 在具体存放的时候，会找到存储表
table，看这个索引位置是否已经存放元素，如果没有，直接加入；如果有，会调用equals（程序员自己定义的，不能理解为单单的字符串内容比较，字符串中的equals方法也是String类进行重写的）进行比较，如果相同，就放弃添加，如果不相同，就添加到最后 - 在
jdk8中，如果一条链表的元素个数大于等于TREEIFY_THRESHOLD（默认值是8），并且table的大小大于等于MIN_TREEIFY_CAPACITY（默认为64），就会进行树化（红黑树）
源码解读：
// 运行代码
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println(hashSet);调用底层的构造器：
javapublic HashSet() { map = new HashMap<>(); }调用添加
add方法：javapublic boolean add(E e) { // 这里的e就是添加的内容，如"java" // 添加之后，如果返回null，表示添加成功了 return map.put(e, PRESENT)==null; // PRESENT是hashSet中的静态对象，没有什么意义，占位 }执行
put方法：会执行hash(key)的计算，得到key对应的哈希值，这个哈希值不完全等价于hashCode，进行了按位异或，再进行了无符号的右移16位的操作javapublic V put(K key, V value) { // key: "java" value: Object@550 value是PRESENT return putVal(hash(key), key, value, false, true); }key的值是变化的，但是value的值是不变的（静态的）hash(key)的计算，每添加一个元素节点，都会进行哈希值的计算：javastatic final int hash(Object key) { int h; // 如果key为null，则返回0，如果不为null，通过按位异或和无符号右移16位，返回对应的哈希值 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >> 16); }执行
putVal()方法：添加内容的核心方法：javafinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量 // 下面的table是hsahMap的属性，类型是Node[]数组，存放Node节点的数组 // 一开始初始化的时候，table是为空的，或者其长度为0 if ((tab = table) == null || (n = tab.length) == 0) // 执行tab = resize()，执行后的tab变成了16个空间大小，但是其内容为null n = (tab = resize()).length; // 每一次的节点添加，都会经过判断 // 根据key,(n - 1) & hash]计算其哈希值，得到应该放到table表的哪个索引位置 // 并把这个位置的对象，赋值给p，判断p是否为空 // 如果p为空，表示还没有添加任何东西，就创建一个Node(key="java", value=PRESENT)，放到该位置 if ((p = tab[i = (n - 1) & hash]) == null) // 同时将hash哈希值存入，用于后续判断传入的值与该值是否相等 tab[i] = newNode(hash, key, value, null); // 如果当前索引位置不为空（是链表或红黑树） else { Node<K,V> e; K k; // 定义辅助变量 // 有三种情况的条件判断 // 情况一：判断当前索引位置对应链表的第一个节点的 hash 值是否和新结点的 hash 值相同 // 并且满足下面两个条件之一： // 1. 准备加入的 key 和 p 指向的Node节点的 key 是同一个对象 // 2. 不是同一个对象，但是内容相同（equals()相同）（这里的equals()方法，是由程序员来确定的，不能简单的理解为比较字符串的内容） // 这时就不能进行元素节点的加入 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) // 将当前索引位置的结点赋值给 e e = p; // 情况二：判断当前索引位置是否是红黑树，如果是红黑树，就通过下面的方式进行比较（红黑树方式） else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 情况三：当前索引位置是链表，使用for循环在链表比较过程中，有一个节点元素于当前添加的元素一样，就立即退出循环，不执行该元素节点的加入，如果执行完整个循环，都没有发现一样的，就会在链表的后面进行添加该新节点 else { for (int binCount = 0; ; ++binCount) { // 比较到最后了，加入元素节点后，退出 // 比较的是当前节点的下一个，当前节点和新元素的比较之前比较过了 if ((e = p.next) == null) { p.next = newNode(hans, key, value, null); // 把元素添加到链表后，立即进行判断，该链表是否已经达到8个节点，如果达到8个节点，就调用treeifyBin()方法，对当前链表进行树化（转成红黑树） if (binCount >= TREEIFY_THRESHOLD -1) treeifyBin(tab, hash); // 注意：在进行树化时还会进行表长度的判断，如果表的长度小于64，那么是不会进行树化的，而是考虑将表进行扩容来进行这个问题的解决 break; } // 比较的过程中，发现一样的，立即退出 if (e.hans == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 用 e 是否为空来判断是否存在重复结点 if (e != null) { // existing mapping for key V oldValue = e.value; // 判断是否更新 value // 这里 value 始终是一个 object 对象，用来占位，所以不需要更新 if (!onlyIfAbsent || oldValue == null) e.value = value; // 一个空方法，供 HashMap 的子类实现 afterNodeAccess(e); // 返回旧的 value return oldValue; // 返回旧值，表示添加失败的，原先的表中有这个值了 } } ++modCount; // 记录修改次数 // 判断现在size值是否超过12，如果超过12就进行扩容 // size就是我们每加入一个节点Node(k, v, h, next)，不管是加在第一个位置还是链的最后一个位置（横向加和纵向加），size都会加一 if (++size > threshold) resize(); afterNodeInsertion(evict); // hashMap留给子类去实现的，对于hashMap来说，这个方式是空方法 return null; // 返回空表示添加成功了 }table数组扩容机制，执行resize()方法：javafinal Node<K,V>[] resize() { // 定义辅助变量 Node<K,V>[] oldTab = table; // 将初始化的table交给oldTab // 旧数组长度 0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧临界值 int oldThr = threshold; // 新的数组长度和临界值 int newCap, newThr = 0; // 第 n 此扩容，n > 1 if (oldCap > 0) { // 判断旧数组长度是否大于最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新数组长度扩大两倍 // 并判断新数组长度是否 < 最大值，同时旧数组长度是否 >= 初始长度（16） else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新数组长度临界值扩大两倍 newThr = oldThr << 1; // double threshold } // 判断旧数组长度临界值是否 > 0 else if (oldThr > 0) // initial capacity was placed in threshold // 新数组长度为旧数组长度临界值 // oldCap 为 0，因为如果 > 0 就走第一个条件了 newCap = oldThr; // 第一次扩容，执行的代码块 else { // zero initial threshold signifies using defaults // 新的数组长度默认为 16（默认table数组表的开辟空间为16个长度） newCap = DEFAULT_INITIAL_CAPACITY; // static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 位左移4位1*2*2*2*2 // 新的临界值默认为 12，节点数组使用12个就开始扩容了 DEFAULT_LOAD_FACTOR为0.75 // 防止大量数据进入导致阻塞 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 判断是否新临界值为 0 if (newThr == 0) { // 将新数组大小的 0.75 倍赋值给 ft // 初始化 HashMap 时就指定了 loadFactor 为默认临界因子（0.75） float ft = (float)newCap * loadFactor; // 如果新的数组大小 < 最大长度，并且 ft < 最大长度，新的数组长度临界值就为 ft // 否则为整数的最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 改变为新的临界值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 定义新的数组，并设置了容量大小为16 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 改变数组 table = newTab; // rable数组表有了空间，但是其内容都是null // 判断旧数组是否为空 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) // 没有下一个结点就直接将该结点移动到新数组上 // 注意：索引是由数组长度和 hash 值共同决定的 // 此时计算索引用的是新数组的长度，结果可能会与旧数组的索引不同 newTab[e.hash & (newCap - 1)] = e; // 判断该索引位置是不是一个红黑树 else if (e instanceof TreeNode) // 移动树上的结点 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 该索引位置是一个链表 else { // preserve order // 定义 lowHead，lowTail，表示低位链表的头结点和尾节点 Node<K,V> loHead = null, loTail = null; // 定义 hightHead，hightTail，表示高位链表的头结点和尾节点 // 低位链表和高位链表里的位，表示的是数组索引位 // 由于数组长度的增加，新数组的索引位置可能不变，也可能变大 // 如果不变，就用低位链表；如果变大，就用高位链表 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 定义下一个结点 do { // 获取下一个结点 next = e.next; // 计算新新数组的索引位是否不变 if ((e.hash & oldCap) == 0) { // 判断当前结点是否是头结点 // 因为最开始定义 loTail 为 null // 而如果添加了一个结点后，loTail 就会指新的结点，不为 null 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; }
练习案例
定义一个Employee类，该类包含private成员属性name、age，要求：创建3个Employee放入HashSet中；当name和age的值相同时，认为是相同的员工，不能添加到HashSet集合中
public class HashSetExercise {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add(new Employee("jlc", 25));
hashSet.add(new Employee("tom", 20));
hashSet.add(new Employee("jack", 30));
// 此时加入了三个元素节点到hashSet集合中
hashSet.add(new Employee("tom", 20)); // 添加不进去，name和age与原来的集合中有相同的
}
}
class Employee {
private string name;
private int age;
public Employee(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Employee{" + "name='" + name + '\'' + ", age=" + age + '}';
}
// 重写equals方法，如果name和age值相同，则返回相同的哈希值
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return age == employee.age && Object.equals(name, employee.name);
}
// 重写hashCode方法
@Override
public int hashCode() {
return Object.hash(name, age);
}
}使用快捷键alt+insert，选择equals() and hashCode()，使用jdk7以上的模板，自定义选择哪些值相同来表示哈希值相同，如下所示：
判断下面代码输出什么：Person类按照id和name重写了hashCode和equals方法
HashSet set = new HashSet();
Person p1 = new Person(1001, "AA");
Person p1 = new Person(1002, "BB");
set.add(p1);
set.add(p2);
p1.name = "CC";
// 删除不成功，通过当前的p1，其id为1001，name为CC，计算出来的哈希值与(1001, "AA")的哈希值一定不同，其哈希值的对应的表索引没有内容，就会删除失败
set.remove(p1);
System.out.print(set); // 输出的还是之前的两个对象 Person{1002,BB} Person{1001,CC}
set.add(new Person(1001, "CC")); // 可以加入
System.out.print(set); // 输出三个对象 Person{1002,BB} Person{1001,CC} Person{1001,CC}
set.add(new Person(1001, "AA")); // 也可以加入成功，加在链后面
System.out.print(set); // 输出四个对象
Person{1002,BB} Person{1001,CC} Person{1001,CC} Person{1001,AA}
LinkedHashSet类
LinkedHashSet是HashSet的子类，其底层是一个LinkedHashMap（LinkedHashMap是HashMap的子类），底层维护了一个数组+双向链表（HashSet类维护的是数组+单向的链表），与HashSet类最大的区别就是使用了双向链表
LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用双向链表维护元素的次序，这使得元素看起来是以插入的顺序保存的（取出来的数据和添加的数据，顺序是一样的）
LinkedHashSet不允许添加重复元素
- 双向链表有头（
head指向链表第一个节点的引用）和尾（tail指向链表最后一个节点的引用）- 每一个节点都有
pre或者brfore和next或者after属性，指向当前节点的前一个节点和后一个节点，进而组成一个双向链表- 双向链表前面有一个节点，后面也有一个节点，后面的节点执行第二个添加的元素，第二个元素的前面节点指向第一个元素，会在具体的
before和after中体现，构成双向链表，添加时也会进行比较，如果相同，就加入不进来- 双向链表有头节点和尾节点，在遍历元素的时候，是按照头到尾的顺序进行遍历的（能够保证获取元素的时候是有序的，即插入顺序和遍历顺序一致）
在第一次添加的时候，直接将数组table扩容到16，存放的节点类型是LinkedHashMao$Entry（即数组是HashMap$Node[]，存放的元素\数据是LinkedHahsMap$Entry类型，继承关系是在内部类中完成的）
练习案例
有一个Car类，属性有name和price，如果name和price一样，则认为是相同的元素，就不能进行添加
public class LinkedHashSetExercise {
public static void main(String[] args) {
LinkedHashSet linkedHashSet = new LinkedHashSet();
linkedHashSet.add(new Car("宝马", 300000));
linkedHashSet.add(new Car("大众", 100000));
linkedHashSet.add(new Car("奥迪", 350000));
// 上述三个对象都是可以加入到LinkedHashSet集合中的
System.out.println(linkedHashSet); // 输出的顺序和输入的顺序一致
linkedHashSet.add(new Car("奥迪", 350000)); // 加入不了
}
}
class Car {
private string name;
private double price;
public Employee(String name, double price) {
this.name = name;
this.price = price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Double getPrice() {
return price;
}
public void setPrice(double price) {
this.price = price;
}
@Override
public String toString() {
return "Car{" + "name='" + name + '\'' + ", price=" + price + '}';
}
// 重写equals方法，如果name和price值相同，则返回相同的哈希值
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Car car = (Car) o;
return price == car.price && Object.equals(name, car.name);
}
// 重写hashCode方法
@Override
public int hashCode() {
return Object.hash(name, price);
}
}TreeSet类
当我们使用无参构造器（默认的构造器）创建TreeSet时，输出仍然是无序的
TreeSet treeSet = new TreeSet();
// 添加数据
treeSet.add("jack");
treeSet.add("jlc");
treeSet.add("mark");
System.out.println(treeSet); // 在没有做处理的时候，输出也是无序的（与输入的顺序不一致）如果我们希望对于添加的元素，按照字符串大小来排序，可以使用TreeSet提供的一个构造器，可以传入一个比较器（匿名内部类），并指定排序规则（在构造器存放数据的时候，会根据排序规则进行数据的存放，后续数据遍历输出时，就是有序的）：
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 进行字符串的大小比较
// 字符串从小到大排序（先比较第一个，如果一样再比较第二个，以此类推）
return ((String) o1).compareTo((String) o2); // o2写在前面则从大到小进行排序
}
});
// 添加数据
treeSet.add("jack");
treeSet.add("jlc");
treeSet.add("mark");
System.out.println(treeSet); // [jack， jlc, mark]源码解读：
构造器将传入的比较器对象，赋给了
TreeSet的底层TreeMap的属性this.comparatorjavapublic TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }在调用
treeSet.add("jack");时，在底层会执行到下面的语句：javapublic boolean add(E e) { return m.put(e, PRESENT) == null; }javaif (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); // cpr就是我们的匿名内部类，会动态绑定到我们的匿名内部类（对象）中的compare方法 if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else // 如果相等，即返回0，即这个Key就没有加入 return t.setValue(value); } while (t != null); }
我们也可以按照字符串的长度大小进行排序：（这个时候，长度相等的元素是加入不进去的）
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 进行字符串的大小比较
// 根据字符串的长度大小进行排序 从小到大进行排序
return ((String) o1).length() - ((String) o2).length();
}
});
treeSet.add("jack"); // 可以加入
treeSet.add("jlc"); // 可以加入
treeSet.add("mark"); // 不能加入 长度相等在比较的过程中，在判断的时候返回了0，不会加入// 判断下面代码会不会抛出异常
public class Homework {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet;
// 从底层源码进行分析
// add方法，因为TreeSet()构造器没有传入Comparator接口的匿名内部类
// 所以在底层 Comparator<? super K> k = (Comparable<? super K>) key; 会把传入的Person对象转成Comparator类型，如果key这个类型实现了Comparable接口，才能转换成功，否则抛出异常
tessSet.add(new Person()); // 抛出ClassCastException异常
}
}
class Person {}解决上述问题，我们只需要实现Comparable接口即可：
class Person implements Comparable {
@Override
public int compareTo(Object o) {
return 0; // 所有对象的返回值都是0 因此treeSet集合中只能加一个该对象的元素
}
}常见面试题
分析HashSet和TreeSet分别任何实现去重：
HashSet的去重机制：hashCode() + equals()，底层通过存入对象，进行运算得到一个hash值，通过hash值得到对应的索引，如果发现table表该索引所在的位置没有数据，就直接存放，如果有数据，就进行equals遍历比较（equals由程序员定义），如果比较后，不同，就加入，否则不加入TreeSet的去重机制：如果你传入了一个Comparator匿名对象，就使用实现的compare方法进行去重，如果方法返回0，就认为是相同的元素/数据，就不进行添加；如果没有传入一个Comparator匿名对象，则以你添加对象的Compareable接口的compareTo方式进行去重
Map接口
Map接口存放的是双列的形式（键值对的形式，k为具体输入的不同对象，v也是为具体存放的内容），对于Set接口，从表面上看只是存放值的形式，但是从底层上看，存放的也是键值对的形式，k具体输入的不同的对象内容，而v为系统提供的PRESENT常量来替代的
接口特点
Map接口在实际的开发中非常的实用
Map接口的常用实现类：HashMap、Hashtable和Properties
jdk8的Map接口实现类的特点
Map和Collection并列存在，用于保存具有映射关系的数据Key-ValuejavaMap map = new HashMap(); map.put("no1", "jlc"); // k-v键值对的形式存放Map中的key和value可以为任何的引用类型的数据（本质上都是Object类型），会封装到HashMap$Node对象中Map中的key不允许重复，原因和HashSet一样，如果key的值一样，会使用后面代码的value将前面的进行替换（新的替换旧的）Map中的value可以重复（key不同，value是可以重复的）Map中的key可以为null，value也可以为null，注意key为null的情况只能有一个，value为null的情况可以重复常用的
String类作为Map的keykey和value之间存在单向一对一的关系，即通过指定的key总能找到对应的valuejavaMap map = new HashMap(); map.put("no1", "jlc"); // k-v键值对的形式存放 System.out.println(map.get("no1")); // 通过key去找具体的value jlcMap存放数据的key-value示意图如下：
一对
k-v是放在一个Node中的（Node除了有k和v属性，还有hash属性和next属性（指向下一个节点）），又因为Node实现了Entry接口，即一对k-v就是一个Entry（key是存放在Set集合中的，value是存放在Collection接口实现的子类中的），但是真正的key和value是存放在HashMap$Node数据类型中的（HashMap$Node最后存放在table表中），而Set集合和Collection接口实现的子类只是指向了HashMap$Node数据类型，本质使用两个集合进行指向是为了方便遍历总之，
k-v最后在表中的存放方式为：HashMap$Node node = newNode(hash, key, value, null);，但是为了方便程序员进行遍历，还会创建EntrySet集合（EntrySet提供了非常重要的方法getKey()和getValue()），该集合存放的元素类型是Entry，而一个Entry对象就有k, v（EntrySet<Entry<K, V>>），在EntrySet中，定义的类型是Map.Entry，但实际上存放的还是HashMap$Node（HashMap$Node实现了Map.Entry接口），除此之外，还提供了keySet()方法，直接将Key封装到一个Set的集合中，即单独的取出Key对象，也可以通过values()方法，将Value封装到一个Collection的集合中，即单独取出Value对象java// EntrySet提供了非常重要的方法getKey()和getValue() Map map = new HashMap(); map.put("no1", "jlc"); // k-v键值对的形式存放 Set set = map.entrySet(); for(Object obj: set) { Map.Entry entry = (Map.Entry) obj; System.out.println(entry.getKey() + "-" + entry.getValue()); // no1-jlc } // 单独取出Key和Value Set key = map.keySet(); Collection value = map.values();
常用方法
Map接口的常用方法：以HashMap来演示下面的方法：
Map map = new HashMap();
map.put("no1", "jlc");
map.put("no2", "tom");put：添加remove：根据键删除映射关系java// 通过key删除 map.remove("no1");get：根据键获取值javaObject val = map.get("no1");size：获取元素个数（多少个键值对）javamap.size(); // 2isEmpty：判断个数是否为0（判断是否为空）：map.isEmpty();clear：清除：map.clear();containsKey：查找键是否存在，返回的是布尔类型的数据javamap.containsKey("no1"); // true
遍历
对于Map集合：
Map map = new HashMap();
map.put("no1", "jlc");
map.put("no2", "tom");Map接口实现的类有六种遍历方式，由简单到复杂依次为：
先取出所有的
Key，再通过Key取出对应的Value（最后遍历完可以看到key和value）javaSet keyset = map.keySet(); // 取出所有key // 方式一：使用增强for for(Object key: keyset) { System.out.println(key + "-" + map.get(key)); // no1-jlc no2-tom } // 方式二：使用迭代器 Interator iterator = keyset.iterator(); while(iterator.hashNext()) { Object key = iterator.next(); System.out.println(key + "-" + map.get(key)); // no1-jlc no2-tom }直接将所有的
values取出（最后遍历完只能看到value）java// Collection values = map.values(); // 取出所有的value // 此时就可以使用所有的Collection的遍历方法 // 方式三：使用增强for for(Object value: values) { System.out.println(value); // jlc tom } // 方式四：使用迭代器 Interator iterator = values.iterator(); while(iterator.hashNext()) { Object value = iterator.next(); System.out.println(value); // jlc tom }通过
EntrySet来获取key和value（最后遍历完可以看到key和value）javaSet entrySet = map.entrySet(); // 通过entrySet()取出来的对象，就是entry，就是Node的接口 // 方式五：使用增强for for(Object entry: entrySet) { // 将entry转成Map.Entry Map.Entry m = (Map.Entry) entry; System.out.println(m.getKey() + "-" + m.getValue()); // no1-jlc no2-tom } // 方式六：使用迭代器 Interator iterator = entrySet.iterator(); while(iterator.hashNext()) { Object entry = iterator.next(); Map.Entry m = (Map.Entry) entry; System.out.println(m.getKey() + "-" + m.getValue()); // no1-jlc no2-tom }
HashMap类
HashMap类是Map接口使用频率最高的实现类，以key-val对的方式来存储数据（HashMap$Node数据类型）
注意事项：
key不能重复，但是value可以重复，允许使用null键和null值- 如果添加相同的
key，则会覆盖原来的key-val，等于修改（key不会替换，val会替换） - 与
HsahSet一样，HashMap不会保证映射的顺序，因为底层是以hash表的方式来存储的（jdk8的底层是数组+链表+红黑树） HashMap没有实现同步，因此线程是不安全的，方法上没有做同步互斥的（没有synchronized）
底层机制
HashMap的扩容机制和HashSet完全一样，因为HashSet底层就是使用HashMap，具体的扩容机制为：
HashMap底层维护了Node类型的数组table，默认为null，在创建对象时，将加载因子（loadFactor）初始化为0.75- 当添加
key-val时，通过key的哈希值得到在table的索引，然后判断该索引处是否有元素，如果没有元素则直接添加；如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等，如果相等，则直接替换val，如果不相等，需要判断是树结构还是链表结构，做出相应的处理。如果添加时发现容量不够，则需要扩容 HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）为0.75 = 12，临界值作为缓冲空间，防止大量数据进入导致的阻塞- 如果
table数组使用到了临界值12，就会扩容到16*2 = 32，新的临界值就是32*0.75=24，依次类推（按照原来的2倍进行扩容） - 在
jdk8中，如果一条链表的元素个数大于等于TREEIFY_THRESHOLD（默认值是8），并且table的大小大于等于MIN_TREEIFY_CAPACITY（默认为64），就会进行树化（红黑树） - 一条链表的元素个数大于等于
TREEIFY_THRESHOLD（默认值是8），不会立刻进行树化，会先判断table的大小大于等于MIN_TREEIFY_CAPACITY（默认为64），如果大于64，会进行树化，如果小于64，会进行一次扩容，依次类推 - 剪枝：如果对于红黑树，在后续进行删除，随着不断的删除，树枝节点越来越少，就会将树重新转换成链表
源码解读：
// 运行代码
HashMap hashMap = new HashMap();
hashMap.put("java", 10);
hashMap.put("php", 20);
hashMap.put("java", 20); // 会进行替换调用底层的构造器：
new HashMap<>()初始化加载因子
loadfactor = 0.75将数组的内容全部置为空：
HashMap$Node[] table = null执行
put方法：会执行hash(key)的计算，得到key对应的哈希值，这个哈希值不完全等价于hashCode，进行了按位异或，再进行了无符号的右移16位的操作javapublic V put(K key, V value) { // key = "java" value = 10 // hash(key)通过特定的算法计算出哈希对应的哈希值 return putVal(hash(key), key, value, false, true); }hash(key)的计算，每添加一个元素节点，都会进行哈希值的计算：javastatic final int hash(Object key) { int h; // 如果key为null，则返回0，如果不为null，通过按位异或和无符号右移16位，返回对应的哈希值 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >> 16); }执行
putVal()方法：添加内容的核心方法：javafinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量 // 下面的table是hsahMap的属性，类型是Node[]数组，存放Node节点的数组 // 一开始初始化的时候，table是为空的，或者其长度为0 if ((tab = table) == null || (n = tab.length) == 0) // 执行tab = resize()，执行后的tab变成了16个空间大小，但是其内容为null n = (tab = resize()).length; // 每一次的节点添加，都会经过判断 // 根据key,(n - 1) & hash]计算其哈希值，得到应该放到table表的哪个索引位置 // 并把这个位置的对象，赋值给p，判断p是否为空 // 如果p为空，表示还没有添加任何东西，就创建一个Node(key="java", value=10)，放到该位置 if ((p = tab[i = (n - 1) & hash]) == null) // 同时将hash哈希值存入，用于后续判断传入的值与该值是否相等 tab[i] = newNode(hash, key, value, null); // 如果当前索引位置不为空（是链表或红黑树） else { Node<K,V> e; K k; // 定义辅助变量 // 有三种情况的条件判断 // 情况一：判断当前索引位置对应链表的第一个节点的 hash 值是否和新结点的 hash 值相同 // 并且满足下面两个条件之一： // 1. 准备加入的 key 和 p 指向的Node节点的 key 是同一个对象 // 2. 不是同一个对象，但是内容相同（equals()相同）（这里的equals()方法，是由程序员来确定的，不能简单的理解为比较字符串的内容） // 这时就不能进行元素节点的加入 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) // 将当前索引位置的结点赋值给 e e = p; // 情况二：判断当前索引位置是否是红黑树，如果是红黑树，就通过下面的方式进行比较（红黑树方式） else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 情况三：当前索引位置是链表，使用for循环在链表比较过程中，有一个节点元素于当前添加的元素一样，就立即退出循环，不执行该元素节点的加入，如果执行完整个循环，都没有发现一样的，就会在链表的后面进行添加该新节点 else { for (int binCount = 0; ; ++binCount) { // 比较到最后了，加入元素节点后，退出 // 比较的是当前节点的下一个，当前节点和新元素的比较之前比较过了 if ((e = p.next) == null) { p.next = newNode(hans, key, value, null); // 把元素添加到链表后，立即进行判断，该链表是否已经达到8个节点，如果达到8个节点，就调用treeifyBin()方法，对当前链表进行树化（转成红黑树） if (binCount >= TREEIFY_THRESHOLD -1) treeifyBin(tab, hash); // 注意：在进行树化时还会进行表长度的判断，如果表的长度小于64，那么是不会进行树化的，而是考虑将表进行扩容来进行这个问题的解决 break; } // 比较的过程中，发现一样的，立即退出 if (e.hans == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 用 e 是否为空来判断是否存在重复结点 if (e != null) { // existing mapping for key V oldValue = e.value; // 判断是否更新 value // 这里 value 始终是一个 object 对象，用来占位，所以不需要更新 if (!onlyIfAbsent || oldValue == null) e.value = value; // 替换key对应的value // 一个空方法，供 HashMap 的子类实现 afterNodeAccess(e); // 返回旧的 value return oldValue; // 返回旧值，表示添加失败的，原先的表中有这个值了 } } ++modCount; // 记录修改次数 // 判断现在size值是否超过12，如果超过12就进行扩容 // size就是我们每加入一个节点Node(k, v, h, next)，不管是加在第一个位置还是链的最后一个位置（横向加和纵向加），size都会加一 if (++size > threshold) resize(); afterNodeInsertion(evict); // hashMap留给子类去实现的，对于hashMap来说，这个方式是空方法 return null; // 返回空表示添加成功了 }table数组扩容机制，执行resize()方法：javafinal Node<K,V>[] resize() { // 定义辅助变量 Node<K,V>[] oldTab = table; // 将初始化的table交给oldTab // 旧数组长度 0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧临界值 int oldThr = threshold; // 新的数组长度和临界值 int newCap, newThr = 0; // 第 n 此扩容，n > 1 if (oldCap > 0) { // 判断旧数组长度是否大于最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新数组长度扩大两倍 // 并判断新数组长度是否 < 最大值，同时旧数组长度是否 >= 初始长度（16） else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新数组长度临界值扩大两倍 newThr = oldThr << 1; // double threshold } // 判断旧数组长度临界值是否 > 0 else if (oldThr > 0) // initial capacity was placed in threshold // 新数组长度为旧数组长度临界值 // oldCap 为 0，因为如果 > 0 就走第一个条件了 newCap = oldThr; // 第一次扩容，执行的代码块 else { // zero initial threshold signifies using defaults // 新的数组长度默认为 16（默认table数组表的开辟空间为16个长度） newCap = DEFAULT_INITIAL_CAPACITY; // static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 位左移4位1*2*2*2*2 // 新的临界值默认为 12，节点数组使用12个就开始扩容了 DEFAULT_LOAD_FACTOR为0.75 // 防止大量数据进入导致阻塞 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 判断是否新临界值为 0 if (newThr == 0) { // 将新数组大小的 0.75 倍赋值给 ft // 初始化 HashMap 时就指定了 loadFactor 为默认临界因子（0.75） float ft = (float)newCap * loadFactor; // 如果新的数组大小 < 最大长度，并且 ft < 最大长度，新的数组长度临界值就为 ft // 否则为整数的最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 改变为新的临界值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 定义新的数组，并设置了容量大小为16 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 改变数组 table = newTab; // rable数组表有了空间，但是其内容都是null // 判断旧数组是否为空 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) // 没有下一个结点就直接将该结点移动到新数组上 // 注意：索引是由数组长度和 hash 值共同决定的 // 此时计算索引用的是新数组的长度，结果可能会与旧数组的索引不同 newTab[e.hash & (newCap - 1)] = e; // 判断该索引位置是不是一个红黑树 else if (e instanceof TreeNode) // 移动树上的结点 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 该索引位置是一个链表 else { // preserve order // 定义 lowHead，lowTail，表示低位链表的头结点和尾节点 Node<K,V> loHead = null, loTail = null; // 定义 hightHead，hightTail，表示高位链表的头结点和尾节点 // 低位链表和高位链表里的位，表示的是数组索引位 // 由于数组长度的增加，新数组的索引位置可能不变，也可能变大 // 如果不变，就用低位链表；如果变大，就用高位链表 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 定义下一个结点 do { // 获取下一个结点 next = e.next; // 计算新新数组的索引位是否不变 if ((e.hash & oldCap) == 0) { // 判断当前结点是否是头结点 // 因为最开始定义 loTail 为 null // 而如果添加了一个结点后，loTail 就会指新的结点，不为 null 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; }
Hashtable类
Hashtable类是实现Map接口的子类，存放的元素是键值对，即k-v，但是Hashtable的键和值都不能为null（否则会抛出NullPointerException异常），Hashtable使用方式基本上和HashMap一样，只是Hashtable是线程安全的
Hashtable table = new Hashtable();
table.put("no1", "jlc");
table.put("no2", "tom");
table.put(null, "mark"); // 报错
table.put("no3", null); // 报错底层机制
Hashtable类底层有数组Hashtable$Entry[]，初始化大小为11，加载因子为0.75，因此其临界值为8（11*0.75），如果表中的size大于临界值8个，就会进行扩容，扩容到23（没有按照2倍进行扩容，有着自己的扩容机制：乘以2再加一（(oldCapacity << 1) + 1）），其临界值变成17（23*0.75），具体代码如下：
Properties类
Properties类继承了Hashtable类，并实现了Map接口，也是使用键值对的形式来保存数据，其使用与Hashtable类似，也是不能使用null
Properties properties = new Properties();
properties.put("no1", "jlc");
properties.put("no2", "tom");
properties.put(null, "mark"); // 报错
properties.put("no3", null); // 报错
properties.put("no2", "tom1"); // 如果有相同的key，其value会被替换常用方法：
put：增加get：通过key获取对应的值可以使用另外的一种查找方法：
getProperty()，也是通过key进行查找remove：通过key删除对应的内容
Properties类还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改
TreeMap类
TreeMap类是实现了Map接口的子类
当我们使用无参构造器（默认的构造器）创建TreeMap时，输出仍然是无序的
TreeMap treeMap = new TreeMap();
// 添加数据
treeMap.put("jack", "杰克");
treeMap.put("mark"， "马克");
treeMap.put("tom"， "汤姆");
System.out.println(treeMap); // 在没有做处理的时候，输出也是无序的（与输入的顺序不一致）如果我们希望对于添加的元素，按照字符串大小来排序，可以使用TreeMap提供的一个构造器，可以传入一个比较器（匿名内部类），并指定排序规则（在构造器存放数据的时候，会根据排序规则进行数据的存放，后续数据遍历输出时，就是有序的）：
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 对传入的key字符串，进行大小比较排序
// 字符串从小到大排序（先比较第一个，如果一样再比较第二个，以此类推）
return ((String) o1).compareTo((String) o2); // o2写在前面则从大到小进行排序
}
});
// 添加数据
treeMap.put("jack", "杰克");
treeMap.put("mark"， "马克");
treeMap.put("tom"， "汤姆");
System.out.println(treeMap); // 输出结果根据key字符串的大小进行了排序
// {jack=杰克, mark=马克, tom=汤姆}我们也可以按照字符串的长度大小进行排序：（这个时候，长度相等的元素是加入不进去的）
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 进行字符串的大小比较
// 根据字符串的长度大小进行排序 从小到大进行排序
return ((String) o1).length() - ((String) o2).length();
}
});
// 添加数据
treeMap.put("jack", "杰克");
treeMap.put("mark"， "马克"); // key字符串长度与jack相等，因此不能被添加
treeMap.put("tom"， "汤姆");子类集合比对
HashMap与Hashtable的对比
集合选择规则
在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特征进行选择：
先判断存储的类型（一组对象（单列）或一组键值对（双列））
一组对象：使用
Collection接口的某一个实现子类允许重复：使用
List增删多：使用
LinkedList类（底层维护了一个双向链表）改查多：使用
ArrayList类（底层维护Object类型的可变数组）不允许重复：使用
Set无序：使用
HashSet类（底层是HashMap，维护了一个哈希表，即数组+链表+红黑树）排序：使用
TreeSet类（通过匿名内部类重写构造器）插入和取出顺序一致：使用
LinkedHashSet（底层是LinkedHashMap，维护了数组+双向链表）
一组键值对：使用
Map接口的某一个实现子类- 键无序：使用
HashMap类（底层维护了哈希表，jdk7：数组+链表；jdk8：数组+链表+红黑树） - 键排序：使用
TreeMap类（通过匿名内部类重写构造器） - 键插入和取出顺序一致：使用
LinkedHashMap（底层是HashMap） - 读取文件：使用
Properties类
- 键无序：使用
Collections工具类
Collections是一个操作Set、List和Map等集合的工具类
Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作
排序操作
创建ArrayList集合，用于测试：
List list = new ArrayList();
list.add("tom");
list.add("smith");
lsit.add("king");
list.add("milan");
System.out.print(list); // 原先的排序顺序 [tom, smith, king, milan]reverse(List)：反转List中的元素顺序javaCollections.reverse(list); System.out.print(list); // 与输入的顺序相反的排序输出 [milan, king, smith, tom]shuffle(List)：对List集合元素进行随机排序：Collections.shuffle(list);sort(List)：根据元素的自然顺序（字符串大小）对指定List集合元素按升序排序javaCollections.sort(list); System.out.print(list); // [king, milan, smith, tom]sort(List, Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序java// 按照字符串的长度大小进行排序 Collections.sort(list, new Comparator() { @Override public int compare(Object o1, Object o2) { // 进行字符串的大小比较 // 根据字符串的长度大小进行排序 从小到大进行排序 return ((String) o1).length() - ((String) o2).length(); } }); System.out.print(list); // [tom, king, milan, smith]swap(List, int, int)：将指定List集合中的i处元素和j处元素进行交换javaCollections.swap(list, 0, 1); // 第一个位置和第二个位置进行交换 System.out.print(list); // [smith, tom, king, milan]
查找和替换操作
创建ArrayList集合，用于测试：
List list = new ArrayList();
list.add("tom");
list.add("smith");
lsit.add("king");
list.add("milan");
System.out.print(list); // 原先的排序顺序 [tom, smith, king, milan]Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素（即自然排序中的最大值，最后一个位置的元素）（min同理）javaSystem.out.print(Collections.max(list)); // tomObject max(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最大元素（min同理）java// 返回长度最大的元素 Object maxObject = Collections.max(list, new Comparator() { @Override public int compare(Object o1, Object o2) { // 进行字符串的大小比较 // 根据字符串的长度大小进行排序 从小到大进行排序 return ((String) o1).length() - ((String) o2).length(); } }); System.out.print(maxObject); // smithint frequency(Collection, Object)：返回指定集合中指定元素的出现次数java// 查看tom元素出现的次数 System.out.print(Collections.frequency(list, "tom")); // 1void copy(List dest, List src)：将src集合中的内容复制到dest集合中javaList dest = new ArrayList(); // 为了完成拷贝，我们需要先给dest赋值，大小为list.size()，赋值可以赋空值 for(int i = 0; i < list.size(); i++) { dest.add(""); } // 不加会抛异常 Collections.copy(dest, list);boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换List对象中的所有旧值java// 将集合中的tom替换为Tom Collections.replaceAll(list, "tom", "Tom");