十四、集合
14.1 集合的引入及好处
前面我们保存多个数据使用的是数组，那么数组有不足的地方，我们分析一下
14.1.1 数组的缺陷
- 数组的长度声明时候就固定好了，无法修改
- 数组里的元素必须是统同一类型
- 使用数组进行增加/删除时不方便
- 如数组扩容的步骤：
- 声明原数组
int[] nums = {1, 2, 3, 4}; - 拷贝原数组内容并扩容
int[] numsNew = Arrays.copy(nums, nums.length + 1); - 在新数组插入数据
numsNew[numsNew.length - 1] = 1;
14.1.2 集合的好处
- 集合的长度 可变
- 可以 动态保存任意多个对象（类型不固定）
- 使用集合添加，删除新元素更简单
- 提供了一系列方便的操作对象的方法：
add、remove、set、get等
14.2 集合框架体系图
14.2.1 集合框架体系图
Java 的集合类很多，主要分为两大类，如图：
14.2.2 单列集合和双列集合
- 集合主要有两种，单列
Collection和双列Map Collection有两个子接口List,Set他们的实现子类都是单列集合Map的实现子类都是双列集合 采用键值对的形式存数据K(key) - V(value)
public class List01 {
public static void main(String[] args) {
//1. 集合主要有两种，单列和双列
//2. Collection 有两个子接口 List, Set. 他们的实现子类都是单列集合
//3. Map 的实现子类都是双列集合 采用键值对的形式存数据 K(key) - V(value)
ArrayList arrayList = new ArrayList();
HashMap hashMap = new HashMap();
//存数据
arrayList.add("张三");
hashMap.put("No.1", "张三");
}
}
14.3 Collection 接口的常用方法
14.3.1 Collection 接口实现类的特点
Collection实观子类可以存放多个元素，每个元素可以是Objiect- 有些
Collection的实现类，可以存放重复的元素List，有些不可以Set - 有些
Collection的实现类是有序的（List），有些不是有序（Set） Collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的
14.3.2 Collection 接口的常用方法
add添加单个元素remove删除指定元素contains查找元素是否存在size获取元素个数isEmpty判断是否为空clear清空addAll添加多个元素containsAll查找多个元素是否都存在removeAll删除多个元素
以ArrayList 类对象来演示
package com.hspedu.collection;
import java.util.ArrayList;
import java.util.Collection;
public class CollectionMethod {
public static void main(String[] args) {
//以ArrayList 类对象来演示
Collection collection = new ArrayList();
//add:添加
boolean b = collection.add("张三");
collection.add(1); //传入的必须是Object类或子类对象，这里做了自动装箱
collection.add(false);
System.out.println("collection = " + collection); //collection = [张三, 1, false]
//remove:删除指定元素
boolean remove = collection.remove("张三");
System.out.println("collection = " + collection);
//删除指定下标 返回被删除的元素
Object remove1 = collection.remove(0);
System.out.println("collection = " + collection); //collection = [1, false]
System.out.println("remove1 = " + remove1); //remove1 = 李四
//contains:查找元素是否存在
boolean b1 = collection.contains(1);
System.out.println("b1 = " + b1); //b1 = true
//size:获取元素个数
int size = collection.size();
System.out.println("size = " + size); //size = 2
//isEmpty:判断是否为空
ArrayList arrayList1 = new ArrayList();
boolean empty = arrayList1.isEmpty();
System.out.println("empty = " + empty); //empty = true
//clear:清空
arrayList1.add("张三");
arrayList1.add("张四");
arrayList1.add("张五");
arrayList1.add("张六");
System.out.println("arrayList1 = " + arrayList1); //[张三, 张四, 张五, 张六]
arrayList1.clear();
System.out.println("arrayList1 = " + arrayList1); //arrayList1 = []
//addAll:添加多个元素 传入Collection及其子类对象
arrayList1.addAll(collection); //添加一个集合的元素
System.out.println("arrayList1 = " + arrayList1); //arrayList1 = [1, false]
arrayList1.addAll(0, collection);
System.out.println("arrayList1 = " + arrayList1); //arrayList1 = [1, false, 1, false]
//containsAll:查找多个元素是否都存在
boolean b2 = arrayList1.containsAll(collection);
System.out.println("b2 = " + b2); //b2 = true
//removeAll：删除多个元素
boolean b3 = arrayList1.removeAll(collection); //删除和arrayList集合相同的元素
System.out.println("b3 = " + b3); //b3 = true
System.out.println("arrayList1 = " + arrayList1); //arrayList1 = []
}
}
14.3.3 Collection 接口遍历元素方式1 – 使用 Iterator(迭代器)
介绍： Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。
类继承关系： Iteratable 接口有一个 iterator() 方法，用以返回一个实现了 lterator 接口的对象， Collection 继承了 Iteratable 接口 ，即所有的 Collection 集合类都有这个方法，用以返回一个迭代器。
场景： lterator 仅用于遍历集合， lterator 本身并不存放对象。
细节： Iterator 的结构.见下图：
迭代器的执行原理
Iterator 类常用方法：
next()指向下一个元素，并将其返回hasNext()有下一个元素就返回true
案例：
package com.hspedu.collection_;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
/**
* @author: Carl Zhang
* @create: 2021-12-03 13:46
*/
public class CollectionIterator {
public static void main(String[] args) {
Collection col = new ArrayList();
col.add(new Book("三国演义", "罗贯中", 10.1));
col.add(new Book("小李飞刀", "古龙", 5.1));
col.add(new Book("红楼梦", "曹雪芹", 34.6));
//遍历col
//1. iterator() 方法返回 col 的iterator对象
Iterator iterator = col.iterator();
//hasNext() 有下一个元素就返回true
//2. 当有下一个元素才能继续遍历，否则就退出
while (iterator.hasNext()) {
//3. 指向下一个元素，并将其返回
Object o = iterator.next();
System.out.println("o = " + o); //动态绑定机制
}
//3. 当退出循环，这是迭代器指向的最后一个位置，再执行 next() 会抛异常
//Object next = iterator.next(); //NoSuchElementException
//4. 如果还想遍历，需重置迭代器
iterator = col.iterator();
//遍历快捷键 itit, 快捷键列表 Ctrl + j
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
}
}
class Book {
private String name;
private String author;
private double 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;
}
public Book(String name, String author, double price) {
this.name = name;
this.author = author;
this.price = price;
}
@Override
public String toString() {
return "Book{" + name + ", " + author + ", "+ price + '}';
}
}
14.3.4 Collection 接口遍历对象方式 2-for 循环增强
特点：
- 底层还是创建了的
Iterator，调用了hasNext()和next()，可以理解成是简化版的Iterator - 只能用于
Collection集合与数组 - 快捷键：
I
public class CollectionForPlus {
public static void main(String[] args) {
Collection col = new ArrayList();
//ArrayList col = new ArrayList();
col.add(new Book("三国演义", "罗贯中", 10.1));
col.add(new Book("小李飞刀", "古龙", 5.1));
col.add(new Book("红楼梦", "曹雪芹", 34.6));
//遍历Collection集合
//Debug分析：
//1. 底层还是创建了的Iterator，调用了hasNext() 和 next()
//2. 可以理解成是简化版的Iterator
//3. 快捷键：I
for (Object o :col) {
System.out.println(o);
}
////遍历数组
//int[] nums = {1, 3, 5, 3, 22, 11, 199};
//for (int i :nums) {
// System.out.println(i);
//}
}
}
14.4 List 接口和常用方法
14.4.1 List 接口介绍
List接口是Collection接口的子接口List集合类中元素 有序（即添加顺序和取出顺序一致）、且 可重复List集合中的每个元素都有其对应的顺序索引，即支持 索引。List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。List接口常用实现类：ArrayList、LinkedList和Vector
14.4.2 List 接口常用方法
见案例：
public class ListMethod {
public static void main(String[] args) {
List list = new ArrayList();
//void add(int index, Object ele):在 index 位置插入 ele 元素
list.add("张三");
list.add(0,"李四");
System.out.println(list);
//boolean addAll(int index, Collection eles):从 index 位置开始将 eles 中的所有元素添加进来
List list1 = new LinkedList();
list1.add("本山");
list1.add("德彪");
list.addAll(2, list1);
System.out.println(list);
//Object get(int index):获取指定 index 位置的元素
System.out.println(list1.get(0));
//int indexOf(Object obj):返回 obj 在集合中首次出现的位置
list.addAll(list1);
int i = list.indexOf("本山");
System.out.println(i);
//int lastIndexOf(Object obj):返回 obj 在当前集合中末次出现的位置
int i1 = list.lastIndexOf("本山");
System.out.println(i1);
//Object remove(int index):移除指定 index 位置的元素，并返回此元素
Object remove = list.remove(0);
System.out.println(remove);
//Object set(int index, Object ele):设置指定 index 位置的元素为 ele , 相当于是替换.
System.out.println(list);
list.set(1, "赵四");
System.out.println(list);
//List subList(int fromIndex, int toIndex):返回从 fromIndex 到 toIndex 位置的子集合
// 含头不含尾
List list2 = list.subList(3, 5);
System.out.println(list2); //[本山, 德彪]
}
}
14.4.3 练习
public class ListExercise02 {
public static void main(String[] args) {
//List list1 = new LinkedList();
//List list1 = new ArrayList();
List list1 = new Vector();
list1.add(new Book("水浒传", 44, "施耐庵"));
list1.add(new Book("西游记", 33, "罗贯中"));
list1.add(new Book("红楼梦", 25, "曹雪芹"));
//按价格冒泡排序
for (int i = 0; i < list1.size() - 1; i++) {
for (int j = 0; j < list1.size() - 1 - i; j++) {
Book book1 = (Book)list1.get(j);
Book book2 = (Book)list1.get(j + 1);
//比较价格，进行元素交换
if (book1.getPrice() > book2.getPrice()) {
list1.set(j, book2); //用 set 方法进行元素交换
list1.set(j + 1, book1);
}
}
}
for (Object o : list1) {
System.out.println(o);
}
}
}
class Book {
private String name;
private double price;
private String author;
...
}
14.5 ArrayList 底层结构和源码分析
14.5.1 ArrayList 的注意事项
permits all elements，including null，ArrayList可以加入null，并且多个ArrayList是由数组来实现数据存储的 【后面解读源码】ArrayList基本等同于Vector，除了ArrayList是 线程不安全（执行效率高）- 看源码（
public boolean add(E e)没有**synchronization**关键字） - 在多线程情况下，不建议使用
ArrayList
14.5.2 ArrayList 的底层操作机制源码分析(重点，难点.)
ArrayList中维护了一个Object类型的数组elementData【debug看源码】transient Object[]elementData；transient表示瞬间，短暂的，表示该属性不会被序列化- 当创建
ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10 ，如需要再次扩容，则扩容elementData为1.5倍。 - 如果使用的是指定大小的构造器，则初始
elementData容量为指定大小。需要扩容，则直接扩容elementData为1.5倍
public class ArraySource {
public static void main(String[] args) {
//注意，注意，注意，Idea 默认情况下，Debug 显示的数据是简化后的，如果希望看到完整的数据
//需要做设置.
//使用无参构造器创建 ArrayList 对象
//ArrayList list = new ArrayList();
ArrayList list = new ArrayList(8);
//使用 for 给 list 集合添加 1-10 数据
for (int i = 1; i
示意图：
14.6 Vector 底层结构
14.6.1 Vector 与 ArrayList 比较
14.6.2 Vector 底层操作机制源码分析
public class Vector01 {
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);
//老韩解读源码
//1. new Vector() 底层
/*
public Vector() {
this(10);
}
补充：如果是 Vector vector = new Vector(8);
走的方法:
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
2. vector.add(i)
2.1 //下面这个方法就添加数据到 vector 集合
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
2.2 //确定是否需要扩容
条件 ： minCapacity - elementData.length > 0
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法
//newCapacity = oldCapacity + ((capacityIncrement > 0) ?
// capacityIncrement : oldCapacity);
//就是扩容两倍.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
*/
}
}
介绍：LinkedList底层实现了双向 链表和双端 队列
特点：
- 可以添加任意元素（元素可以重复），包括 null
-
线程不安全，没有实现同步
-
LinkedList底层维护了一个双向链表. -
LinkedList中维护了两个属性first和last分别指向首节点和尾节点每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表。 - 所以
LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。
package com.hspedu.list_;
import java.util.LinkedList;
/**
* @author: Carl Zhang
* @create: 2021-12-06 16:56
*/
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=" + linkedList);
//Debug 源码分析
/*
1. LinkedList linkedList = new LinkedList();
public LinkedList() {}
此时 linkedList属性 first = null, last = null;
2. linkedList.add() 执行添加
public boolean add(E e) {
linkLast(e); //调用linkLast()方法添加元素和节点
return true;
}
3. linkLast() 将新的节点，添加到双向链表最后
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null); //创建一个新节点，pre指向最后的节点
last = newNode; //重新将last指向新创建的节点
if (l == null) //如果是第一次添加，就将first指向刚创建的节点
first = newNode;
else
l.next = newNode; //第二次及以后，就将之前的last节点的next指向新创建的节点
size++;
modCount++;
}
此时
l.next -> newNode,
l
14.9 Set 接口和常用方法
14.9.1 Set 接口基本介绍
- 无序（添加和取出的顺序不一致），没有索引[后面演示]
- 不允许重复元素，所以最多包含一个
null JDKAPI中Set接口的实现类有：
14.9.2 Set 接口的常用方法
-
和
List接口一样,Set接口也是Collection的子接口，因此，常用方法和Collection接口一样. -
遍历：同
Collection的遍历方式一样，因为Set接口是Collection接口的子接口。 - 可以使用迭代器
- 增强
for - 不能使用索引的方式来获取
package com.hspedu.set_;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* @author Carl Zhang
* @description
* @date 2021/12/6 20:47
*/
public class SetMethod {
public static void main(String[] args) {
// 1. 以 Set 接口的实现类 HashSet 来讲解 Set 接口的方法
// 2. set 接口的实现类的对象(Set 接口对象), 不能存放重复的元素, 可以添加一个 null
// 3. set 接口对象存放数据是无序(即添加的顺序和取出的顺序不一致)
// 4. 注意：取出的顺序的顺序虽然不是添加的顺序，但是他的固定.
Set set = new HashSet();
set.add("john");
set.add("lucy");
set.add("john");//重复
set.add("jack");
set.add("hsp");
set.add("mary");
set.add(null);
set.remove("jack");
System.out.println(set);
set.add(null);//再次添加 null
for (int i = 0; i < 10; i++) {
System.out.println("set=" + set);
}
//遍历
//一、使用迭代器
System.out.println("一、使用迭代器");
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
System.out.println();
//二、增强型for
System.out.println("二、增强型for");
for (Object o : set) {
System.out.println(set);
}
System.out.println();
//三、使用for循环
System.out.println("三、使用for循环");
//for (int i = 0; i < set.get(); i++) { //没有get方法
//
//}
}
}
14.10 Set 接口实现类 – HashSet
14.10.1 HashSet 的全面说明
HashSet实现了Set接口HashSet实际上是HashMap，看下源码.（图）
- 可以存放
null值，但是只能有一个null HashSet不保证元素是有序的，取决于hash后，再确定索引的结果（即，不保证存放元素的顺序和取出顺序一致）- 不能有重复元素/对象.在前面
Set接口使用已经讲过
package com.hspedu.set_;
import java.util.HashSet;
/**
* @author Carl Zhang
* @description
* @date 2021/12/6 21:36
*/
public class HashSet_ {
public static void main(String[] args) {
HashSet set = new HashSet();
set.add("lucy");//添加成功
set.add("lucy");//加入不了
set.add(new Dog("tom"));//OK
set.add(new Dog("tom"));//Ok
System.out.println("set=" + set);
//去看他的源码，即 add 到底发生了什么?=> 底层机制.
set.add(new String("hsp"));//ok
set.add(new String("hsp"));//加入不了.
System.out.println("set=" + set);
}
}
class Dog {
private String name;
public Dog(String name) {
this.name = name;
}
@Override
public String toString() {
return "Dog{" + "name='" + name + '\'' + '}';
}
}
14.10.2 模拟数组链表
分析：
HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树）- 通过案例模拟 简单的数组+链表结构，理解底层结构
public class SimpleHashSet {
public static void main(String[] args) {
//创建 Node 数组
Node[] table = new Node[10];
//往table的第一个位置添加元素
Node jack = new Node("jack", null);
table[2] = jack;
Node wick = new Node("wick", null);
jack.next = wick; //将wick节点挂载到jack
Node lucy = new Node("lucy", null);
wick.next = lucy; //将lucy节点挂载到wick
//往table的第三个位置添加元素
Node john = new Node("john", null);
table[3] = john;
}
}
//节点类，有next属性，指向下一个节点，从而形成链表
class Node {
Object item;
Node next;
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
}
通过 debug 查看 table 数组结构：
14.10.3 HashSet 底层机制说明（hash（）+ equals（））
底层：
HashSet底层是HashMap
扩容机制：
- 添加一个元素时，先得到
hash值再转成 -> 索引值 - 找到存储数据表
table，看这个索引位置是否已经存放的有元素 - 如果没有，直接加入
- 如果有，调用
equals()比较，如果相同，就放弃添加，如果不相同，则添加到最后 - 在
Java8中，如果一条链表的元素个数 超过TREEIFY THRESHOLD（默认是8），并且table的大小 >=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）否则仍采用数组扩容机制
通过 **debug** 分析底层机制：
package com.hspedu.set_;
import java.util.HashSet;
/**
* @author: Carl Zhang
* @create: 2021-12-07 10:18
*/
public class HashSetSource {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
boolean res = hashSet.add("java");//到此位置，第 1 次 add 分析完毕
System.out.println(res);
boolean hsp = hashSet.add("hsp");
System.out.println(hsp);
boolean java = hashSet.add("java");
System.out.println(java);
//debug分析：
/* 1. new HashSet(); 底层是 new HashMap<>();
public HashSet() {
map = new HashMap<>();
}
2. 执行hashSet.add("java");
public boolean add(E e) {
//private static final Object PRESENT = new Object();
//是一个常量的空Object对象
return map.put(e, PRESENT)==null; //判读是否添加成功
}
3. 执行put key = "java" , value = PRESENT
该方法会调用hash(key), 返回对应的hash值, 算法：(h = key.hashCode()) ^ (h >>> 16);
public V put(K key, V value) {
//这里执行完添加成功 return null
//否则就return 重复的对象的key，表示要添加的元素已经存在
return putVal(hash(key), key, value, false, true);
}
4. 执行 putVal(hash(key), key, value, false, true);
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node[] tab; HashMap.Node p; int n, i; //定义辅助变量
//table 是 HashMap 的一个Node类型数组[]，用来存储数据
//if语句判断table是否为null，或者长度是否为0
//是就执行resize() 初始化容量为16 , threshold = 12 临界值，防止多线程同时添加溢出问题，类比教室扩充座位
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1)判断key对应的索引位置是否为null
//(1.1).通过hash值算出索引：i = (n - 1) & hash], 注意：hash值不同，两个元素的索引也可能相同
//(1.2).将对应索引位置的值传给p
//(2)如果为null，就表示索引位置为空，就创建一个 newNode(key = "java", value = PRESENT)
// 再放在对应位置 tab[i] = newNode(hash, key, value, null);
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//开发小技巧：在需要局部变量辅助的时候，再创建
HashMap.Node e; K k; //定义辅助变量
//(1) 如果目标索引位置对应的链表第一个元素p的hash值等于要添加的key的hash值，并且满足以下二者之一条件：
//(1.1) p所指向的Node节点元素的key 和 要添加的key相同
//(1.2) 要添加的key不为空 并且 key的内容 与 p所指向的Node节点元素的内容 相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//(2) 否则判断 p 是不是一颗红黑树
// 是红黑树，就调用putTreeVal()方法进行添加
else if (p instanceof TreeNode)
e = ((HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
//(3) 如果上面两条都不满足，表示目标索引位置是一条链表，通过循环进行比较
//(3.1) 依次将链表的每一个元素与null比较，如果等于null，就创建newNoe()，将要添加的key
// 挂载到链表后面，注意：挂载完成后，立即判断链表内元素的个数是否超过8个，
// 超过就调用treeifyBin(tab, hash);对当前链表进行树化(转成红黑树)
// 注意：进行树化之前会先判断，判断条件如下：
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //默认为64
// resize();
// 如果满足上述条件，就将table先扩容
// 只有上述条件不成立，才会进行树化
//(3.2) 如果在循环比较过程中，发现链表中的元素与要添加的元素相同，就直接退出
else {
for (int binCount = 0; ; ++binCount) { //这是一个死循环
if ((e = p.next) == null) { //因为p已经在前面比较过，所以从p.next开始
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断添加后的 table 里的节点个数是否大于临界值
if (++size > threshold)
resize(); //扩容
afterNodeInsertion(evict);
return null;
}
*/
}
}
分析 **HashSet** 的扩容和转成红黑树机制：
HashSet底层是HashMap，第一次添加时，table数组扩容到 16，临界值（threshold）是16 * 加载因子（loadFactor）是 0.75 = 12- 如果
table数组使用到了临界值12，就会扩容到 16 _ 2 = 32，新的临界值就是 32 _ 0.75 = 24，依次类推 - 在
Java8中，如果单条链表的元素个数 超过TREEIFY_THRESHOLD（默认是8），并且table的大小 >=MIN TREEIFY CAPACITY（默认64），就会进行 树化（红黑树），否则仍然采用 *数组扩容机制
package com.hspedu.set_;
import java.util.HashSet;
/**
* @author Carl Zhang
* @description
* @date 2021/12/7 19:24
*/
public class HashSetIncrement {
public static void main(String[] args) {
// HashSet 底层是 HashMap，第一次添加时，table数组扩容到 16，临界值（threshold）
// 是16*加载因子loadFactor）是0.75=12
HashSet set = new HashSet();
set.add("马大帅");
//如果table数组使用到了临界值12，就会扩容到16*2=32，新的临界值就是32*0.75=24，依次类推
//注意：此处处临界值到了12，也包括了table中单条链表的元素个数 ，
// 如果table的元素个数，加所有链表的元素的个数达到12，也会调用resize()进行扩容
//for (int i = 1; i [] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0; //定义辅助变量
//1. 如果原来的table容量大于0 进入此处
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//这里先将oldCap << 1 即原始容量 * 2 ，然后赋值给newCap
//再判断newCap是否大于MAXIMUM_CAPACITY 并且oldCap >= 16
//满足就将oldThr * 2 得到newThr(新临界值)
//新临界值与新容量的关系同时满足：newThr = newCap * 0.75(即默认的加载系数)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //DEFAULT_INITIAL_CAPACITY = 16
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//2. 如果第一次扩容，就执行此处
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //默认的值 = 16
//新的阈值(临界值) = (int) 0.75 * 16 = 12
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 = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//3. 创建扩容后的Node数组并传递给newTab
Node[] newTab = (Node[])new Node[newCap];
table = newTab; //将扩容后的newTab传递给table
//如果原数组不为空，就把原数组的元素拷贝给新数组
if (oldTab != null) {
//..... 省略此处代码
}
return newTab;
}
* */
//在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认是8），并且table的
// 大小>=MIN TREEIFY CAPACITY（默认64），就会进行树化（红黑树），否则仍然采用数组扩容机制
//debug演示
//思路：
// 1. 要在单条链表添加元素 -> 即要满足 添加元素的索引相同，并且 每个元素的key和内容都不同
// 可用重写hashCode()方法，返回同一个值，使得每个要添加的元素的目标索引相同
// 创建不同的对象，使得每个元素的key不同
// 给每个元素赋不同的属性，使得每个元素的内容不同
// 2. 利用循环往同一个链表上添加9个元素
for (int i = 1; i
14.10.4 HashSet 练习
定义一个 Employee 类，该类包含： private 成员属性 name， sal， birthday（ MyDate 类型），其中 birthday 为 MyDate 类型（属性包括： year， month， day），要求：
- 创建3个
Employee放入HashSet中 - 当
name和birthday的值相同时，认为是相同员工，不能添加到HashSet集合中
package com.hspedu.set_;
import java.util.HashSet;
/**
* @author: Carl Zhang
* @create: 2021-12-08 10:30
*/
public class HashSetExercise02 {
public static void main(String[] args) {
//定义一个Employee类，该类包含：private成员属性name，sal，birthday（MyDate类
//型），其中birthday为MyDate类型（属性包括：year，month，day），要求：
//1.创建3个Employee放入HashSet中
//2.当name和birthday的值相同时，认为是相同员工，不能添加到HashSet集合中
//分析：Employee类，name sal birthday属性
// MyDate类 ，year，month，day属性 继承LocalDate类
// 重写Employee的hashCode() ,equals(), toString()
// 重写MyDate类的hashCode() ,equals(), toString()
HashSet set = new HashSet();
set.add(new Employee("张三",20000, new MyDate("1999", "01", "09")));
set.add(new Employee("李四",8000, new MyDate("1998", "01", "09")));
set.add(new Employee("王五",9000, new MyDate("1997", "01", "09")));
set.add(new Employee("张三",20000, new MyDate("1999", "01", "09")));
for (Object o : set) {
System.out.println(o);
}
}
}
package com.hspedu.set_;
import java.util.Objects;
/**
* @author: Carl Zhang
* @create: 2021-12-08 10:36
*/
public class Employee {
//分析：Employee类，name sal birthday属性
// 重写Employee的hashCode() ,equals()
private String name;
private double sal;
private MyDate birthday;
public Employee(String name, double sal, MyDate birthday) {
this.name = name;
this.sal = sal;
this.birthday = birthday;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Employee)) return false;
Employee employee = (Employee) o;
return Objects.equals(name, employee.name) &&
Objects.equals(birthday, employee.birthday);
}
@Override
public int hashCode() {
return Objects.hash(name, birthday);
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", sal=" + sal +
", birthday=" + birthday +
'}';
}
}
package com.hspedu.set_;
import java.time.LocalDateTime;
import java.util.Objects;
import java.util.SplittableRandom;
/**
* @author: Carl Zhang
* @create: 2021-12-08 10:36
*/
public class MyDate {
// MyDate类 ，year，month，day属性 继承LocalDate类
// 重写MyDate类的hashCode() ,equals()
private String year;
private String month;
private String day;
public MyDate(String year, String month, String day) {
this.year = year;
this.month = month;
this.day = day;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof MyDate)) return false;
MyDate myDate = (MyDate) o;
return Objects.equals(year, myDate.year) &&
Objects.equals(month, myDate.month) &&
Objects.equals(day, myDate.day);
}
@Override
public int hashCode() {
return Objects.hash(year, month, day);
}
@Override
public String toString() {
return
"year：" + year + '\'' +
", month：'" + month + '\'' +
", day：'" + day + '\'' +
'}';
}
}
LinkedHashSet是HashSet的子类LinkedHashSet底层是一个LinkedHashMap，底层维护了一个 数组 + 双向链表LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的 次序（图），这使得元素看起来是以插入 顺序保存的。LinkedHashSet不允许添 重复元素
debug 分析源码：
package com.hspedu.set_;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* @author: Carl Zhang
* @create: 2021-12-08 11:40
*/
public class LinkedHashSetSource {
public static void main(String[] args) {
Set set = new LinkedHashSet();
set.add(new String("AA")); //第一次添加
set.add(456); //第二次添加
set.add(456);
set.add(new Customer("刘", 1001));
set.add(123);
set.add("HSP");
System.out.println(set);
// 结论：
// 1. LinkedHashSet 添加的顺序和取出的顺序一致
// 2. LinkedHashSet 底层创建的是 LinkedHashMap(是HashMap的子类)
// initialCapacity = 16, loadFactor = 0.75，有head和tail属性
// 3. 添加元素时最终调用的是HashMap.putVal() 方法，添加机制和HashSet一致，添加节点最终调用
// 的是LinkedHashMap.newNode() 添加完成之后会将添加的元素加入双向链表中
// 4. LinkedHashSet 底层结构是 table数组(HashMap$Node类型) + 双向链表
// 5. LinkedHashSet 第一次添加时会将table扩容到16
// 6. LinkedHashMap 中的table里的节点是 LinkedHashMap$Entry 类型，是 HashMap$Node 的子类
// 有before和after属性
//debug分析源码
/*
1. 执行new LinkedHashSet() 初始容量16 加载系数0.75
//底层调用的是父类HashSet的构造器, new LinkedHashMap(initialCapacity, loadFactor);
public LinkedHashSet() {
super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
2. 执行set.add(new String("AA")); 第一次添加
//底层调用的是hashSet.add() -> map.put() -> hashMap.put() -> hashMap.putVal() 过程与HashSet的扩容一致
//执行hashMap.putVal() 方法时
if ((p = tab[i = (n - 1) & hash]) == null)
//2.1 此处调用newNode(), 最终调用的是LinkedHashMap.newNode() 动态绑定机制
tab[i] = newNode(hash, key, value, null);
//2.2 创建了内部类LinkedHashMap.Entry的对象，最终创建的节点是LinkedHashMap$Entry 类型
Node newNode(int hash, K key, V value, Node e) {
LinkedHashMap.Entry p =
new LinkedHashMap.Entry(hash, key, value, e);
linkNodeLast(p); // 这个方法会将节点挂载到链表最后 解析见 3.
return p;
}
//2.3 内部类LinkedHashMap.Entry
//table的类型是Node 这里节点Entry 继承了Node类型，所以能保存在table里
//编程思想：Node是HashMap的静态内部类，所以能直接类名.内部类访问
// 因为这个Node类只想在HashMap类里使用，所以设计成静态的
static class Entry extends HashMap.Node {
Entry before, after; //Entry的两个属性，一个执行前面节点，一个执行后面节点
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
3. 执行linkNodeLast(p); 将节点挂载到链表最后从而形成双向链表
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry p) {
LinkedHashMap.Entry last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
* */
}
}
class Customer {
private String name;
private int id;
public Customer(String name, int id) {
this.name = name;
this.id = id;
}
@Override
public String toString() {
return "name='" + name + '\'' +
", id=" + id;
}
}
14.12 Map 接口和常用方法
14.12.1 Map 接口实现类特点【很实用】
注意：这里讲的是 JDK8 的 Map 接口特点
Map与Collection并列存在。用于保存具有映射关系的数据Key-Value（双列元素）Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中，底层是HashMap$Node类型的数组table，与hashSet一致- 但是常用
String类作为Map的key -
Map中的key不允许重复，原因和HashSet一样，前面分析过源码. -
Map中的value可以重复 Map的key可以为null，value也可以为null，注意key为null，只能有一个，value为null,可以多个key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value
import java.util.HashMap;
import java.util.Map;
/**
* @author: Carl Zhang
* @create: 2021-12-08 15:09
*/
public class Map_ {
public static void main(String[] args) {
//1. Map 与 Collection 并列存在。用于保存具有映射关系的数据:Key-Value(双列元素)
//2. Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中
// 但是常用 String 类作为 Map 的 key
//3. Map 中的 key 不允许重复，原因和 HashSet 一样，前面分析过源码.
//4. Map 中的 value 可以重复
//5. Map 的 key 可以为 null, value 也可以为 null ，注意 key 为 null,
// 只能有一个，value 为 null ,可以多个
//6. key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
Map map = new HashMap();
map.put("no1", "韩顺平");//k-v
map.put("no2", "张无忌");//k-v
map.put("no1", "张三丰");//当有相同的 k , 就等价于替换.
map.put("no3", "张三丰");//k-v
map.put(null, null); //k-v
map.put(null, "abc"); //等价替换
map.put("no4", null); //k-v
map.put("no5", null); //k-v
map.put(1, "赵敏");//k-v
map.put(new Object(), "金毛狮王");//k-v
// 通过 get 方法，传入 key ,会返回对应的 value
System.out.println(map.get("no2"));//张无忌
System.out.println("map=" + map);
}
}
Map存放数据的key-value示意图，一对k-v是放在一个HashMap$Node中的，有因为Node实现了Entry接口，有些书上也说一对k-v就是一个Entry，其实Entry里存放的是HashMap$Node里key、value的引用
package com.hspedu.map_;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
* @author: Carl Zhang
* @create: 2021-12-08 16:06
*/
public class MapSource {
public static void main(String[] args) {
Map map = new HashMap();
map.put("no1", "韩顺平");//k-v
map.put("no2", "张无忌");//k-v
map.put(new Car(), new Person());//k-v
//老韩解读
//1. k-v 最终是 在创建 newNode(hash, key, value, null) 时，存入到的newNode节点里，类型是HashMap$Node
//2. 为了方便程序员的遍历，还会 创建 EntrySet 集合 EntrySet>，该集合存放的元素的类型 Entry, 而一个Entry
// 对象就有k,v 即：transient Set> entrySet;
//3. Entry对象里的k,v 存放的是newNode节点里key，value的地址值，即是一个引用，而不是新创建了对象
//4. entrySet 中， 定义的类型是 Map.Entry ，但是实际上存放的还是 HashMap$Node
// 这时因为 static class Node implements Map.Entry
//5. 当把 HashMap$Node 对象 存放到 entrySet 就方便我们的遍历, 因为 Map.Entry 提供了重要方法
// K getKey(); V getValue();
Set set = map.entrySet(); //返回entrySet 集合
System.out.println(set.getClass());// HashMap$EntrySet
for (Object obj : set) {
System.out.println(obj.getClass()); //运行类型HashMap$Node
//为了从 HashMap$Node 取出k-v
//1. 先做一个向下转型
Map.Entry entry = (Map.Entry) obj; //这里因为 HashMap$Node 是内部类，无法访问，所以转换成Entry类型
System.out.println(entry.getKey() + "-" + entry.getValue() );
}
Set set1 = map.keySet(); //返回keySet集合，即map里存放的key
System.out.println(set1.getClass()); //HashMap$KeySet 结构：final class KeySet extends AbstractSet
Collection values = map.values(); //返回values集合，即map里存放的value
System.out.println(values.getClass()); //HashMap$Values 结构：final class Values extends AbstractCollection
}
}
class Car {
}
class Person{
}
14.12.2 Map 接口常用方法
remove：根据键删除映射关系
get：根据键获取值
size：获取元素个数
isEmpty：判断个数是否为0
clear：清除k-V
containskey：查找键是否存在
package com.hspedu.map_;
import java.util.HashMap;
import java.util.Map;
/**
* @author: Carl Zhang
* @create: 2021-12-08 16:46
*/
public class MapMethod {
public static void main(String[] args) {
//演示 Map 常用方法
Map map = new HashMap();
map.put("邓超", new Book("", 100));//OK
map.put("邓超", "孙俪");//替换-> 一会分析源码
map.put("王宝强", "马蓉");//OK
map.put("宋喆", "马蓉");//OK
map.put("刘令博", null);//OK
map.put(null, "刘亦菲");//OK
map.put("鹿晗", "关晓彤");//OK
map.put("hsp", "hsp 的老婆");
System.out.println("map=" + map);
//remove:根据键删除映射关系
Object remove = map.remove("邓超");
System.out.println(remove); //孙俪
//get：根据键获取值
Object o = map.get("王宝强");
System.out.println(o); //马蓉
//size:获取元素个数
int size = map.size();
System.out.println(size); //6
//isEmpty:判断个数是否为 0
boolean empty = map.isEmpty();
System.out.println(empty); //false
//clear:清除 k-v
//map.clear();
//System.out.println(map);
//containsKey:查找键是否存在
boolean b = map.containsKey("王宝强");
System.out.println(b); //true
}
}
class Book {
private String name;
private int num;
public Book(String name, int num) {
this.name = name;
this.num = num;
}
}
14.12.3 Map 接口遍历方法
通过 EntrySet、 keySet、 values 集合的方式获取对应的 k - v，思路与 List、 Set 类似
package com.hspedu.map_;
import java.util.*;
/**
* @author Carl Zhang
* @description
* @date 2021/12/8 21:25
*/
public class MapFor {
public static void main(String[] args) {
Map map = new HashMap();
map.put("邓超", "孙俪");
map.put("王宝强", "马蓉");
map.put("宋喆", "马蓉");
map.put("刘令博", null);
map.put(null, "刘亦菲");
map.put("鹿晗", "关晓彤");
//第一组: 先取出 所有的 Key , 通过 Key 取出对应的 Value
//通过 map.keySet() 返回所有 key 引用集合
Set set = map.keySet();
//(1) 增强型 for
System.out.println("(1) 增强型for");
for (Object o : set) {
Object o1 = map.get(o); //通过 key 拿到 value
System.out.println(o + "-" +o1);
}
System.out.println();
//(2) 用迭代器
System.out.println("(2) 用迭代器");
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
Object o = map.get(next);
System.out.println(next + "-" + o);
}
System.out.println();
//第二组: 把所有的 values 引用取出
//通过 map.values() 返回 values 集合
Collection values = map.values();
//(1) 增强 for
System.out.println("(1) 增强型for");
for (Object o : values) {
System.out.println(o);
}
System.out.println();
//(2) 用迭代器
System.out.println("(2) 用迭代器");
Iterator iterator1 = values.iterator();
while (iterator1.hasNext()) {
Object next = iterator1.next();
System.out.println(next);
}
System.out.println();
//第三组: 通过 EntrySet 来获取 k-v
//通过map.entrySet() 返回entrySet集合
Set entrySet = map.entrySet();
//(1) 增强for
System.out.println("(1) 增强for");
for (Object o : entrySet) { //这里的 o 运行类型是 Hashmap$Node 类型，但是由于权限访问不了
//System.out.println(o.getClass()); //class java.util.HashMap$Node
Map.Entry entry = (Map.Entry) o; //向下转型成 Map$Entry 类型，
// 调用 getKey() 和 getValue()
System.out.println(entry.getKey() + "-" + entry.getValue());
}
System.out.println();
//(2) 迭代器
Iterator iterator2 = entrySet.iterator();
System.out.println("(2) 迭代器");
while (iterator2.hasNext()) {
Object next = iterator2.next();
Map.Entry next1 = (Map.Entry) next;
System.out.println(next1.getKey() + "-" + next1.getValue());
}
}
}
14.13 Map 接口实现类 – HashMap
14.13.1 HashMap 小结
Map接口的常用实现类：HashMap、Hashtable和Properties。HashMap是Map接口使用 频率最高的实现类。HashMap是以key-val对的方式来存储数据（HashMap$Node类型）【案例Entry】key不能重复，但是值可以重复，允许使用null键和null值。- 如果添加相同的key，则会覆盖原来的
key-val，等同于修改，key不会替换，val会替换。（putValue()方法里有e.value = value;） - 与
HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的.（jdk8的hashMap底层 数组+链表+红黑树）HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized
14.13.2 HashMap 底层机制分析
HashMap 底层机制和 HashSet 完全一致，因为 HashSet 底层也是 HashMap
- 底层结构：
HashMap底层维护了Node类型的数组table，默认为null - 当 创建对象时，将加载因子（
loadfactor）初始化为0.75。 - 添加机制：当添加
key-val时，通过key的hash值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加，如果该索引处有元素，继续判断该元素的key不相等需要判断是树结构还是链表结构，做出相应处理。如果添加完发现容量超过临界值，则需要扩容。 - 第1次添加，则需要扩容
table容量为16，临界值（threshold）为12（16*0.75） - 以后再扩容，则需要扩容
table容量为原来的2倍（32），临界值为原来的2倍，即24，依次类推。 - 树化：
Java8中，如果一条链表的元素个数超过TREEIFY THRESHOLD（默认是8），并且table的大小 >=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）
package com.hspedu.map_;
import java.util.HashMap;
/**
* @author: Carl Zhang
* @create: 2021-12-09 11:11
*/
public class HashMapSource {
public static void main(String[] args) {
HashMap map = new HashMap();
Object o = map.put("java", 10);//ok
map.put("php", 10);//ok
map.put("java", 20);//替换 value
System.out.println("map=" + map);//
/*
debug 分析源码
1. 执行 HashMap map = new HashMap();
//先调用父类AbstractMap的无参，再将加载因子设置为DEFAULT_LOAD_FACTOR 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2. 执行map.put();
//2.2 先根据传入的key获取hash值，再调用putVal()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i; //定义辅助遍历
//(1) 判断table是否为空或长度是否为0，如果满足就先将table扩容至16，临界值 16*0.75 = 12
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(2) 根据hash值获取要添加的位置，如果位置为空就直接添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //(3) 如果不为空，还要进行三种情况判断
Node e; K k; //定义辅助变量
//(3.1) 如果目标位置的第一个元素的hash值和要添加元素的hash值一样，并且和要添加的元素是同一个对象
就将目标位置第一个元素返回
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//(3.2) 如果目标位置是红黑树，就调用红黑树的方法进行添加，再返回
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//(3.3) 既不是同一个元素，也不是红黑树，就是链表
//将链表上的元素和要添加的元素循环比较，相同就跳出循环，为空就添加到链表后面
//每次添加完要判断链表上的元素是否超过8个，超过就调用treeifyBin(tab, hash)进行树化
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //树化方法，解析见 3.
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果添加没成功，就将原来位置的元素的value进行替换并返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //value 替换
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //hashMap 修改次数++
if (++size > threshold) //添加成功后如果元素个数超过临界值，数组table就会扩容
resize();
afterNodeInsertion(evict);
return null; //添加成功返回null
}
3. 进行树化，真正树化之前还会进行判断，如果table为空，或者长度小于64，就会先扩容
剪枝：红黑树进行删除元素的操作时，会判断大小，如果不满足红黑树的条件，就会转换成链表
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//....省略
}
* */
}
}
14.14 Map 接口实现类 – Hashtable
14.14.1 Hashtable 基本介绍
类继承关系：
特点：
- 底层维护的是
Hashtable数组[] table，初始大小11，加载因子0.75，临界值 =11 * 0.75 = 8 - 存放的 元素是键值对：即
K-V，每个节点元素是Hashtable$Entry类型 hashtable的键和值都不能为null，否则会抛出NullPointerExceptionhashtable使用方法基本上和HashMap一样hashtable是 线程安全的（synchronized），hashMap是线程不安全的hashtable有 自己的扩容机制，debug分析源码👇
package com.hspedu.map_;
import java.util.Hashtable;
/**
* @author: Carl Zhang
* @create: 2021-12-09 13:59
*/
public class HashTable_ {
public static void main(String[] args) {
Hashtable hashtable = new Hashtable(); //初始大小11，加载因子0.75，临界值 = 11 * 0.75 = 8
//● 存放的元素是键值对：即K-V
hashtable.put("01", "赵四"); // 底层是Hashtable数组，每个节点是Hashtable$Entry类型
hashtable.put("02", "赵二四");
hashtable.put("03", "赵小四");
//● hashtable 的键和值都不能为null，否则会抛出NullPointerException
//hashtable.put(null, "马大帅"); //NullPointerException
//hashtable.put("04", null); //NullPointerException
//● hashTable 使用方法基本上和HashMap一样
//● hashTable 是线程安全的（synchronized），hashMap是线程不安全的
hashtable.put("01", "马大帅"); //替换
hashtable.put("04", "赵小四");
hashtable.put("05", "范德彪");
hashtable.put("06", "华强");
hashtable.put("07", "瓜摊摊主");
hashtable.put("08", "路人");
hashtable.put("09", "助手"); //扩容后 threshold 17, 大小为23
System.out.println(hashtable);
//debug查看扩容机制
// 1. 最终真正扩容调用的是 rehash();
// 2. 新容量的算法：int newCapacity = (oldCapacity << 1) + 1; 即oldCapacity * 2 + 1
}
}
14.14.2 Hashtable 和 HashMap 比较
14.15 Map 接口实现类 – Properties
14.15.1 Properties 基本介绍
Properties类继承自Hashtable类并且实现了Map接口，也是使用一种 键值对的形式来保存数据。- 他的使用特点和
Hashtable类似 Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改- 说明：工作后
xxx.properties文件通常作为 配置文件，这个知识点在IO流举例，有兴趣可先看文章
14.15.2 Properties 基本方法
package com.hspedu.map_;
import java.util.Properties;
/**
* @author: Carl Zhang
* @create: 2021-12-09 15:32
*/
public class PropertiesMethod {
public static void main(String[] args) {
Properties properties = new Properties();
//增加
properties.put("name", "张三");
properties.put("password", "123456");
//properties.put(null, "本山"); //NullPointerException
//properties.put("deBiao", null); //NullPointerException
System.out.println(properties);
//通过 k 获取对应值
Object name = properties.get("name");
System.out.println(name);
//删除
Object name1 = properties.remove("name");
System.out.println(name1);
System.out.println(properties);
//修改
properties.put("name", "李四");
properties.put("name", "马大帅"); //覆盖相同key的value 等同于修改
System.out.println(properties);
}
}
14.16 总结-开发中如何选择集合实现类(记住)
14.16.1 TreeSet 底层机制分析
package com.hspedu.set_;
import java.util.Comparator;
import java.util.TreeSet;
/**
* @author Carl Zhang
* @description
* @date 2021/12/9 20:04
*/
public class TreeSetSource {
@SuppressWarnings({"all"})
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add("a");
treeSet.add("b");
treeSet.add("abc");
treeSet.add("abcd");
treeSet.add("A");
treeSet.add("AB");
treeSet.add("ABCD");
treeSet.add("ABCDE");
System.out.println(treeSet); //[A, AB, ABCD, ABCDE, a, abc, abcd, b]
//1. 当我们使用无参构造器，创建 TreeSet 时，仍然是无序的
//2. 老师希望添加的元素，按照字符串长度排序
//3. 使用 TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)并指定排序规则
TreeSet treeSet1 = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).length() - ((String) o2).length();
}
});
treeSet1.add("a");
treeSet1.add("b");
treeSet1.add("abc");
treeSet1.add("abcd");
treeSet1.add("A");
treeSet1.add("AB");
treeSet1.add("ABCD");
treeSet1.add("ABCDE");
System.out.println(treeSet1); //[a, AB, abc, abcd, ABCDE] 按设定的规则排序的
//debug查看底层源码
/*
1. 调用含迭代器的构造方法，底层创建的是TreeMap，把匿名对象传递给了this.comparator属性
TreeMap底层维护的是Entry数组，每个节点是Entry类型
public TreeSet(Comparator comparator) {
this(new TreeMap<>(comparator));
}
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
2. 进行添加时，最终调用的也是TreeMap.put()方法
其中：
// split comparator and comparable paths
Comparator cpr = comparator; //cpr 即传递的 comparator 匿名对象
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key); //调用匿名对象的compare方法进行比较
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//当要添加的元素和TreeSet里的元素相同时，即cmp为0时，加入失败，返回默认的value
return t.setValue(value);
} while (t != null);
}
*/
}
}
14.16.2 TreeMap 底层源码分析
package com.hspedu.map_;
import java.util.Comparator;
import java.util.TreeMap;
/**
* @author Carl Zhang
* @description
* @date 2021/12/9 21:46
*/
public class TreeMapSource {
public static void main(String[] args) {
//利用无参构造创建的TreeMap，添加时是无序的，取出来时也没有排序
//TreeMap treeMap = new TreeMap();
//可用创建时传递一个Comparator类型的匿名对象，制定添加时的规则
//指定添加顺序按key的长度排序
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String) o2).length() - ((String) o1).length();
}
});
treeMap.put("jack", "杰克");
treeMap.put("tom", "汤姆");
treeMap.put("kristina", "克瑞斯提诺");
treeMap.put("smith", "斯密斯");
treeMap.put("hsp", "韩顺平");//长度相同加入不了，但是会覆盖之前的value
System.out.println(treeMap);
/*
debug源码：
1. 执行创建 new TreeMap(new Comparator{...})
//底层将实现的匿名内部类传递给了TreeMap的属性this.comparator
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
2. 执行添加方法
2.1 第一次添加会根据动态绑定机制调用匿名内部类的compare方法但是不返回结果
直接将要添加的元素封装成Entry节点传递给root
Entry t = root; //此时root为空
if (t == null) {
//如果treeMap创建时没有传递匿名对象，改对象类也没有实现Comparable接口，重写 CompareTo()方法，就会报错
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
2.2 第二次添加
Comparator cpr = comparator; //将匿名内部类对象传递给cpr
if (cpr != null) {
do { //这里会循环比较要添加的key和已存在的key，确定位置，如果key相同，就会覆盖value
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); //覆盖相同key的value
} while (t != null);
}
HashMap的compare方法
//这里会进行判断
//1. 如果创建TreeMap时传递了匿名对象，就会调用匿名对象的compare方法进行比较
//2. 如果创建时没有传递匿名对象，就会返回调用对象的compareTo()方法
// 如果对象所属类没有实现Compareble接口，重写compareTo()方法，就会抛异常
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
*/
}
}
14.16.3 开发中的集合选型（记住）
在开发中，选择什么集合实现类，主要取决于 业务操作特点，然后根据集合实现类特性进行选择，分析如下：
- 先判断存储的类型（一组 对象【单列】或一组 键值对【双列】）
- 一组对象【单列】：
Collection- 允许重复：
List - 增删多：
LinkedList【底层维护了一个 双向链表】 - 改查多：
ArrayList【底层维护Object类型的 可变数组】 - 不允许重复：
Set - 无序：
HashSet【底层是HashMap，维护了一个哈希表即（ 数组+链表+红黑树）】 - 排序：
TreeSet - 插入和取出顺序一致：
LinkedHashSet，维护 数组+双向链表
- 允许重复：
- 一组键值对【双列】：
Map - 键无序：
HashMap【底层是：哈希表jdk7：数组+链表，jdk8： 数组+链表+红黑树】 - 键排序：
TreeMap - 键插入和取出顺序一致：
LinkedHashMap - 读取文件
Properties
14.17 Collections 工具类
14.17.1 Conllections 工具类介绍
Collections是一个操作Set、List和Map等集合的工具类Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作
14.17.2 Collections 常用方法
reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序，例如抽奖
sort(List：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List,Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行
swap(List,int i,int j)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection,Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection,Comparator)
int frequency(Collection,Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将 src 中的内容复制到 dest 中
boolean replaceAll(List list,Object oldVal,Object newVal)：使用新值替换 List 对象的所有旧值
package com.hspedu.conllections_;
import java.util.*;
/**
* @author: Carl Zhang
* @create: 2021-12-10 09:57
*/
@SuppressWarnings({"all"})
public class CollectionsMethod01 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("马大帅");
list.add("范伟");
list.add("范德彪");
list.add("刘能");
list.add("赵本山");
list.add("赵四");
System.out.println(list); //[马大帅, 赵本山, 范德彪, 范伟, 刘能, 赵四]
//reverse(List):反转 List 中元素的顺序
Collections.reverse(list);
System.out.println(list); //[赵四, 刘能, 范伟, 范德彪, 赵本山, 马大帅]
//shuffle(List):对 List 集合元素进行随机排序，例如抽奖
Collections.shuffle(list);
System.out.println(list); //[范伟, 刘能, 马大帅, 范德彪, 赵四, 赵本山]
Collections.shuffle(list);
System.out.println(list); //[马大帅, 赵四, 范伟, 赵本山, 范德彪, 刘能] 每次结果都不一样
//sort(List):根据元素的自然顺序对指定List 集合元素按升序排序
Collections.sort(list); //内部按照的元素的默认compareTo方法进行排序
System.out.println(list);
//sort(List,Comparator):根据指定的Comparator 产生的顺序对List 集合元素进行
//按照长度对list中的元素排降序
Collections.sort(list, new Comparator() {
//问：为何没有重写Comparator接口的所有方法？
//答：这里虽然只重写的compare方法，但是其他方法被临时重写了，只是方法为空
@Override
public int compare(Object o1, Object o2) {
//排序规则：
//o1, o2 分别对应前一个和后一个元素
//o2 - o1 会将o2排在前面，即降序
//o1 - o2 会将o1排序前面，即升序
return ((String) o1).length() - ((String) o2).length();
}
});
System.out.println(list); //[刘能, 范伟, 赵四, 范德彪, 赵本山, 马大帅]
//排序
//swap(List,int i,int j):将指定list集合中的i处元素和j处元素进行交换
Collections.swap(list, 2, 3);
System.out.println(list); //[刘能, 范伟, 范德彪, 赵四, 赵本山, 马大帅]
//Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
Comparable max = Collections.max(list);
System.out.println(max); //马大帅
//Object max(Collection,Comparator):根据Comparator 指定的顺序,返回给定集合中的最大元素
//指定规则，返回元素中最长的数
Object max1 = Collections.max(list, new Comparator() {
/*
debug查看源码
while (i.hasNext()) {
T next = i.next();
if (comp.compare(next, candidate) > 0) //这里会循环拿候选数跟下一个数比
candidate = next; //满足条件就将候选数替换
}
return candidate; 最终返回满足条件的候选数
* */
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).length() - ((String) o2).length();
}
});
System.out.println(max1);
//Object min(Collection)
Comparable min1 = Collections.min(list);
System.out.println(min1);
//Object min(Collection,Comparator)
//拿到list里长度最小的
Object min = Collections.min(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
/*
if (comp.compare(next, candidate) < 0)
candidate = next;
* */
//return ((String) o2).length() - ((String) o1).length();
return ((String) o1).length() - ((String) o2).length();
}
});
System.out.println(min); //刘能
//int frequency(Collection,Object):返回指定集合中指定元素的出现次数
list.add("刘能");
list.add("刘能");
int frequency = Collections.frequency(list, "刘能");
System.out.println(frequency); //3
//void copy(List dest,List src):将src中的内容复制到dest中
//List list1 = new LinkedList();
//Collections.copy(list1, list); //IndexOutOfBoundsException
//debug查看源码：
/*
底层：会比较元素个数
if (srcSize > dest.size())
throw new IndexOutOfBoundsException("Source does not fit in dest");
结论：目标集合的元素个数要 >= 源数组的元素个数
* */
ArrayList list1 = new ArrayList();
for (int i = 0; i < list.size(); i++) {
list1.add(1);
}
Collections.copy(list1, list);
System.out.println(list1);
//boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List 对象的所有旧值
Collections.replaceAll(list, "刘能", "刘晓莉");
System.out.println(list);
}
}
14.18 本章练习
练习1：
看以下代码运行结果：
知识点： TreeSet() 的添加机制
package com.hspedu.conllections_;
import java.util.TreeSet;
/**
* @author: Carl Zhang
* @create: 2021-12-10 15:02
*/
public class Homework05 {
public static void main(String[] args) {
TreeSet treeSet=new TreeSet();
treeSet.add(new Person()); //ClassCastException
System.out.println(treeSet);
/*
debug查看源码：
底层最终调用的 treeMap.put() -> treeMap.compare() 来确定添加的位置
public V put(K key, V value) {
Entry t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
HashMap的compare方法
这里会进行判断
1. 如果创建TreeMap时传递了匿名对象，就会调用匿名对象的compare方法进行比较
2. 如果创建时没有传递匿名对象，就会将对象转型成Comparable 调用对象的compareTo()方法
如果对象所属类没有实现Comparable接口，重写compareTo()方法，就会抛异常
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
*
* */
}
}
class Person{}
练习2：
看以下代码运行结果：
- 知识点：
hashMap.remove()的删除机制
package com.hspedu.conllections_;
import java.util.HashSet;
/**
* @author: Carl Zhang
* @create: 2021-12-10 15:32
*/
public class Homework06 {
public static void main(String[] args) {
HashSet set = new HashSet();
Person p1 = new Person("AA", 1001); //66443
Person p2 = new Person("BB", 1002); //67434
set.add(p1);
set.add(p2);
p1.name = "CC";
boolean remove = set.remove(p1); //查看源码可知：这里的传入的p1的hash值是按照CC重新算的，而原来的p1的hash值是根据AA来算的
System.out.println(remove); //false
System.out.println(set); //两个元素
set.add(new Person("CC", 1001)); //ok 这里的对象的hash值按照CC计算，与p1的hash值不同
//68427
System.out.println(set);
set.add(new Person("AA", 1001)); //true 这里的hash值已经存在，所以会比较内容，内容不同，添加到链表最后
System.out.println(set);
/*
* debug 查看源码
删除的机制：hashMap.remove()方法 底层也是根据传入object的 hash(key) 来找到要删除的元素的位置
同hashVal()的比较机制一样(hash + equals)
会判断目标位置元素的key和要删除的key是不是同一个元素
是不是一棵树
是不是链表
然后比较是否相同，根据各自删除规则，删除成功返回删除的value，删除失败返回null
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value; //根据传入的key来算出hash值
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //比较是否同一个元素
node = p;
...
*/
}
}
Original: https://www.cnblogs.com/Carl-Zhang/p/15763054.html
Author: Carl-Zhang
Title: 十四、集合（完结）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685897/
转载文章受原作者版权保护。转载请注明原作者出处！