1.概述
集合是 Java 中提供的一种容器，可以用来存储多个数据。集合主要分为两大系列：Collection和Map，Collection 表示一组对象，Map表示一组映射关系或键值对。集合和数组既然都是容器，它们有啥区别呢？
- 数组的长度是固定的。集合的长度是可变的。
- 数组中可以存储基本数据类型值，也可以存储对象，而集合中只能存储对象。
2. 集合的框架体系
Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出三个子接口：List、Set、Queue, 因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。List: 存储的元素是有序的、可重复的。Set: 存储的元素是无序的、不可重复的。Queue: 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。Map: 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
Collection
Map
3. Collection接口和常用方法
3.1 概述
Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为 Collection 的元素。一些 Collection 实现类允许有重复的元素，而另一些则不允许。一些 Collection实现类是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List、Queue）实现。
Collection中常用的方法:
| 方法 | 描述 |
|---|---|
| add(E e) | 添加元素对象到当前集合中 |
| addAll(Collection<? extends E> other) | 添加other集合中的所有元素对象到当前集合中，即this = this ∪ other |
| remove(Object obj) | 从当前集合中删除第一个找到的与obj对象equals返回true的元素 |
| removeAll(Collection<?> coll) | 从当前集合中删除所有与coll集合中相同的元素。即this = this - this ∩ coll |
| isEmpty() | 判断当前集合是否为空集合 |
| contains(Object obj) | 判断当前集合中是否存在一个与obj对象equals返回true的元素 |
| containsAll(Collection<?> c) | 判断c集合中的元素是否在当前集合中都存在。即c集合是否是当前集合的“子集” |
| int size() | 获取当前集合中实际存储的元素个数 |
| retainAll(Collection<?> coll) | 当前集合仅保留与c集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即this = this ∩ coll |
| toArray() | 返回包含当前集合中所有元素的数组 |
方法示例:
java">import java.util.ArrayList;
import java.util.Collection;public class Collection_ {public static void main(String[] args) {// 创建集合对象 多态形式Collection<String> coll = new ArrayList<>();// 向集合中添加元素coll.add("科比");coll.add("詹姆斯");coll.add("麦迪");System.out.println(coll); // [科比, 詹姆斯, 麦迪]// 判断某个元素是否在集合中System.out.println("判断科比是否在集合中: " + coll.contains("科比"));// 删除集合中的元素System.out.println("删除詹姆斯: " + coll.remove("詹姆斯"));System.out.println("操作之后的集合元素为" + coll);// 统计集合中元素个数System.out.println("集合中有 " + coll.size() + " 个元素");// 判断集合是否为空System.out.println("集合是否为空: "+coll.isEmpty());// 将集合转换为Object数组Object[] obj = coll.toArray();for (int i = 0; i < obj.length; i++) {System.out.println(obj[i]);}}
}
3.2 遍历方式1-Iterator(迭代器)
3.2.1 概述
java.util.Iterator是 Java 集中的一员, Iterator对象称为迭代器, 主要用于遍历 Collection 集合中的元素。所有实现了 Collection 接口的集合类都有一个 iterator() 方法, 返回一个实现了 Iterator 接口的对象, 即可返回一个迭代器。
什么叫迭代?
即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续在判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。
3.2.2 迭代器的常用方法
| 方法 | 描述 |
|---|---|
| public Iterator iterator() | 获取集合对应的迭代器，用来遍历集合中的元素的。 |
| public E next() | 返回迭代的下一个元素。 |
| public boolean hasNext() | 如果仍有元素可以迭代，则返回 true。 |
| public void remove() | 移除迭代器中返回的最后一个元素。 |
java">import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class Iterator1 {public static void main(String[] args) {// 创建集合对象Collection<String> coll = new ArrayList<>();// 添加元素coll.add("串串星人");coll.add("吐槽星人");coll.add("汪星人");// 获取迭代器对象Iterator<String> iterator = coll.iterator();while (iterator.hasNext()) { // 判断是否有迭代对象String s = iterator.next();// 获取迭代出的对象System.out.println(s);}}
}
3.2.3 迭代器的实现原理
当遍历集合时, 首先通过调用集合的 iterator() 方法获得迭代器对象, 然后使用 hasNext() 方法判断集合中是否存在下一个元素, 如果存在, 则调用 next() 方法将元素取出, 否则说明已经到达了集合末尾, 停止遍历元素。
Iterator迭代器对象在遍历集合时，内部采用指针来跟踪集合中的元素，为了更好地理解迭代器的工作原理，通过下图来演示Iterator对象迭代元素的过程：
- ① 在调用Iterator的next方法前，迭代器的索引位于第一个元素前，指向第一个元素
- ② 当第一次调用迭代器的next方法时，返回第一个元素，然后迭代器的索引会向后移动一位，指向第二个元素，当再次调用next方法时，返回第二个元素，然后迭代器的索引会再向后移动一位，指向第三个元素
- ③ 依此类推，直到hasNext方法返回false，表示到达了集合的末尾，终止对元素的遍历
3.2.4 应用实例
Book对象
java">public class Book {private String name;private String author;private double price;public Book() {}public Book(String name, String author, double price) {this.name = name;this.author = author;this.price = price;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getAuthor() {return author;}public void setAuthor(String author) {this.author = author;}public double getPrice() {return price;}public void setPrice(double price) {this.price = price;}@Overridepublic String toString() {return "Book{name='" + name + '\'' + ", author=" + author + ", price=" + price + '}';}
}
BookIterator类
java">import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class BookIterator {public static void main(String[] args) {Collection<Book> col = new ArrayList<>();col.add(new Book("三国演义", "罗贯中", 10.1));col.add(new Book("小李飞刀", "古龙", 5.1));col.add(new Book("红楼梦", "曹雪芹", 34.6));Iterator<Book> iterator = col.iterator();while (iterator.hasNext()) {Book book = iterator.next();System.out.println("book= " + book);}iterator.next(); // 异常: java.util.NoSuchElementException}
}
3.3 遍历方式2-增强for循环
3.3.1 概述
增强for循环(也称for each循环)是JDK1.5以后出来的一个高级for循环，专门用来遍历数组和集合的。
3.3.2 基本语法
java">for(元素类型 元素名: 集合名或数组名){ //访问元素
}
3.3.3 应用实例
遍历数组: 通常只进行遍历元素，不要在遍历的过程中对数组元素进行修改。
java">public class ForEach1 {public static void main(String[] args) {int[] arr = {3, 5, 6, 58, 100};for (int i : arr) {System.out.println(i);}}
}
遍历集合: 通常只进行遍历元素，不要在遍历的过程中对集合元素进行增加、删除、替换操作。
java">public class Dog {private String name;private int age;public Dog() {}public Dog(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "Dog{" + "name='" + name + '\'' + ", age=" + age + '}';}
}import java.util.ArrayList;
import java.util.Iterator;public class ForEach2 {public static void main(String[] args) {// 创建对象ArrayList<Dog> list = new ArrayList<>();list.add(new Dog("小花", 3));list.add(new Dog("小白", 4));list.add(new Dog("小黑", 5));System.out.println("=============增强for遍历==================");//遍历元素--增强for循环for (Dog dog : list) {System.out.println("dog=" + dog);}System.out.println("=============迭代器遍历==================");// 遍历元素--迭代器Iterator<Dog> iterator = list.iterator();while (iterator.hasNext()) {Dog dog = iterator.next();System.out.println("dog=" + dog);}}
}
4. List接口和常用方法
4.1 概述
java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性将实现List接口的对象称为List集合。List接口的特点如下:
- ① List 集合中的元素有序(即添加顺序与取出顺序一致)
- ② List 集合中的每个元素都有其对应的顺序索引, 即支持索引; 通过索引可取出对应的元素
- ③ List 集合中的元素是可重复的, 通过 equals 方法可比较是否为重复元素
List 集合关心元素是否有序，而不关心是否重复。
4.2 List 常用方法
List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。
| 方法 | 描述 |
|---|---|
| boolean add(E e) | 将指定的元素到这个列表的末尾 |
| void add(int index, E element) | 在列表中指定的位置上插入指定的元素 |
| boolean addAll(Collection<? extends E> c) | 追加指定集合的所有元素到这个列表的末尾 |
| boolean addAll(int index, Collection<? extends E> c) | 将指定的集合中的所有元素插入到指定位置的列表中 |
| E get(int index) | 返回此列表中指定位置的元素。 |
| List subList(int fromIndex, int toIndex) | 返回list中指定下标的元素组成的list集合,左闭右开 |
| int indexOf(Object obj) | 返回列表中首次出现的指定元素的索引，如果列表不包含该元素，则返回-1 |
| int lastIndexOf(Object obj) | 返回列表中最后出现的指定元素的索引，如果列表不包含该元素，则返回-1 |
| boolean remove(Object o) | 移除列表中首次出现的指定元素（如果存在） |
| E remove(int index) | 移除列表中指定位置的元素 |
| E set(int index, E ele) | 替换列表中指定位置的元素 |
| int size() | 返回列表中的元素个数 |
| boolean isEmpty() | 如果列表不包含元素，则返回true |
| Iterator iterator() | 返回列表中元素的迭代器 |
使用示例
java">import java.util.ArrayList;
import java.util.List;public class List_ {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("张三丰");list.add("金毛狮王");System.out.println("操作前的list为 " + list);// 在index=1的位置插入一个元素 张无忌list.add(1, "张无忌");System.out.println("插入张无忌之后的list为 " + list);// 在指定位置插入某个集合的所有元素List<String> list1 = new ArrayList<>();list1.add("殷素素");list1.add("张五侠");list.addAll(1, list1);System.out.println("插入list1之后的结果为 " + list);//获取指定位置的元素System.out.println("获取集合中第一个元素: " + list.get(1));//获取集合元素首次出现的位置System.out.println("殷素素首次出现的位置为 " + list.indexOf("殷素素"));list.add("殷素素");//获取集合元素最后出现的位置System.out.println("殷素素最后出现的位置为 " + list.lastIndexOf("殷素素"));// 移除指定位置的元素System.out.println("移除集合中的最后一个元素" + list.remove(5));System.out.println("移除之后的集合为 " + list);// 设置集合的最后元素为: 韦一笑list.set(4, "韦一笑");System.out.println("修改之后的集合为 " + list);// 获取指定范围内的集合System.out.println("集合中1-4的元素集合为 " + list.subList(1, 4));}
}
4.3 List遍历方式
List 的遍历方式有 3 种: ① 迭代器(Iterator) ② 增强for循环 ③ 普通for循环。List 接口对应的实现类 ArrayList、LinkedList 以及 Vector的遍历方式也是上述 3 种。
java">import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;public class ListFor {public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("A");list.add("B");list.add("C");// 方式1:迭代器System.out.println("=======1.迭代器========");Iterator<String> iterator = list.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}//方式2:增强forSystem.out.println("=======2.增强for========");for (String s : list) {System.out.println(s);}//方式3:普通forSystem.out.println("=======3.普通for========");for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}}
}
4.4 ArrayList
4.4.1 概述
ArrayList是实现List接口的动态数组，所谓动态就是它的大小是可变的。实现了所有可选列表操作，并允许包括 null 在内的所有元素。它允许存储重复的元素，有序，支持随机访问，且动态扩容。ArrayList 不是线程安全的，多个线程同时修改需要手动同步。
4.4.2 ArrayList底层结构和源码分析
ArrayList 底层操作机制:
① ArrayList 中维护了一个 Object 类型的数组 elementData
② 当创建 ArrayList 对象时, 如果使用的是无参构造器, 则初始化 elementData 容量为0, 第 1 次添加元素时, 则扩容 elementData 为 10, 如果需要再次扩容, 则扩容当前 elementData 大小的 1.5 倍
③ 如果使用的是指定大小的构造器, 则初始 elementData 容量为指定大小, 如果需要扩容, 则直接扩容当前 elementData 大小的1.5倍
java">import java.util.ArrayList;@SuppressWarnings("all")
public class ArrayListSource {public static void main(String[] args) {ArrayList list = new ArrayList();// ArrayList list = new ArrayList(8);//使用 for 给 list 集合添加 1-10 数据for (int i = 1; i <= 10; i++) {list.add(i);}//使用 for 给 list 集合添加 11-15 数据for (int i = 11; i <= 15; i++) {list.add(i);}list.add(100);list.add(200);list.add(null);}
}
如果使用的是有参构造, 如果初始化容量=0, 创建private static final Object[] EMPTY_ELEMENTDATA = {};, 如果初始容量大于0, 创建初始容量大小的Object数组(this.elementData = new Object[initialCapacity]), 第一次扩容就按照当前 elementData 容量的1.5倍扩容, 后续流程与上述流程一致。
4.5 Vector
4.5.1 概述
java.util.Vector 实现了一个动态数组的数据结构, 能够存储任意类型的对象, 允许存储重复的元素, 也可以存储 null 值。其所有方法都是同步的, 因此线程是安全的。Vector 实现了 List 接口, 提供了列表的所有操作, 如添加、删除、修改、遍历等。由于 Vector 性能相对较低, 同步操作会带来额外的开销, 逐渐被 ArrayList 取代。在开发中, 需要线程同步安全时, 考虑使用 Vetor 。
java"> public synchronized E get(int index) {if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);}
4.5.2 Vector 底层结构和源码剖析
Vector 的底层机制:
- ①
Vector底层维护了一个Object类型的数组 elementData - ② 当创建
Vector对象时, 如果使用的是无参构造器, 则初始化 elementData 容量为10, 如果需要再次扩容, 则扩容当前 elementData 大小的 2 倍 - ③ 如果使用的是指定大小的构造器, 则初始 elementData 容量为指定大小, 如果需要扩容, 则直接扩容当前 elementData 大小的 2 倍
java">import java.util.Vector;@SuppressWarnings("all")
public class VecotrSource {public static void main(String[] args) {Vector vector = new Vector();for (int i = 0; i < 10; i++) {vector.add(i);}vector.add(100);System.out.println("vector=" + vector);}
}
-
① 使用无参构造器
-
- 创建一个大小为10 的Object数组–>elementData
- 创建一个大小为10 的Object数组–>elementData
-
- 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
- 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
-
- 执行添加操作, 其执行过程如下:如果elementData容量够,则直接添加元素,否则进行扩容之后再进行元素的添加。
- 执行添加操作, 其执行过程如下:如果elementData容量够,则直接添加元素,否则进行扩容之后再进行元素的添加。
-
-
② 使用有参构造器
java">import java.util.Vector;@SuppressWarnings("all") public class VecotrSource {public static void main(String[] args) {Vector vector = new Vector(8);for (int i = 0; i < 10; i++) {vector.add(i);}vector.add(100);System.out.println("vector=" + vector);} }-
- 创建一个初始化大小为8的Object数组–>elementData
- 创建一个初始化大小为8的Object数组–>elementData
-
- 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
- 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
-
- 执行添加操作, 其执行过程如下:如果elementData容量够,则直接添加元素,否则进行扩容之后再进行元素的添加。
- 执行添加操作, 其执行过程如下:如果elementData容量够,则直接添加元素,否则进行扩容之后再进行元素的添加。
-
4.6 Vector 和 ArrayList 的比较
| 类名 | 底层结构 | 版本 | 线程安全(同步)效率 | 扩容倍数 |
|---|---|---|---|---|
| ArrayList | 可变数组 | jdk1.2 | 不安全,效率高 | 如果有参构造,扩容1.5倍,如果无参构造,第一次10,第二次以及后续按照1.5倍扩容 |
| Vector | 可变数组 | jdk1.0 | 安全,效率低 | 如果有参构造,扩容2倍,如果无参构造,默认10,满后按照2倍扩容 |
4.7 LinkedList
4.7.1 概述
链表（LinkedList）是一种常见的基础数据结构，是一种线性表，但是不会按线性的顺序存储数据，而是在每一个节点里面存储下一节点的地址。链表可以分为单项列表和双向链表，单向链表包含两个值：当前节点的值和下一节点的链接。一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。下图就是介绍单向链表和双向链表。
Java中的LinkedList 的底层实现了双向链表和双端队列的特点, 可以添加任意元素(可重复),包括null。其线程不安全, 没有实现同步。LinkedList 底层维护了两个属性 first 和 last 分别指向首尾节点, 每个节点(Node对象)维护了 prev[指向前一个] 、next [指向后一个]、item 三个属性。双向链表的示意图见下图。
java"> transient Node<E> first;transient Node<E> last;private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
4.7.2 应用实例
模拟一个简单的双向链表
定义一个Node类, Node 对象 表示双向链表的一个结点
java">public class Node {public Object item; // 数据public Node next; // 指向后一个节点public Node prev; // 指向前一个节点public Node(Object item) {this.item = item;}@Overridepublic String toString() {return "Node name" + item + '}';}
}
模拟双向链表的操作
java">public class LinkedList01 {public static void main(String[] args) {Node jack = new Node("jack");Node tom = new Node("tom");Node siri = new Node("siri");// jack --> tom --> sirijack.next = tom;tom.next = siri;// siri --> tom --> jacksiri.prev = tom;tom.prev = jack;// first 引用 --> jack, 双向链表的头结点Node first = jack;// last 引用 --> siri,双向链表的尾结点Node last = siri;// 从头到尾遍历System.out.println("======从头到尾遍历=======");while (true) {if (first == null) {break;}// 输出 first信息System.out.println(first);first = first.next;}// 从尾到头遍历System.out.println("=======从尾到头遍历=========");while (true) {if (last == null) {break;}//输出 last信息System.out.println(last);last = last.prev;}System.out.println("=======向链表中添加节点smith=======");// jack-->tom-->smith-->siriNode smith = new Node("smith");smith.next = siri;smith.prev = tom;tom.next = smith;siri.prev = smith;System.out.println("=======添加成功==========");System.out.println("===从头到尾进行遍历===");// 让 first 引用指向 jack,就是双向链表的头结点first = jack;while (true) {if (first == null) {break;}//输出 first 信息System.out.println(first);first = first.next;}last = siri; //让 last 重新指向最后一个结点System.out.println("====从尾到头的遍历====");while (true) {if (last == null) {break;}//输出 last 信息System.out.println(last);last=last.prev;}}
}
增加元素的图解:
4.7.3 LinkedList底层结构和源码剖析
1.添加元素
java">import java.util.LinkedList;@SuppressWarnings("all")
public class LinkedListSource {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);System.out.println("linkedList=" + linkedList);}
}
尾插法[每次添加元素都是last节点移动,并指向最新插入的元素]的核心代码:
java"> void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}
插入第一个元素的图解:
插入第二个元素图解:
2.移除元素
remove 不带参数的移除方法就是移除集合中 first 节点指向的元素，并且 first 顺延指向下一个元素。主要功能还是 unlinkFirst 方法，将 first 头指针指向下一个元素，并将要移除的元素置空。
java">import java.util.LinkedList;@SuppressWarnings("all")
public class LinkedListSource {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);System.out.println("linkedList=" + linkedList);//演示一个删除结点的linkedList.remove(); // 这里默认删除的是第一个结点System.out.println("linkedList=" + linkedList);}
}
java">import java.util.LinkedList;@SuppressWarnings("all")
public class LinkedListSource {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);System.out.println("linkedList=" + linkedList);//演示一个删除结点的linkedList.remove(1); // 这里默认删除的是第一个结点System.out.println("linkedList=" + linkedList);}
}
结合源码, 根据下标移除元素的逻辑主要是实现以下步骤:
- ① 检查下标是否在 size 范围内；
- ② 根据下标，找到移除的节点；
- ③ 将节点移除链表，并将链表的前驱指针和后驱指针链接正确。
4.8 ArrayList 和 LinkedList 比较
| 类名 | 底层结构 | 增删效率 | 改查效率 |
|---|---|---|---|
| ArrayList | 可变数组 | 较低,数组扩容 | 较高 |
| LinkedList | 双向链表 | 较高,通过链表追加 | 较低 |
如何选择
ArrayList和LinkedList?① 如果改查的操作多, 选择
ArrayList, 如果增删的操作多, 选择LinkedList。② 一般来说, 在程序中80%-90%的场景都是查询, 因此大部分情况下会选择
ArrayList③ 在项目中也可以根据实际的业务场景来选择
ArrayList和LinkedList。
9. Set 接口和常用方法
9.1 概述
在 Java 集合框架中, Set是一种非常重要的接口, 它继承自 Collection 接口。与 List 和 Queue 不同, Set不允许存储重复元素, 并且没有特定的顺序(除非使用LinkedHashSet或者TreeSet)。Set 集合支持的遍历方式和 Collection 集合一样：foreach(增强for)和Iterator(迭代器)。Set接口的特点: 唯一性、无序性、空集合。Set 的常用实现类有：HashSet、TreeSet、LinkedHashSet。
java">import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {Set set = new HashSet();set.add("john");set.add("lucy");set.add("jack");set.add("hsp");set.add("mary");set.add(null);// 1. 使用迭代器遍历System.out.println("=====使用迭代器====");Iterator iterator = set.iterator();while (iterator.hasNext()) {Object obj = iterator.next();System.out.println("obj=" + obj);}// 2.使用增强 forSystem.out.println("=====增强 for====");for (Object o : set) {System.out.println("o=" + o);}}
}
/**
=====使用迭代器====
obj=null
obj=hsp
obj=mary
obj=john
obj=lucy
obj=jack
=====增强 for====
o=null
o=hsp
o=mary
o=john
o=lucy
o=jack
*/
9.2 HashSet
9.2.1 概述
HashSet 是 Set 接口典型实现，它按照 Hash 算法 来存储集合中的元素，具有很好的存取和查找性能。底层数据结构是哈希表。哈希表即一个元素为链表的数组，综合了数组与链表的优点。HashSet主要具有以下特点：
- 不保证set的迭代顺序
- HashSet不是同步的，如果多个线程同时访问一个HashSet，要通过代码来保证其同步
- 集合元素值可以是null，但只能有一个null
9.2.2 HashSet 底层结构与源码剖析
1.源码剖析
HashSet 内部其实是基于 HashMap 的，使用 map 来完成 put 操作，value 需要自定义；而在 HashSet中，value 是常量（一个 Object 对象）。
java">import java.util.HashSet;
import java.util.Set;@SuppressWarnings({"all"})
public class HashSet1 {public static void main(String[] args) {Set hashSet = new HashSet();hashSet.add(null);hashSet.add(null);System.out.println("hashSet=" + hashSet);}
}
① 创建空集合,底层是通过 HashMap 实现。调用 HashSet 的无参构造
java"> // Set hashSet = new HashSet(); 底层源码如下:static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();/*** Constructs a new, empty set; the backing HashMap instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() {map = new HashMap<>();}
===================================HashMap==============================================private static final long serialVersionUID = 362498820763181265L;static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;/*** Constructs an empty HashMap with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
② 向集合中添加元素 null, PRESENT 是一个 Object 对象。如果是添加其他类型的数据, 首先会进行自动装箱操作,随后调用 put方法, 返回 true 或者 false 表明元素是否添加成功。
java"> /*** Adds the specified element to this set if it is not already present.* More formally, adds the specified element e to this set if this set contains no * element e2 such that(e==null ? e2==null:e.equals(e2)).* If this set already contains the element, the call leaves the set unchanged and * returns false.** @param e element to be added to this set* @return true if this set did not already contain the specified* element* PRESENT此处在put函数中就是充当一个占位的作用，并无实际意义。*/public boolean add(E e) {// nullreturn map.put(e, PRESENT)==null; // put方法返回null说明元素已经插入成功}/*** Associates the specified value with the specified key in this map.* If the map previously contained a mapping for the key, the old* value is replaced.** @param key key with which the specified value is to be associated* @param value value to be associated with the specified key* @return the previous value associated with key, or null if there was no mapping for key.* (A null return can also indicate that the map previously associated null with key.)*/public V put(K key, V value) { // 此时 key = null value=Object@522return putVal(hash(key), key, value, false, true); // key = null value=Object@522}// 返回当前元素对应的哈希值static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}===================================field=================================================/*** The table, initialized on first use, and resized as necessary. When allocated, * length is always a power of two.(We also tolerate length zero in some operations * to allow bootstrapping mechanics that are currently not needed.)*/transient Node<K,V>[] table;/*** Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and * values().*/transient Set<Map.Entry<K,V>> entrySet;/*** The number of key-value mappings contained in this map.*/transient int size;/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash). This field is used to make iterators on Collection-views of* the HashMap fail-fast. (See ConcurrentModificationException).*/transient int modCount;/*** The next size value at which to resize (capacity * load factor).** @serial*/// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)int threshold;/*** The load factor for the hash table.** @serial*/final float loadFactor;/*** 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) {// hash:0 key:null value:Object@522,onlyIfAbsent:false,evict:true// 定义辅助变量 tab是Node类型的数组，而p只是个Node类型的引用Node<K,V>[] tab; Node<K,V> p; int n, i; // tab = HashMap$Node[16]@555, n=16(新数组的长度,其所有元素均为null),i=0// 短路或的逻辑运算符(只要满足第一个条件就进入if语句) table是HashMap中一个Node类型的数组，并且没有显式初始化，默认为空引用null 。if ((tab = table) == null || (n = tab.length) == 0)// 猜测，resize函数的返回值是一个节点类型（Node类型）的数组。n = (tab = resize()).length;// 将tab中的一个特定元素赋值给p,再判断p是否为空,其实就是判断tab数组某个索引处的元素是否为空。// hash=0,tab=HashMap$Node[16]@555,n=16,即为 p=tab[15&0]=tab[0]=null,所以进入if条件if ((p = tab[i = (n - 1) & hash]) == null)// 此时 tab[0]=newNode(0,null,Object@522,null),存储hash值方便再次插入时,进行判断。// Node<K,V> newNode(int hash, K key, V value, Node<K,V> next)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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold) // 当前数组的大小是否大于12,判断是否需要扩容resize();afterNodeInsertion(evict);return null;}=========================================================================================// 以下为 resize方法源码/*** Initializes or doubles table size. If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** @return the table*/final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 此时 oldTab = nullint oldCap = (oldTab == null) ? 0 : oldTab.length; // 此时oldCap = 0int oldThr = threshold; // 此时 threshold = 0 即 oldThr = 0int newCap, newThr = 0;// 下面的判断直接进入 else分支 if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaults// 给 newCap,newThr 赋值// newCap 顾名思义 newCapacity，表示新数组的容量 赋值为大小等于 16 的静态常量newCap = DEFAULT_INITIAL_CAPACITY;// newThr，顾名思义，newThreshold，表示临界值,其值=0.75*16 = 12newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {//此时不满足条件,跳过float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;// 此时 其值=12@SuppressWarnings({"rawtypes","unchecked"})//将长度为16的Node类型的新数组的地址赋给了newTab引用，并由newTab引用传递给table，到此，table已经由null变为了长度为16的数组，Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) { //此时 oldTab = null ,不进入if条件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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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; // 返回 newTab:HashMap$Node[16]@555}
Q: 所谓的临界值"Threshold"到底有什么用？
① Threshold是门槛的意思，是java设计者提供的一个临界值。
② 临界值 = （向下转型) 增长因子 * 默认初始容量 = 0.75 * 16 = 12
③ 为了尽可能防止线程阻塞情况的发生。如果一直到table数组满16才扩容，当数组可用空间已经不多时，假如这时候有许多线程同时向集合中添加元素，就可能因为扩容不及时造成阻塞。假如数组已添加了12个元素，到达临界值，数组就要准备开始扩容，未雨绸缪，就不容易发生阻塞，即起到一个缓冲的作用。
在向tab数组中插入元素后, putVal方法执行完毕, modCount记录修改次数的变量, if语句是判断当前集合中元素的个数是否超过临界值, 如果超过临界值就准备对数组再次进行扩容。最终返回 null表示插入元素成功了。
③ 当再次向集合中添加元素 null 值时, 元素 null是重复元素, 在底层肯定会被’干掉’。当前只分析 putVal 方法的执行过程。
java">final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// hash=0,key=null,value=Object@522,onlyIfAbsent=fasle,evict=true// tab=HasgMap$Node[16]@555 p="null=java.lang.Object@7b1d7fff",n=16,i=0Node<K,V>[] tab; Node<K,V> p; int n, ;)//table=HasgMap$Node[16]@555,此时集合不为null,不进入if条件 if ((tab = table) == null || (n = tab.length) == 0n = (tab = resize()).length;//此时对应位置的地址不为null[元素值为null],故也不进入该分支,进入else分支if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 当添加相同元素时,else分支有3种情况// k:null 此时 hash = 0Node<K,V> e; K k;// 情况1:// 1. tab数组该索引处的元素哈希值 == 当前元素哈希值相等的情况下满足下面两个条件之一即可// 2.1 当前元素的值和tab数组该索引处的元素的值相等（或者是同一个对象）// 2.2 当前元素和该索引处的元素不是同一个对象；但是当前元素不为空，并且其内容与数组该索引处的元素的内容相等,此时满足条件,直接放弃添加元素。if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))e = p;//情况2: 判断 p 是不是一棵红黑树, 如果是一棵红黑树, 调用putTreeVal方法添加元素else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//情况3: 如果tab对应索引位置已经是一个链表, 使用for循环比较。for (int binCount = 0; ; ++binCount) {// 1) 依次和该链表的每个元素比较后,都不相同,则加入到该链表的最后if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 把元素添加到链表后，立即判断 该链表是否已经达到 8 个节点if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// treeifyBin() 对当前链表进行树化(转成红黑树),在转化时还需要满足其他条件treeifyBin(tab, hash);break;}// 2) 依次和该链表的每个元素比较的过程中,如果有相同的情况,就直接breakif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 此时,e不等于 "null=java.lang.Object@7b1d7fff"if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent:faslee.value = value;afterNodeAccess(e);return oldValue;// 此时返回值为 Object@522}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
2.小结
-
①
HashSet的底层是调用了HashMap, 而HashMap的底层是 “数组+链表+红黑树” 的结构。简言之: 数组的元素是一个链表, 并且在某些条件下将链表树转化为红黑树。 -
② 当向
HashSet集合中添加一个元素时, 会先得到该数据的hash值(哈希值), 然后在底层将它转化为一个索引值[索引值会决定元素在集合中的存储位置]。 -
③ 当索引值对应的位置没有元素存在时, 直接将当前元素加入集合。反之, 则调用
equals方法(该方法由程序员控制)进行判断, 如果当前要添加的元素与该位置处的元素相等, 放弃添加该元素。如果当前要添加的元素与该位置处的元素不相等, 则将该元素添加(挂在)到该位置处元素的最后面。如下图所示, 便实现了 “数组+链表” 的结构。
- ④ 在 Java8 中, 如果一条链表的元素个数达到或超过了TREEIFY_THRESHOLD（默认是8），并且table数组的长度达到或超过了MIN_TREEIFY_CAPACITY（默认是64），底层就会对该链表进行树化，将其转化为一棵红黑树；否则仍采用[数组扩容]机制。
- ⑤ 第一次向集合中添加元素时，底层的table数组会扩容到16，临界值(threshold) = 16 * 0.75 = 12； 临界值的存在是为了对扩容起到一个缓冲的效果。当数组中元素的个数达到临界值12后，会对数组进行第二次扩容，16 * 2 = 32，此时临界值 = 32 * 0.75 = 24；当数组中元素的个数达到24后会进行第三次扩容，32 * 2 = 64，此时临界值 = 64 * 0.75 = 48，依次类推。
9.2.3 应用实例
需求:定义一个Employee类, 该类包含: private 成员属性: name 和 age, 要求:
① 创建 3 个 Employee 对象, 添加到 HashSet中
② 当 name 和 age 相同时, 认为是相同员工, 不能添加到 HashSet中
java">import java.util.HashSet;
import java.util.Objects;@SuppressWarnings({"all"})
public class HashSetExercise {public static void main(String[] args) {HashSet hashSet = new HashSet();hashSet.add(new Employee("milan", 18));hashSet.add(new Employee("tom", 28));hashSet.add(new Employee("milan", 18));System.out.println("hashset=" + hashSet);}
}class Employee {private String name;private int age;public Employee() {}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 int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "Employee{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic 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 && Objects.equals(name, employee.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}
}
9.3 LinkedHashSet
9.3.1 概述
java.util.LinkedHashSet 是 HashSet 的子类, 而由于 HashSet 实现了 Set 接口，因此 LinkedHashSet 也间接实现了 Set 接口。LinkedHashSet 底层是一个 LinkedHashMap，是“数组 + 双向链表” 的结构。LinkedHashSet也具有Set集合"不可重复"的特点。但由于LinkedHashSet根据元素的哈希值来决定元素的存储位置，同时使用双向链表来维护元素的次序，这就使得元素看起来是以插入顺序保存的。
9.3.2 LinkedHashSet 底层结构和源码剖析
1.源码剖析
示例代码:
java">import java.util.LinkedHashSet;@SuppressWarnings({"all"})
public class LinkedHashSet1 {public static void main(String[] args) {LinkedHashSet linkedHashSet = new LinkedHashSet();linkedHashSet.add(141);linkedHashSet.add("CSDN");linkedHashSet.add(141);linkedHashSet.add(11);linkedHashSet.add("51CTO");linkedHashSet.add(new Phone("小米"));linkedHashSet.add(new Phone("三星"));System.out.println("linkedHashSet= " + linkedHashSet);}
}
① 创建 LinkedHashSet 对象, 最终底层创建了一个 LinkedHashMap 类型的 map 对象。
java">// 调用 LinkedHashSet 的无参构造器
LinkedHashSet linkedHashSet = new LinkedHashSet();// 1) 调用 LinkedHashSet 的无参构造器
public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {public LinkedHashSet() {// 调用父类 HashSet 的带参构造器super(16, .75f, true);}
}// 2) 调用父类的带参构造器
public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{private transient HashMap<E,Object> map;private static final Object PRESENT = new Object();HashSet(int initialCapacity, float loadFactor, boolean dummy) {// 带参传过来的// 调用LinkedHashMap的带参构造器。（LinkedHashMap是HashMap的子类，此处构成“多态”）map = new LinkedHashMap<>(initialCapacity, loadFactor);}
}// 3) 调用LinkedHashMap的带参构造器
public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}transient LinkedHashMap.Entry<K,V> head;transient LinkedHashMap.Entry<K,V> tail;public LinkedHashMap(int initialCapacity, float loadFactor) {// 调用父类HashMap的带参构造器super(initialCapacity, loadFactor);accessOrder = false;}
}// 4) 调用父类HashMap的带参构造器
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;static final int tableSizeFor(int cap) {//16int n = cap - 1; // n=15n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0) // initialCapacity=16,throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)// 2^30initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;// 0.75this.threshold = tableSizeFor(initialCapacity); // threshold=16}
}
此时LinkedHashSet的属性如下图:
② 加入第一个元素 String 类型的 “CSDN”,最终 Hashmap中的put方法返回 null值, 表明元素已经插入成功。其中底层最终是调用的 HashMap 中的 putVal方法。 如下图所示:
java">linkedHashSet.add(new String("CSDN"));//1) 调用 HashSet 中的 add 方法
public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{private transient HashMap<E,Object> map;public boolean add(E e) {// 调用 HashMap中的put方法return map.put(e, PRESENT)==null;}
}// 2) 调用 HashMap中的put方法
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;public V put(K key, V value) {// 调用 HashMap中的putVal方法// hash(key):获取当前插入元素的哈希值return putVal(hash(key), key, value, false, true);}// 3) 调用 HashMap中的putVal方法final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 第一次插入元素时, tab = nullif ((tab = table) == null || (n = tab.length) == 0)// resize()方法返回一个Node类型的数组给tab数组n = (tab = resize()).length;// 1.根据当前元素的哈希值,然后通过特定的算法,获得当前元素在table数组中应该存放的位置的索引值if ((p = tab[i = (n - 1) & hash]) == null)// 1.1 如果table数组该索引处为空，就直接放进去(调用LinkedHashMap中的带参构造方法)tab[i] = newNode(hash, key, value, null);else {// 1.2 如果table数组该索引处不为空,取链表中一一判断Node<K,V> e; K k;//情况1://1. tab数组该索引处的元素哈希值 == 当前元素哈希值相等的情况下满足下面两个条件之一即可// 2.1 当前元素的值和tab数组该索引处的元素的值相等（或者是同一个对象）// 2.2 当前元素和该索引处的元素不是同一个对象；但是当前元素不为空，并且其内容与数组该索引处的元素的内容相等,此时满足条件,直接放弃添加元素。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//情况2:判断 p 是不是一棵红黑树, 如果是一棵红黑树, 调用putTreeVal方法添加元素else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//情况3: 如果tab对应索引位置已经是一个链表, 使用for循环比较。for (int binCount = 0; ; ++binCount) {// 1) 依次和该链表的每个元素比较厚,均不同,则加入到该链表的最后if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 把元素加入到链表后,立即判断该链表的元素是否已经达到8个节点if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 通过treeifyBin方法将链表转换为红黑树treeifyBin(tab, hash);break;}// 2) 依次和该链表的每个元素比较的过程中,如果有相同的情况,就直接breakif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
} =========================================================================================
// HashMap中的resize方法源码, threshold的值在初始化LinkedHashSet时,通过HashMap中的tableSizeFor方法修改final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // oldTab = nullint oldCap = (oldTab == null) ? 0 : oldTab.length; // oldTab=null,则oldCap=0int oldThr = threshold; // threshold=16int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//此时代码执行到 else-if 分支 此时 oldThr = 16,此时newCap = 16else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12}// 此时 newThr = 0if (newThr == 0) {float ft = (float)newCap * loadFactor;// 16 * 0.75=12newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);// 执行完该语句后,newThr=12}threshold = newThr; // 12@SuppressWarnings({"rawtypes","unchecked"})// 创建长度为16的数组，并最终将table属性初始化Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// table = null// 接下来不进入if条件语句,直接返回newTabif (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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}
=========================================================================================
// 4) 调用LinkedHashMap中的带参构造方法
public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}// table数组仍然是Node类型（LinkedHashMap的静态内部类），但是里面保存的元素却成了Entry类型（LinkedHashMap的内部类）。==> 多态数组Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);// 调用LinkedHashMap中的linkNodeLast方法linkNodeLast(p);return p;}// 5) 调用LinkedHashMap中的linkNodeLast方法private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}}
} 执行完 resize 方法后,返回的 newTab 对象
③ 当第一个元素插入成功后,插入第二个元素 141, 此时 table 的大小为 16, 索引为 5 的位置存放的是 “CSDN”。最终 put 方法返回 null, 说明元素插入成功。
源码执行过程如下:
java">// 1) 自动装箱public static Integer valueOf(int i) {if (i >= IntegerCache.low && i <= IntegerCache.high)return IntegerCache.cache[i + (-IntegerCache.low)];return new Integer(i);}//2) 调用 HashSet 中的add()方法
public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{private transient HashMap<E,Object> map;private static final Object PRESENT = new Object();public boolean add(E e) {// 调用 HashMap中的 put方法return map.put(e, PRESENT)==null;}
}//3) 调用 HashMap中的 put方法
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {public V put(K key, V value) {// 调用 HashMap中的 putVal方法return putVal(hash(key), key, value, false, true);}// 4) 调用 HashMap中的 putVal方法final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 如下if条件不满足, 不进入该部分if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 满足如下if条件,创建新节点,将141插入table中if ((p = tab[i = (n - 1) & hash]) == null)// 调用 LinkedHashMap的带参构造方法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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
}// 5) 调用 LinkedHashMap的带参构造方法
public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{ // 静态内部类static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {// 1.调用父类 HashMap 的带参构造方法super(hash, key, value, next);}}Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);// 2.调用LinkedHashMap中的linkNodeLast()方法linkNodeLast(p);return p;}//7) 调用LinkedHashMap中的linkNodeLast()方法private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}}
}// 6) 调用父类 HashMap 的带参构造方法
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}
}
最终结果如下图:
④ 插入重复元素 141时,底层与 HashSet的流程一致, 无法插入。代码执行的是else分支中的情况1, 当前插入元素与对应索引处的元素相同, 最终返回的结果为 oldValue, 表名元素未插入。
2.小结
-
①
LinkedHashSet在底层会用到一个 HashMap$Node[]类型的table表（Node类是HashMap中维护的一个静态内部类），与HashSet相同, 该table表即用来存储元素(在通过add方法添加元素时，底层调用HashMap的put方法)。table的属性被HashMap类维护，无论HashSet还是LinkedHashSet，需要先访问到HashMap。HashSet中维护了一个 HashMap<E,Object>类型的map属性，而HashSet构造器中对该map属性进行初始化，LinkedHashSet的构造器中，使用多态的方式, 两者均是借助该map对象即可访问到HashMap中的table属性。java">public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { /*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*/transient Node<K,V>[] table }public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{private transient HashMap<E,Object> map;/*** Constructs a new, empty set; the backing HashMap instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() {map = new HashMap<>();} }===============================LinkHashSet创建过程================================= public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {public LinkedHashSet() {super(16, .75f, true);} }public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);} }public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;} }public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);} } -
②
LinkedHashSet通过head和tail维护了一个双向链表（本质上是LinkedHashMap中的两个属性），此处Entry是LinkedHashMap的一个静态内部类。LinkedHashMap$Entry类维护before[指向前一个节点] 和after[指向后一个节点] 属性, 形成双向链表。java">public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{/*** HashMap.Node subclass for normal LinkedHashMap entries.*/static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}/*** The head (eldest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> tail; } -
③
LinkedHashSet在添加元素时，先求该元素的hash值，根据特定算法求得该元素在table中应该存放的位置。如果该位置已经有相同元素，放弃添加；反之则将该元素加入到双向链表。 -
④
LinkedHashSet的底层机制图:java">import java.util.LinkedHashSet;@SuppressWarnings({"all"}) public class LinkedHashSet1 {public static void main(String[] args) {LinkedHashSet linkedHashSet = new LinkedHashSet();linkedHashSet.add(141);linkedHashSet.add("CSDN");linkedHashSet.add(141);linkedHashSet.add(11);linkedHashSet.add("51CTO");linkedHashSet.add(new Phone("小米"));linkedHashSet.add(new Phone("三星"));System.out.println("linkedHashSet= " + linkedHashSet);} }class Phone {private String name;public Phone(String name) {this.name = name;}@Overridepublic String toString() {return "Phone{" +"name='" + name + '\'' +'}';}@Overridepublic int hashCode() {return 100;} }上述代码的机制图:
9.3.3 应用实例
需求: 定义 Car 类, 包含private属性 name 和 price, 如果 name 和 price 一样, 则认为是相同元素, 就不能添加。
java">package JavaBase.hashset1;import java.util.LinkedHashSet;
import java.util.Objects;@SuppressWarnings({"all"})
public class LinkedHashSetExercise {public static void main(String[] args) {LinkedHashSet linkedHashSet = new LinkedHashSet();linkedHashSet.add(new Car("奥拓", 1000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//OKlinkedHashSet.add(new Car("法拉利", 10000000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//加入不了linkedHashSet.add(new Car("保时捷", 70000000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//加入不了System.out.println("linkedHashSet=" + linkedHashSet);}
}class Car{private String name;private int price;public Car() {}public Car(String name, int price) {this.name = name;this.price = price;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getPrice() {return price;}public void setPrice(int price) {this.price = price;}@Overridepublic String toString() {return "Car{" +"name='" + name + '\'' +", price=" + price +'}';}//重写 equals 方法 和 hashCode//当 name 和 price 相同时， 就返回相同的 hashCode 值, equals 返回 true@Overridepublic 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 && Objects.equals(name, car.name);}@Overridepublic int hashCode() {return Objects.hash(name, price);}
}
/**
linkedHashSet=[Car{name='奥拓', price=1000}, Car{name='奥迪', price=300000}, Car{name='法拉利', price=10000000}, Car{name='保时捷', price=70000000}]
*/
10.Map 接口和常用方法
10.1 概述
Map 与 Collection 并列存在。用于保存具有映射关系的数据:Key-Value(双列元素)。Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中。Map 中的 key 不允许重复，但是 value 可以重复。Map 的 key 可以为 null(只能有一个), value 也可以为 null (可有多个)。key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value。
10.2 Map 接口的常用方法
| 方法 | 描述 |
|---|---|
| V get(Object key) | 返回 key 对应的 value |
| V getOrDefault(Object key, V defaultValue) | 返回 key 对应的 value，key 不存在，返回默认值 |
| V put(K key, V value) | 设置 key 对应的 value |
| V remove(Object key) | 删除 key 对应的映射关系 |
| Set keySet() | 返回所有 key 的不重复集合 |
| Collection values() | 返回所有 value 的可重复集合 |
| Set<Map.Entry<K, V>> entrySet() | 返回所有的 key-value 映射关系 |
| boolean containsKey(Object key) | 判断是否包含 key |
| boolean containsValue(Object value) | 判断是否包含 value |
| int size() | 返回元素个数 |
| void clear() | 根据键删除映射关系 |
使用示例
java">import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Collection;public class MapMethodsExample {public static void main(String[] args) {// 创建一个 HashMap 实例Map<String, Integer> map = new HashMap<>();// 设置 key 对应的 valuemap.put("apple", 1);map.put("banana", 2);map.put("orange", 3);// 返回 key 对应的 valueInteger appleValue = map.get("apple");System.out.println("Value for 'apple': " + appleValue);// 返回 key 对应的 value，key 不存在，返回默认值Integer mangoValue = map.getOrDefault("mango", 0);System.out.println("Value for 'mango': " + mangoValue);// 删除 key 对应的映射关系Integer removedValue = map.remove("banana");System.out.println("Removed value for 'banana': " + removedValue);System.out.println("Map after removing 'banana': " + map);// 返回所有 key 的不重复集合Set<String> keys = map.keySet();System.out.println("Keys: " + keys);// 返回所有 value 的可重复集合Collection<Integer> values = map.values();System.out.println("Values: " + values);// 返回所有的 key-value 映射关系Set<Map.Entry<String, Integer>> entries = map.entrySet();System.out.println("Entries: " + entries);// 判断是否包含 keyboolean containsApple = map.containsKey("apple");System.out.println("Contains key 'apple': " + containsApple);// 判断是否包含 valueboolean containsValue2 = map.containsValue(2);System.out.println("Contains value 2: " + containsValue2);}
}
10.3 Map的遍历方式
首先我们需要把 map 转换为 set 进行遍历，可使用 entrySet 和 keySet 共2种方式进行转换。每一种情况都可以使用 迭代器iterator()遍历；增强for循环遍历；forEach+lambda循环遍历，将循环简化。
java">import java.util.*;public class MapFor {public static void main(String[] args) {Map<String,String> map = new HashMap<String,String>();map.put("邓超", "孙俪");map.put("王宝强", "马蓉");map.put("宋喆", "马蓉");map.put("刘令博", null);map.put(null, "刘亦菲");map.put("鹿晗", "关晓彤");System.out.println("=================方式1:以键取值=========================");//方式1: 先取出 所有的 Key , 通过 Key 取出对应的 ValueSet<String> keySet = map.keySet();// ① 增强 forSystem.out.println("-----第一种方式-------");for (String key : keySet) {System.out.println(key + "-" + map.get(key));}// ② 迭代器System.out.println("----第二种方式--------");Iterator<String> iterator = keySet.iterator();while (iterator.hasNext()) {String key = iterator.next();System.out.println(key + "-" + map.get(key));}System.out.println("=================方式2:获取值=========================");// 方式2:获取所有的valueCollection<String> values = map.values();System.out.println("---取出所有的 value 增强 for----");// ① 增强 for循环for (String value : values) {System.out.println(value);}//② 迭代器System.out.println("---取出所有的 value 迭代器----");Iterator<String> iterator1 = values.iterator();while (iterator1.hasNext()){System.out.println(iterator1.next());}//方式3: 通过 EntrySet 来获取 k-vSystem.out.println("=================方式3:EntrySet方式=========================");Set<Map.Entry<String,String>> entrySet = map.entrySet();// ① 增强forSystem.out.println("----使用 EntrySet 的 for 增强(第 3 种)----");for (Map.Entry<String,String> entry : entrySet) {System.out.println(entry.getKey() + "-" + entry.getValue());}// ② 迭代器System.out.println("----使用 EntrySet 的 迭代器(第 4 种)----");Iterator<Map.Entry<String, String>> iterator2 = entrySet.iterator();while (iterator2.hasNext()) {Map.Entry<String,String> entry = iterator2.next();System.out.println(entry.getKey() + "-" + entry.getValue());}System.out.println("=================方式4:Lambda表达式=========================");map.forEach((key,value)->{System.out.println(key + "-" + value);});}
}
10.3 HashMap
10.3.1 概述
java.util.HashMap是 Map集合体系中使用频率最高的一个实现类。Map 接口常用的实现类 HashMap、Hashtable 和 Properties。HashMap 是以 key -value 对的方式存储数据。 key 不能重复, 但是 value可以重复, 允许 null 键和 null 值。如果添加相同的 key, 则会覆盖原来的 key-value对,等同于修改。与 HashSet 相同的是, 不保证映射顺序, 因为底层是以 hash表的方式存储。HashMap没有实现同步, 因此线程是不安全的, 方法没有做互斥的操作, 没有 synchronized。
10.3.2 HashMap底层机制与源码实现
示例代码:
java">import java.util.HashMap;@SuppressWarnings({"all"})
public class HashMapSource {public static void main(String[] args) {HashMap map = new HashMap<>();map.put("CSDN", "NB");map.put("xiaohu", "Rain");map.put("CSDN", "YYDS");System.out.println(map);}
}
1.源码剖析
① 创建 HashMap 对象，跳入 HashMap 的无参构造器。此时将loadFactor（加载因子）初始为了0.75。初始完构造器后, 可以看到 HashMap$Node[] table = null; 。
java">public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {// 跳入 HashMap 的无参构造器public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
}
② [第一次插入元素] 执行 put 调用 hash 方法，计算 key 的 hash 值 (h = key.hashCode()) ^ (h >>> 16)。
此时可看到, IDEA的提示信息中, key = “CSDN”；并且value值不再是在 HashSet 源码分析中见到的那个PRESENT了，而是"NB"。 put 方法的内部又调用了putVal方法，并且传入了5个实参 —— ① hash 方法的返回值；② 键值对中的 key；③键值对中的 value；④ false（传递给 onlyIfAbsent）；⑤ true（传递给evict）。
hash方法的本质就是根据一个算法来返回键值对中key对应的哈希值。此处key显然不为null，因此会返回三目运算符的"(h = key.hashCode()) ^ (h >>> 16)"部分。
③ [第一次插入元素] 执行 putVal 方法, 此时 table 为空, 需要对 数组进行扩容操作, 即 resize()方法
java">final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}================================第一次数组扩容=========================================
// 对数组第一次扩容,数组大小为 16, 执行成功后, 返回新数组(大小为16)
final Node<K,V>[] resize() {// oldTab，见名知意，oldTableNode<K,V>[] oldTab = table;// oldCap见名知意，oldCapacityint oldCap = (oldTab == null) ? 0 : oldTab.length;// 此时 threshold = 0 oldThr，见名知意，oldThresholdint oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 此时代码进入else分支else { // zero initial threshold signifies using defaults// newCap变量初始化为了16，并且将newThr变量初始化为了16 * 0.75 = 12newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 此时 threshold = 12threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})// 创建大小为16的数组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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}
④ [第一次插入元素] 回到 putVal 方法, 执行完 resize 方法, 返回大小为 16 的数组, 继续往下执行代码。 if条件语句中，利用获取到的key的哈希值，根据特定算法可以得到一个索引值i，该索引之当前键值对在table数组中应该存放的位置。显然，此处p不为空，所以会直接将当前键值对包装成Node类型，然后加入到table数组该索引处。
java">final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)// 此时 n = 16n = (tab = resize()).length;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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
⑤ 返回演示类,可以看到第一个键值对"CSDN"-"NB"已成功加入到了table数组中, 如下图:
[第二次插入元素] 第二个键值对的key = “Cyan”，它的哈希值肯定与第一个键值对的key（“CSDN”）不同。因此，第二个元素的添加过程与第一个元素一样, 在处就不具体演示, 插入后见下图:
⑥ [第三次插入元素] 此时插入相同key的元素 可以看到， 此时key = “CSDN”，value = “YYDS”。key相同，hash方法返回的哈希值就一定相同。此时直接进入 putVal 方法。此时进入最外层的 else 分支。此时分为三种情况:
- ① 如果table数组该索引处元素的
key与当前元素的key相同，就放弃添加当前键值对。 - ② 如果该索引处元素的
key与当前元素的key不相同，并且该索引处元素后面跟着的是一棵红黑树，就采用红黑树的方法进行元素的添加。 - ③ 在不满足前面两种情况的基础上，如果该索引处元素的后面跟着的是一个链表，就要对链表中的元素挨个进行判断，只要链表中的元素出现了与当前元素
key相同的情况，就立刻break出去，放弃添加当前元素。
java">final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 此时代码执行到该部分, 此时满足上述的情况1:放弃添加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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)//进行了值的替换，将table数组该索引出的键值对的旧值替换为了当前键值对的新值e.value = value;afterNodeAccess(e);// 返回旧的值return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
⑦ [第三次插入元素] 完成 value 值的替换, 返回演示类, 见下图最终结果。
2.小结
-
①
HashMap底层维护了Node类型的数组table，默认为null。HashMap的底层是“数组 + 链表 + 红黑树”的结构。简单来说，即table数组的元素是一个链表，并且在某些条件下会将链表树化为红黑树。如下图所示 :
-
② 当创建
HashMap对象时，会将加载因子（loadFactor）初始化为0.75。 -
③ 当向
table数组中添加一个key-value键值对时，会先根据当前键值对的key得到一个该键值对的hash值(哈希值)，然后在底层将它转化为一个索引值。这个索引值决定该元素在table数组中应该存放的位置。 -
④ 当（table数组中）索引值对应的位置没有元素存在时，直接将当前元素（键值对）加入table数组。
反之，则进行判断，如果当前要添加的键值对的
key与该位置处的键值对的key判断为相等，放弃添加该元素，并用新的value值替换掉key对应的旧的value值，返回旧值；如果当前元素的key与已存在元素的key不相等，则继续判断table数组该索引处的元素后面跟着的是一个链表还是一棵红黑树。 -
⑤ 若判断
table数组该索引处的元素是一个链表，则继续判断该链表中的元素有无与当前元素相同的key，若有——放弃添加该key-value键值对，用新的value值替换对应旧的value值，并返回旧值；若无——直接将当前键值对挂载到当前链表的最后面（实现了数组 + 链表的结构）。若判断
table数组该索引处的元素是一棵红黑树，则用红黑树的方法去添加元素。 -
⑥ 第一次向
HashMap集合中添加元素时，底层的table数组会扩容到16，临界值(threshold) = 16 * 0.75 = 12；之后每当table数组中的元素超过临界值时，就要对table数组进行扩容，容量和临界值都扩大2倍，以此类推。 -
⑦ 在JDK17.0版本中，如果
table数组中某一条链表的元素个数达到或超过了TREEIFY_THRESHOLD（默认是8），并且table数组的长度达到或超过了MIN_TREEIFY_CAPACITY（默认是64），底层就会对该链表进行树化，将其转化为一棵红黑树；否则仍采用数组扩容机制。（JDK8.0同）
3. HashMap 树化触发机制
HashMap底层链表转换为红黑树的条件——① table数组的某索引处的链表中，元素的个数达到或超过8个；② table数组本身的长度达到或超过64个。
对于第② 个条件比较简单，table数组在初始化后，长度 = 16，我们只需要让它再扩容2次，16 ——> 32 ——> 64即可满足; 但是对于第 ① 个条件而言, 如何才能顺利地把八个元素挂载在table数组的同一索引处？ 答案是: key的哈希码值。 只要 key的哈希码值相同，就能轻松将多个元素挂载到同一链表下（当然前提得value不一样）。
演示代码:
java">import java.util.HashMap;@SuppressWarnings({"all"})
public class HashMap_Demo2 {public static void main(String[] args) {HashMap hashMap = new HashMap();for (int i = 0; i < 12; ++i) {hashMap.put(new Fruit(), i);}for (Object o : hashMap.entrySet()) {System.out.println(o);}}
}class Fruit {@Overridepublic int hashCode() {return 400;}@Overridepublic String toString() {return "Fruit{}";}
}
对于条件①: table数组的某索引处的链表中，元素的个数达到或超过8个；
对于条件②: table数组本身的长度达到或超过64个。
java"> for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// TREEIFY_THRESHOLD = 8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}// 当在某条链表下挂载的元素达到8后，会进入treeifyBin方法进行二次判断final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// MIN_TREEIFY_CAPACITY = 64if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}
从上述代码可知: 如果table数组当前的长度不够64，就继续调用resize方法进行扩容；直到table数组的长度达到64后才开始树化。当前集合中共有8 + 2 = 10个元素, 此时 table 数组中元素的类型是 HashMap$Node 类型。
当向集合中添加第11个元素时，就会对元素个数达到或超过8的链表进行树化, 如下图所示:
第11个元素添加后，瞬间结点中新增了一些属性，并且table表中元素的类型由HashMap$Node类型转换为了HashMap$TreeNode类型。
10.4 HashTable
10.4.1 概述
哈希表(Hash Table)，又名做散列表，是根据关键字和值直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，用于存放记录的数组叫做哈希表。 哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。HashTable 是线程安全的(synchronized ), HashMap 是线程不安全的。
10.4.2 Hashtable 和 HashMap 对比
| 版本 | 线程安全 | 效率 | 允许null键null值 | |
|---|---|---|---|---|
HashMap | 1.2 | 不安全 | 高 | 可以 |
HashTable | 1.0 | 安全 | 较低 | 不可以 |
10.5 Properties
10.5.1 概述
Properties（Java.util.Properties）是 Java 中一个比较重要的类，主要用于读取Java的配置文件。Properties 是一个 Map 体系集合类，因为其继承于 Hashtable，而 Hashtable 继承于 Dictionary类，实现了 Map 接口，所以 Properties 也保留了其相关特性。
10.5.2 基本特点
- ①
Properties是Hashtable<Object,Object>的子类； - ②
Properties类表示了一个可持久的属性集； - ③
Properties可以保存在流中或从流中加载； - ④
Properties中每个键和对应的值都是一个字符串（String类型）； - ⑤
Properties有一个特殊的作用：专门用来加载xxx.properties配置文件。
11.Collections工具类
11.1 概述
Collections 是个操作 Set、List 和 Map 等集合的工具类Collections 工具类位于 java.util 包下
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作。如果提供给它们的集合或类对象为 null，则此类的方法都抛出一个 NullPointerException。
11.2 常用方法
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法（均为 static方法）。
1.排序
| 方法 | 描述 |
|---|---|
| reverse(List) | 反转 List 中元素的顺序 |
| shuffle(List) | 对 List 集合元素进行随机排序 |
| sort(List) | 根据元素的自然顺序对指定 List 集合元素按升序排序 |
| sort(List，Comparator) | 根据指定的 Comparator 产生的顺序对 List 集合元素进行排序 |
| swap(List，int， int) | 将指定 list 集合中的 i 处元素和 j 处元素进行交换 |
java">@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();list.add("abc");list.add("abcde");list.add("abcdefg");list.add("abcdef");list.add("abcd");// 排序System.out.println(list);// [abc, abcde, abcdefg, abcdef, abcd]Collections.sort(list);System.out.println(list);// [abc, abcd, abcde, abcdef, abcdefg]}
}
===================================================================================
@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();list.add("abc");list.add("abcde");list.add("abcdefg");list.add("abcdef");list.add("abcd");// 排序:根据字母长度进行排序System.out.println(list); // [abc, abcde, abcdefg, abcdef, abcd]Collections.sort(list, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {int o1len = o1.length();int o2len = o2.length();if (o1len > o2len) {return 1;} else if (o1len < o2len) {return -1;} else {return 0;}}});System.out.println(list); // [abc, abcd, abcde, abcdef, abcdefg]}
}=========================================================================================
@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();list.add("abc");list.add("abcde");list.add("abcdefg");list.add("abcdef");list.add("abcd");// 交换System.out.println(list);// [abc, abcde, abcdefg, abcdef, abcd]Collections.swap(list, 2, 3);System.out.println(list);// [abc, abcde, abcdef, abcdefg, abcd]}
}
2.查找
| 方法 | 描述 |
|---|---|
| Object max(Collection) | 根据元素的自然顺序，返回给定集合中的最大元素 |
| Object max(Collection，Comparator) | 根据 Comparator 指定的顺序，返回给定集合中的最大元素 |
| Object min(Collection) | 根据元素的自然顺序，返回给定集合中的最小元素 |
| Object min(Collection，Comparator) | 根据 Comparator 指定的顺序，返回给定集合中的最小元素 |
| int binarySearch(List list,T key) | 在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。 |
| int binarySearch(List list,T key,Comparator c) | 在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且集合也事先必须是按照c比较器规则进行排序过的，否则结果不确定。 |
| int frequency(Collection c，Object o) | 返回指定集合中指定元素的出现次数 |
java">@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();list.add("abc");list.add("abcde");list.add("abcdefg");list.add("abcdef");list.add("abcd");System.out.println(list);// [abc, abcde, abcdefg, abcdef, abcd]// 取集合中的最大元素System.out.println(Collections.max(list));// abcdefg}
}=========================================================================================
@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();list.add("abc");list.add("abcde");list.add("abcdefg");list.add("abcdef");list.add("abcd");System.out.println(list);// 排序:在进行二分查找之前必须对集合进行排序Collections.sort(list);System.out.println(list);// 排序之后的集合System.out.println(Collections.binarySearch(list, "abcd"));// 1System.out.println(Collections.binarySearch(list, "abqd"));// -6}
}
3.复制、替换
| 方法 | 描述 |
|---|---|
| void copy(List dest,List src) | 将src中的内容复制到dest中 |
| boolean replaceAll(List list，Object oldVal，Object newVal) | 使用新值替换 List 对象的所有旧值 |
java">@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();Collections.addAll(list, 10, 20, 30, 40, 50, 30, 70);System.out.println(list);//[10, 20, 30, 40, 50, 30, 70]Collections.replaceAll(list, 30, 300);System.out.println(list);//[10, 20, 300, 40, 50, 300, 70]}
}
4.添加
| 方法 | 描述 |
|---|---|
| boolean addAll(Collection c,T… elements) | 将所有指定元素添加到指定 collection 中 |
java">@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {List list = new ArrayList();Collections.addAll(list, "abc", "abcde", "abcdefg", "abcdef", "abcd");System.out.println(list);}
}
12.总结
