第14章 集合

第14章 集合

集合 用起来不是很难，难点主要有以下2点

前面我们保存多个数据使用的是数组，那么数组有不足的地方，我们分析一下

集合

1）可以动态保存任意多个对象，使用比较方便

2）提供了一系列方便的操作对象的方法：add、remove、set、get等

3）使用集合添加，删除新元素的示意代码—简洁了

集合的框架体系

Java的集合类很多，主要分为两类，如图（这2张图背下来，很重要）：

//老韩解读
//1. 集合主要是两组（单列集合，双列集合）
//2. Collection 接口有两个重要的子接口 List 和 Set，他们的实现子类都是单列结合
//3. Map接口实现的子类是 双列集合
//4. 把老师梳理的两张图记住
//Collection
//Map
ArrayList arrayList = new ArrayList();
arrayList.add("jack");
arrayList.add("tom");

HashMap hashMap = new HashMap();
hashMap.put("No1", "北京");
hashMap.put("No2", "上海");

Collection接口和常用方法

public interface Collection<E> extends Iterable<E>

1）Collection 实现子类可以存放多个元素，每个元素可以是 Object

2）有些 Collection 的实现类，可以存放重复的元素，有些不可以

3）有些 Collection 的实现类，有些是有序的（List），有些不是有序的（Set）

4）Collection接口没有直接的实现子类，是通过它的子接口 List 和 Set 来实现的

接下来选用实现了 Collection 的实现类 ArrayList，来演示 Collection 接口里面的方法

//说明：以ArrayList实现类来演示
List list = new ArrayList(); //这里用List接口来接收
// add：添加单个元素
list.add("jack");
list.add(99); //list.add(new Integer(10))
list.add(true);
System.out.println("list = "+ list);

list.remove(true);
System.out.println("list = "+ list);

if (list.contains("jack"))
System.out.println("存在jack");

//size：获取元素个数
System.out.println(list.size()); //2

//isEmpty：判断是否为空
System.out.println(list.isEmpty()); //False

//clear：清空
list.clear();
System.out.println("list = " + list);

//addAll：添加多个元素
ArrayList list2 = new ArrayList();
list2.add("红楼梦");
list2.add("三国演义");
list.addAll(list2);
System.out.println("list = " + list);

//containsAll：查找多个元素是否都存在
System.out.println(list.containsAll(list2)); //True

//removeAll：删除多个元素
list.add("聊斋");
list.removeAll(list2);
System.out.println("list = " + list);

Collection接口遍历元素方式1→使用Iterator（迭代器）

1）Iterator对象称为迭代器，主要用于遍历Collection 集合中的元素

2）所有实现了Collection 接口的集合类都有一个iterator() 方法，用以返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器

3）Iterator 的结构【看一张图】

4）Iterator 仅用于遍历集合，Iterator 本身并不存放对象

迭代器的使用案例：

package com.hwledu.collection_;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
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.5));
System.out.println(col);
// 现在老师希望能够遍历 col集合
// 1.先得到col对应的迭代器
Iterator iterator = col.iterator();
// 2.使用while循环遍历
// 这里老师教大家一个快捷键，快速生成 while –> itit
// 显示所有的快捷键的 快捷键 ctrl + j
while (iterator.hasNext()){
Object obj = iterator.next();
System.out.println("obj = " + obj);
}
// 3.当退出while循环以后，这时iterator迭代器指向最后的元素
// iterator.next(); // NoSuchElementException
// 4.如果希望再次遍历，需要重置我们的迭代器
iterator = col.iterator();
System.out.println("—————–第二次遍历——————");
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println("obj = " + obj);
}
}
}
class Book {
private String name;
private String author;
private double price;

public Book(String name, String author, double price) {
this.name = name;
this.author = author;
this.price = price;
}
// getter、setter方法
@Override
public String toString() {
return "Book{" + "name='" + name + '\\'' + ", author='" + author + '\\'' + ", price=" + price + '}';
}
}

Collection接口遍历元素方式2→增强for循环

package com.hwledu.collection_;
import java.util.ArrayList;
import java.util.Collection;
public class CollectionFor {
@SuppressWarnings({"all"})
public static void main(String[] args) {
Collection col = new ArrayList();
col.add(new Book("三国演义", "罗贯中", 12.9));
col.add(new Book("小李飞刀", "古龙", 5.1));
col.add(new Book("红楼梦", "曹雪芹", 34.6));
// 1.使用增强for，在Collection集合
// 2.增强for，底层仍是迭代器
// 3.增强for可以理解成就是简化版本的 迭代器遍历
// 4.增强for的快捷键方式
// 1)数组或集合名.for 这个最快了，感觉
// 2) iter 或者 itar
// 3)大写字母I + 回车
for (Object o : col) {
System.out.println("book = " + o);
}
// 增强for，也可以直接在数组中使用
int[] nums = {1, 2, 3, 4};
for (int num : nums) {
System.out.println("num = " + num);
}
}
}

List接口和常用方法

List 接口基本介绍

List接口是 Collection 接口的子接口 List_.java

1）List 集合类中元素有序（即添加顺序和取出顺序一致），且可重复

2）List 集合中的每个元素都有其对应的顺序索引，即支持索引

3）List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素（这就是第2点吧…）

4）JDK API中 List 接口的实现类有（常用的有：Vector、ArrayList、LinkedList）：

package com.hwledu.list_;
import java.util.ArrayList;
import java.util.List;
public class List_ {
@SuppressWarnings({"all"})
public static void main(String[] args) {
//1. List集合类中元素有序（即添加元素和取出元素一致）、且可重复[案例]
List list = new ArrayList();
list.add("jack");
list.add("tom");
list.add("mary");
list.add("hsp");
System.out.println("list = "+ list);
//2. List 集合中的每个元素都有其对应的顺序索引，即支持索引
// 索引是从0开始的
System.out.println(list.get(3)); //hsp
}
}

List接口的常用方法

List list = new ArrayList();
list.add("许嵩");
list.add("王菲");
System.out.println("list = " + list);
// void add(int index, Object obj)：在index位置插入obj元素
// 在index = 1 的位置插入一个对象
list.add(1, "韩顺平");
System.out.println("list = " + list);

// boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
List list2 = new ArrayList();
list2.add("jack");
list2.add("tom");
list.addAll(1, list2);
System.out.println("list = " + list);

// Object get(int index):获取指定index位置的元素
// 讲过了

// int indexOf(Object obj):返回obj在集合中 首次出现的位置
System.out.println(list.indexOf("tom")); // 2

// int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
list.add("韩顺平");
System.out.println("list=" + list);
System.out.println(list.lastIndexOf("韩顺平"));

// Object remove(int index):移除指定index位置的元素，并返回此元素
list.remove(2); //去掉tom
System.out.println("list=" + list);

//Object set(int index, Object ele): 设置指定index位置的元素为ele , 相当于是替换
list.set(4, "kkk");
System.out.println("list=" + list);

// List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合
// 注意返回的子集合 fromIndex <= subList < toIndex 左闭右开
List returnList = list.subList(0, 2);
System.out.println("returnList = " + returnList);

List 的三种遍历方式 [ArrayList, LinkedList, Vector]

1）方式1：使用 Iterator

2）方式2：使用 增强 For

3）方式3：使用 普通 For

package com.hwledu.list_;
import java.util.*;
public class ListFor {
@SuppressWarnings({"all"})
public static void main(String[] args) {
// List 接口的实现子类 Vector LinkedList
// List list = new ArrayList();
// List list = new Vector();
LinkedList list = new LinkedList();
list.add("jack");
list.add("tom");
list.add("鱼香肉丝");
list.add("北京烤鸭");

// 遍历
// 方法1. 迭代器
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Object o = iterator.next();
System.out.println(o);
}
System.out.println("—————————————");
// 方法2. 增强for
for (Object o : list) {
System.out.println(o);
}
System.out.println("—————————————");
// 方法3. 使用普通for
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}

package com.hwledu.list_;
import java.util.*;
public class ListExercise02 {
public static void main(String[] args) {
// List list = new ArrayList();
// List list = new Vector();
List list = new LinkedList();

list.add(new Book("红楼梦", "曹雪芹", 100));
list.add(new Book("三国", "罗贯中", 200));
list.add(new Book("西游记", "吴承恩", 180));
list.add(new Book("水浒传", "施耐庵", 110));
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Object s = iterator.next();
System.out.println(s);
}
sort(list);
System.out.println("———————-");
for (Object o : list) {
System.out.println(o);
}

}

public static void sort(List list) {
for (int i = 0; i < list.size() – 1; i++) {
for (int j = 0; j < list.size() – i – 1; j++) {
Book book1 = (Book) list.get(j);
Book book2 = (Book) list.get(j + 1);
if (book1.getPrice() > book2.getPrice()) {
list.set(j + 1, book1); //这里这样实现 反而简单些
list.set(j, book2);
}
}
}
}
}

class Book {
private String name;
private String author;
private int price;

public Book(String name, String author, int price) {
this.name = name;
this.author = author;
this.price = price;
}
// Getter、Setter方法
@Override
public String toString() {
return "书名：" + name + "\\t\\t" + "作者：" + author + "\\t\\t" +
"价格：" + price + "\\t\\t";
}
}

ArrayList 注意事项

1）可以加入null，并且多个

2）ArrayList 是由数组来实现数据存储的

3）ArrayList 基本等同于Vector，除了ArrayList 是线程不安全（执行效率高）看源码。在多线程情况下，不建议使用 ArrayList

//ArrayList 是线程不安全的，可以看源码 没有synchronized
/*
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
*/
ArrayList arrayList = new ArrayList();
arrayList.add(null);
arrayList.add("jack");
arrayList.add(null);
arrayList.add("hsp");
System.out.println(arrayList);

ArrayList底层源码

先设置以下关于 Debug 的

先说结论，再分析源码

1）ArrayList 中维护了一个 Object 类型的数组 elementData [debug 看源码]

transient Object[] elementData; //transient 表示瞬间的，短暂的，表示该属性不会被序列化

2）当创建 ArrayList 对象时，如果使用的是无参构造器，则初始 elementData 容量为 0，第 1 次添加，则扩容 elementData 为 10，如需要再次扩容，则扩容elementData 为 1.5 倍

3）如果使用的是指定大小的构造器，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为 1.5 倍

一定要自己去 debug 一把 ArrayList 的创建和扩容的流程

public class ArrayListSource {
public static void main(String[] args) {
// 注意，注意，注意，Idea 默认情况下，Debug 显示的数据是简化后的，如果希望看到完整的数据
// 需要做设置.
// 使用无参构造器创建ArrayList对象
ArrayList arrayList = new ArrayList();
//ArrayList arrayList = new ArrayList(8); //有参
for (int i = 1; i <= 10; i++) {
arrayList.add(i);
}

for (int i = 11; i <= 15; i++) {
arrayList.add(i);
}
arrayList.add(100);
arrayList.add(200);
arrayList.add(null);
}
}

进去， →

这里的划线的其实就是个空数组。

然后出来到添加 add

进去，

size 初始化为 0

再进去，

DEFAULT_CAPACITY 默认为10，

再进去，

这里的 modCount 也是初始化为 0：

再进去，到 grow

然后一层一层出来，直到 add 方法

再到：

接下来再次扩容（满10个了）：

然后像第一次一样，逐层返回

使用有参基本上与上面一样。

Vector基本介绍

1）Vector 类的定义说明

2）Vector 底层也是一个对象数组：

protected Object[] elementData;

3）Vector 是线程同步的，即线程安全，Vector 类的操作方法带有 synchronized

4）在开发中，需要线程同步安全时，考虑使用 Vector

看Vector的源码

public class Vector_ {
public static void main(String[] args) {
//先看Vector类的无参构造
Vector vector = new Vector();
//Vector vector = new Vector(8); //有参
for (int i = 1; i <= 10 ; i++) {
vector.add(i);
}
for (int i = 11; i < 20; i++) {
vector.add(i);
}
}
}

先看Vector类的无参构造，

进去，

再调用本类的有参构造器

再进去

再逐层返回到主方法中，elementData 数组中就有 10 个了

第一个 for 完成后，装满 10 个数据，接下来接着装，需要扩容

进去，

到 ensureCapacityHelper，进去：

再进去 grow：

再逐层返回到主函数，可见已经扩容到了 20 个：

有参基本也和上面一样。其实 Vector 的扩容基本就和 ArrayList 一样。

LinkedList

LinkedList的底层操作机制

1）LinkedList 的底层维护了一个双向链表

2）LinkedList 中维护了两个属性 first 和 last 分别指向首结点和尾结点

3）每个结点（Node对象）里面又维护了prev、next、item三个属性，其中通过 prev 指向前一个，通过 next 指向后一个结点。最终实现双向链表。

4）所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高

5）模拟一个简单的双向链表

package com.hwledu.list_;
public class LinkedList01 {
public static void main(String[] args) {
//模拟一个简单的双向链表
Node jack = new Node("jack");
Node tom = new Node("tom");
Node hsp = new Node("老韩");

//连接三个结点，形成双向链表
//jack -> tom -> hsp
jack.next = tom;
tom.next = hsp;
//hsp -> tom -> jack
hsp.pre = tom;
tom.pre = jack;

Node first = jack;// 让first引用指向jack,就是双向链表的头结点
Node last = hsp; // 让last引用指向hsp,就是双向链表的尾结点

//演示，从头到尾进行遍历
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.pre;
}

//演示链表的添加对象/数据，是多么的方便
//要求，是在 tom ——— 老韩直接，插入一个对象 smith

//1. 先创建一个 Node 结点，name 就是 smith
Node smith = new Node("smith");
//下面就把 smith 加入到双向链表了
smith.next = hsp;
smith.pre = tom;
hsp.pre = smith;
tom.next = smith;

//让first 再次指向jack
first = jack;//让first引用指向jack,就是双向链表的头结点

System.out.println("===从头到尾进行遍历===");
while (true) {
if (first == null) {
break;
}
//输出first 信息
System.out.println(first);
first = first.next;
}

last = hsp; //让last 重新指向最后一个结点
//演示，从尾到头的遍历
System.out.println("====从尾到头的遍历====");
while (true) {
if (last == null) {
break;
}
//输出last 信息
System.out.println(last);
last = last.pre;
}
}
}

class Node {
public Object item;
//类是引用类型
public Node pre;
public Node next;

public Node(Object item) { this.item = item; }

@Override
public String toString() { return "Node name = " + item; }
}

LinkedList的增删改查案例

public class LinkedListCRUD {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println("linkedList=" + linkedList);

//演示一个删除结点的
linkedList.remove(); // 这里默认删除的是第一个结点
//linkedList.remove(2);

System.out.println("linkedList=" + linkedList);

//修改某个结点对象
linkedList.set(1, 999);
System.out.println("linkedList=" + linkedList);

//得到某个结点对象
//get(1) 是得到双向链表的第二个对象
Object o = linkedList.get(1);
System.out.println(o);//999

//因为LinkedList 是 实现了List接口, 遍历方式
System.out.println("===LinkeList遍历迭代器====");
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("next=" + next);

}
System.out.println("===LinkeList遍历增强for====");
for (Object o1 : linkedList) {
System.out.println("o1=" + o1);
}
System.out.println("===LinkeList遍历普通for====");
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}
//老韩源码阅读.
/* 1. LinkedList linkedList = new LinkedList();
public LinkedList() {}
2. 这时 linkeList 的属性 first = null last = null
3. 执行 添加
public boolean add(E e) {
linkLast(e);
return true;
}
4.将新的结点，加入到双向链表的最后
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;
else
l.next = newNode;
size++;
modCount++;
}

*/

/*
老韩读源码 linkedList.remove(); // 这里默认删除的是第一个结点
1. 执行 removeFirst
public E remove() {
return removeFirst();
}
2. 执行
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size–;
modCount++;
return element;
}
*/
}
}

如何选择 ArrayList 和 LinkedList ：

Set 接口和常用方法

Set 接口基本介绍

1）无序（添加和取出顺序不一致），没有索引

2）不允许重复元素，所以最多包含一个 null

3）JDK API 中 Set 接口的实现类有：

Set 接口的常用方法

和 List 接口一样，Set 接口也是Collection 的子接口，因此常用方法和 Colection 接口一样

Set 接口的遍历方式

同 Collection 的遍历方式一样，因为 Set 接口是 Collection 接口的子接口

// Set 接口的常用方法举例
// 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.add(null);
for (int i = 0; i < 10; i++) {
System.out.println("set = "+ set);
}
//遍历
//方式1：使用迭代器
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println("obj = " + obj);
}
set.remove(null); //去掉null

//方式2: 增强for
System.out.println("=====增强for====");
for (Object o : set) {
System.out.println("o = " + o);
}
//注意：set接口对象，不能通过索引来获取！！！

Set 接口实现类-HashSet

HashSet 的全面说明

1）HashSet 实现了 Set 接口

2）HashSet 实际上是HashMap：

3）可以存放 null 值，但是只能有一个 null

4）HashSet 不保证元素是有序的，取决于 hash 后，再确定索引的结果。（即：不保证存放元素的顺序和取出顺序一致）

5）不能有重复元素/对象。在前面 Set 接口使用时已经讲过

package com.hwledu.set_;
import java.util.HashSet;
public class HashSet01 {
public static void main(String[] args) {
HashSet set = new HashSet();
System.out.println(set.add("john")); // T
System.out.println(set.add("lucy")); // T
System.out.println(set.add("john")); // F
System.out.println(set.add("jack")); // T
System.out.println(set.add("rose")); // T
set.remove("john");
System.out.println("set = " + set);
System.out.println("——–");
set = new HashSet();
System.out.println("set = " + set); //0
//4. Hashset 不能添加相同的元素/数据？
set.add("lucy"); //添加成功
set.add("lucy"); //加入不了
set.add(new Dog("tom")); //OK
set.add(new Dog("tom")); //OK
System.out.println("set = " + set);
System.out.println("————–");

//再加深一下. 非常经典的面试题.
//看源码，做分析， 先给小伙伴留一个坑，以后讲完源码，你就了然
//去看他的源码，即 add 到底发生了什么?=> 底层机制.
set.add(new String("hsp")); //ok
set.add(new String("hsp")); //加入不了
System.out.println("set = " + set);
}
}
class Dog { //定义Dog 类
private String name;
public Dog(String name) { this.name = name; }
@Override
public String toString() {
return "Dog{" + "name='" + name + '\\'' + '}';
}
}

HashSet底层机制说明

HashSet 底层是 HashMap，HashMap 底层是 数组 + 链表 + 红黑树

package com.hwledu.set_;

import java.util.HashSet;
@SuppressWarnings({"all"})
public class HashSetSource {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println("HashSet = " + hashSet);
}
}

第1次 add 的执行流程如下：

hashSet.add("java");

hash 方法见下图：

下面这张图片 628 行那里的红色字体有点小错误， ，table 是一个数组

然后逐层返回

第2次 add("php") 的执行流程（跟第一次大差不差）如下：

hashSet.add("php");

return null 后，逐层返回

接下来到最复杂的，添加 "java"（与之前重复）。

hashSet.add("java");

就不会返回 null → 不返回 null 就代表插入失败！

最终的输出就只有 "java", "php"。

他写的代码解释：

package com.hspedu.set_;

import java.util.HashSet;

@SuppressWarnings({"all"})
public class HashSetSource {
public static void main(String[] args) {

HashSet hashSet = new HashSet();
hashSet.add("java"); //到此位置，第1次add分析完毕.
hashSet.add("php"); //到此位置，第2次add分析完毕
hashSet.add("java");
System.out.println("set=" + hashSet);

/*
老韩对HashSet 的源码解读
1. 执行 HashSet()
public HashSet() {
map = new HashMap<>();
}
2. 执行 add()
public boolean add(E e) {//e = "java"
return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
}
3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//key = "java" value = PRESENT 共享
return putVal(hash(key), key, value, false, true);
}
4.执行 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; //定义了辅助变量
//table 就是 HashMap 的一个数组，类型是 Node[]
//if 语句表示如果当前table 是null, 或者 大小=0
//就是第一次扩容，到16个空间.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;

//(1) 根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
// 并把这个位置的对象，赋给 p
//(2) 判断p是否为null
//(2.1) 如果p为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)

if ((p = tab[i = (n – 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
Node<K,V> e; K k; //
//如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
//并且满足 下面两个条件之一:
//(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
//(2) p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判断 p 是不是一颗红黑树,
//如果是一颗红黑树，就调用 putTreeVal , 来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果table对应索引位置，已经是一个链表, 就使用for循环比较
//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意，在转成红黑树时，要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立，先table扩容.
// 只有上面条件不成立时，才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break

for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD(8) – 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;
//size 就是我们每加入一个结点Node(k,v,h,next), size++
if (++size > threshold)
resize();//扩容
afterNodeInsertion(evict);
return null;
}
*/
}
}

HashSet（底层是HashMap）的扩容机制

先演示上图的1、2点：

package com.hwledu.set_;
import java.util.HashSet;
//(Increment n.增长)
public class HashSetIncrement {
public static void main(String[] args) {
/*
HashSet底层是HashMap，第一次添加时，table数组扩容到 16，临界值(threshold)为 16 × 加载因子(loadFactor，默认0.75) = 12
如果table数组长度到了临界值 12，就会扩容到 16 * 2 = 32，此时新的临界值就是 32 * 0.75 = 24, 依次类推：64(48) → 128(96)…
*/
HashSet hashSet = new HashSet();
for (int i = 1; i <= 100; i++) {
hashSet.add(i); // 1, 2, 3, 4, 5…100
}
}
}

可见，到 threshold = 12 的时候，总的容量就扩容到了 32 个

依此类推…

下面演示图片中的第3点

public class HashSetIncrement {
@SuppressWarnings({"all"})
public static void main(String[] args) {
HashSet hashSet = new HashSet();
/*
在Java8中，如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认8)，
并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制
*/
for (int i = 1; i <= 12; i++) {
hashSet.add(new A(i)); //equals()不同，保证所有A对象都在一条链表上
}
}
}

class A {
private int n;
public A(int n) { this.n = n; }
/**
* 重写hashCode方法，返回固定的值
*/
@Override
public int hashCode() {
return 100; // 使得所有A对象的hashCode都是100
}
}

一个链表的元素个数 >= 8 了，但 table 的大小没有 >= 64，所以不会树化 → table 扩到 32 个，还是不会树化 → table 扩到 64 个，再下一步，才开始树化。

树化很复杂，这里就不再追了。

Set 接口的实现类-LinkedHashSet

LinkedHashSet 的全面说明

1）LinkedHashSet 是 HashSet 的子类

2）LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个数组 + 双向链表

3）LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

4）LinkedHashSet 不允许添加重复元素

public class LinkedHashSetSource {
public static void main(String[] args) {
//分析一下 LinkedHashSet 的底层机制
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=" + set);
// 1.LinkedHashSet 加入顺序和取出元素/数据的顺序一致
// 2.LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)
// 3.LinkedHashSet 底层结构 (数组table+双向链表)
// 4.添加第一次时，直接将数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry
// 5.数组是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$Entry类型
/*
//继承关系是在内部类完成.
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);
}
}
*/

}
}
class Customer {
private String name;
private int no;

public Customer(String name, int no) {
this.name = name;
this.no = no;
}
}

Map 接口

Map接口实现类的特点 [很实用]

public class Map_ {
@SuppressWarnings({"all"})
public static void main(String[] args) {
// 老韩解读Map 接口实现类的特点，使用实现类HashMap
// 1、Map与Collection并列存在。用于保存具有映射关系的数据：Key—Value（双列元素）
// 2、Map 中的key 和 value 可以是任何引用类型的数据，会封装到HashMap$Node对象中
// 3、Map中的key 不允许重复，原因和HashSet 一样，前面分析过源码
// 4、Map中的value 可以重复
// 5、Map中的key可以为null，value也可以为null，注意key为null只能有一个，value为null，可以有多个
// 6、常用String 类作为Map的key
// 7、key 和 value之前存在单向一对一关系，即通过指定的key 总能找到对应的value
Map map = new HashMap();
map.put("no1", "韩顺平"); // k-v
map.put("no2", "张无忌"); // k-v
map.put("no1", "张三丰"); // 当有相同的key，就等价于替换
// map.put("no3", "张三丰"); // k-v
map.put(null, null); // k-v
map.put(null, "abc"); // 等价替换
map.put("no4", null);
map.put("no5", null);
map.put(1, "赵敏");
map.put(new Object(), "金毛狮王"); // k-v
System.out.println(map.get(1));// 通过get方法，传入key，会返回对应的value
System.out.println(map.get("no2")); // 张无忌
System.out.println(map);
}
}

p532 听了 3 遍，才基本听懂，要自己动手啊。后面回来再看看

真正的 key 和 value 是放在 HashMap$Node 里面的，而 set 集合 和 collection 集合只是指向它们而已。只是为了方便去遍历key、value，提供了set 和collection。把 set 和 collection 做成一组对象放在 Entry 里面，把 Entry 再放到 EntrySet 集合 里面。在底层只是建立一个简单的引用。

它是这样一个结构：table表里面是以 数组+链表+红黑树 的方式来组织 Node，但是为了方便管理，它在底层做了一个控制，把每一个Node 封装成 entry，然后把 entry 放到 entrySet 集合里去，方便管理。注意只是指向，并不是真正放到里面去。

@SuppressWarnings({"all"})
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 最后是 HashMap$Node node = newNode(hash, key, value, null)
//2. k-v 为了方便程序员的遍历，还会 创建 EntrySet 集合，该集合存放的元素的类型 Entry, 而一个Entry对象就有k,v EntrySet<Entry<K,V>> 即： transient Set<Map.Entry<K,V>> entrySet;
//3. entrySet 中， 定义的类型是 Map.Entry，但是实际上存放的还是 HashMap$Node，这是因为 static class Node<K,V> implements Map.Entry<K,V>
//4. 当把 HashMap$Node 对象 存放到 entrySet 就方便我们的遍历, 因为 Map.Entry 提供了重要方法
// K getKey(); V getValue();
Set set = map.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;
System.out.println(entry.getKey() + "-" + entry.getValue() );
}
Set set1 = map.keySet();
System.out.println(set1.getClass()); //class java.util.HashMap$KeySet
Collection values = map.values();
System.out.println(values.getClass()); //class java.util.HashMap$Values
}
}
class Car {}
class Person{}

Map 接口常用方法

public class MepMethod {
@SuppressWarnings({"all"})
public static void main(String[] args) {
Map map = new HashMap();
map.put("邓超", new Book("", 100));
map.put("邓超", "孙俪"); //替换->一会儿分析源码
map.put("王宝强", "马蓉");
map.put("许嵩", "黄龄");
map.put("千百度", null);
map.put(null, "刘亦菲");
map.put("鹿晗", "关晓彤");
map.put("hsp", "hsp的老婆");
System.out.println("map = "+ map);
}
}
class Book {
private String name;
private int num;

public Book(String name, int num) {
this.name = name;
this.num = num;
}
}

Map 接口遍历方法

下面看 Map 遍历方式案例演示 MapFor.java

1）keySet：查找键是否存在

2）values：获取所有的值

3）entrySet：获取所有关系k-v

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
Set keySet = map.keySet();
//（1）增强for
System.out.println("—–第一种方式——-");
for (Object key : keySet) {
System.out.println(key + "-" + map.get(key));
}
//（2）迭代器
System.out.println("—-第二种方式——–");
Iterator iterator1 = keySet.iterator();
while (iterator1.hasNext()) {
Object key = iterator1.next();
System.out.println(key + "-" + map.get(key));
}
}
}

//第二组：把所有的values取出
Collection values = map.values();
//这里可以使用所有的Collection 使用的方法
//（1）增强for
System.out.println("—取出所有的value 增强for—-");
for (Object value : values) {
System.out.println(value);
}

//（2）迭代器
System.out.println("—取出所有的value 迭代器—-");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
Object value = iterator2.next();
System.out.println(value);
}

//第三组：通过EntrySet 来获取
Set entrySet = map.entrySet();
System.out.println("—-使用EntrySet 的 for增强(第3种)—-");
for (Object obj : entrySet) {
Map.Entry entry = (Map.Entry) obj;
//System.out.println(entry);//其实直接这样就可以
System.out.println(entry.getKey() + "-" + entry.getValue());
}

System.out.println("—-使用EntrySet 的 迭代器(第4种)—-");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Object obj = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
//向下转型 Map.Entry
Map.Entry m = (Map.Entry) obj; //向下转型
System.out.println(m.getKey() + "-" + m.getValue());
}

Map 接口课堂练习

public class MapExercise {
public static void main(String[] args) {
Map map = new HashMap();
map.put("01", new Employee("hwl", 30000, "e01"));
map.put("02", new Employee("vae", 2000, "e02"));
map.put("03", new Employee("jack", 15000, "e03"));
map.put("03", new Employee("jack", 21000, "e03"));

// keySet – for
Set keySet = map.keySet();
for (Object key : keySet) {
Employee em = (Employee) map.get(key);
if (em.getSal() > 18000) {
System.out.println(em);
}
}

// EntrySet – 迭代器
Set set = map.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
Employee em = (Employee) entry.getValue();
if (em.getSal() > 18000) {
System.out.println(em);
}
}
}
}

class Employee {
private String name;
private double sal;
private String employId;
public Employee(String name, double sal, String employId) {
this.name = name;
this.sal = sal;
this.employId = employId;
}
// getter、setter方法
@Override
public String toString() {
return "Employee{" + "name='" + name + '\\'' + ", sal=" + sal + ", employId='" + employId + '\\'' + '}';
}
}

HashMap小结

1）Map接口的常用实现类：HashMap、HashTable 和 Properties

2）HashMap 是 Map 接口使用频率最高的实现类

3）HashMap 是以 key-val 对的方式来存储数据

4）key 不能重复，但是值可以重复，允许使用 null 键和 null 值

5）如果添加相同的 key，则会覆盖原来的 key-val，等同于修改（key不会替换，val会替换）

6）与 HashSet 一样，不保证映射的顺序，因为底层是以 哈希表的方式来存储的。（Jdk8的 HashMap 底层：数组+链表+红黑树）

7）HashMap 没有实现同步，因此线程是不安全的，方法没有做同步互斥的操作，没有 synchronized

HashMap底层机制及源码剖析

其实之前在 HashSet 那里已经讲的很详细了（HashSet 的底层就是 HashMap ），这里就不再细讲。

package com.hwledu.map_;
import java.util.HashMap;
public class HashMapSource1 {
@SuppressWarnings({"all"})
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("java", 10); //ok
map.put("php", 10); //ok
map.put("java", 20); //替换value
System.out.println(map);
}
}

执行过程分析：

1、执行构造器 new HashMap()
初始化加载因子 loadfactor = 0.75
HashMap$Node[] table = null
2、执行put 调用 hash方法，计算 key 的 hash 值 (h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) { // K = "java" value = 10
return putVal(hash(key), key, value, false, true);
}
3、执行 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; // 辅助变量
// 如果底层的table 数组为null, 或者 length =0 , 就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v, 创建成一个 Node ,加入该位置即可
if ((p = tab[i = (n – 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k; // 辅助变量
// 如果table的索引位置的key的hash相同和新的key的hash值相同，
// 并满足(table现有的结点的key和准备添加的key是同一个对象 || equals返回真)
// 就认为不能加入新的k-v
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
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);
//加入后，判断当前链表的个数，是否已经到8个，到8个，后就调用 treeifyBin 方法进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD – 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && //如果在循环比较过程中，发现有相同，就break，就只是替换value
((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; //替换，key对应value
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 每增加一个Node ,就size++
if (++size > threshold[12–24–48]) // 如size > 临界值，就扩容
resize();
afterNodeInsertion(evict);
return null;
}

5、关于树化(转成红黑树)
// 如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容。否则才会真正的树化 -> 剪枝
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
}

HashMap扩容树化触发

package com.hwledu.map_;
import java.util.HashMap;
public class HashMapSource2 {
@SuppressWarnings({"all"})
public static void main(String[] args) {
HashMap hashMap = new HashMap();
for (int i = 1; i <= 12; i++) {
hashMap.put(i, "hello");
}
hashMap.put("aaa", "bbb");
System.out.println("hashMap=" + hashMap); // 12个 k-v
// 布置一个任务，自己设计代码去验证，table 的扩容
// 0 -> 16(12) -> 32(24) -> 64(64*0.75=48)-> 128 (96) ->
// 自己设计程序，验证–> 增强自己阅读源码能力. 看别人代码.
}
}

class A {
private int num;
public A(int num) {
this.num = num;
}

// 所有的A对象的hashCode都是100
// @Override
// public int hashCode() {
// return 100;
// }

@Override
public String toString() {
return "\\nA{" + "num=" + num + '}';
}
}

Map接口实现类-Hashtable

（注意 table 的 t 是小写，与 HashMap 不一样）

1）存放的元素是键值对：即 K-V

2）Hashtable 的键和值都不能为 null，否则会抛出 NullPointerException

3）Hashtable 使用方法基本上和 HashMap 一样

4）Hashtable 是线程安全的（synchronized），HashMap 是线程不安全的

5）简单看下底层结构

package com.hwledu.map_;
import java.util.Hashtable;
public class HashtableExercise {
@SuppressWarnings({"all"})
public static void main(String[] args) {
Hashtable table = new Hashtable();//ok
table.put("john", 100); //ok
//table.put(null, 100); //异常 NullPointerException
//table.put("john", null);//异常 NullPointerException
table.put("lucy", 100); // ok
table.put("lic", 100); // ok
table.put("lic", 88); // 替换
table.put("hello1", 1);
table.put("hello2", 1);
table.put("hello3", 1);
table.put("hello4", 1);
table.put("hello5", 1);
table.put("hello6", 1);
System.out.println(table);

//简单说明一下Hashtable的底层
//1. 底层有数组 Hashtable$Entry[] 初始化大小为 11
//2. 临界值 threshold 8 = 11 * 0.75
//3. 扩容: 按照自己的扩容机制来进行即可.
//4. 执行 方法 addEntry(hash, key, value, index); 添加K-V 封装到Entry
//5. 当 if (count >= threshold) 满足时，就进行扩容
//5. 按照 int newCapacity = (oldCapacity << 1) + 1; 的大小扩容.
}
}

HashMap与Hashtable 对比

Map接口实现类–Properties

1）Properties 类继承自 Hashtable 类并且实现了 Map 接口，也是使用一种键值对的形式来保存数据

2）它的使用特点和 Hashtable 类似

3）Properties 还可用于从 xxx.properties 文件中，加载数据到 Properties 类对象，并进行读取和修改

4）说明：工作后 xxx.properties 文件通常作为配置文件，这个知识点在 I/O 流举例，有兴趣可以先看文章

​ https://www.cnblogs.com/xudong-bupt/p/3758136.html

package com.hwledu.map_;
import java.util.Properties;
public class Properties_ {
public static void main(String[] args) {
// 1、Properties 继承 Hashtable
// 2、可以通过 k-v 存放数据，当然 key 和 value 不能为 null
// 增加
Properties properties = new Properties();
// properties.put(null, "abc"); // 抛出空指针异常
// properties.put("abc", null); // 抛出空指针异常
properties.put("john", 100); // k-v
properties.put("lucy", 100);
properties.put("lic", 100);
properties.put("lic", 88);// 如果有相同的key，value被替换

System.out.println("properties=" + properties);

// 通过k 获取对应值
System.out.println(properties.get("lic")); // 88

// 删除
properties.remove("lic");
System.out.println("properties=" + properties);

// 修改
properties.put("john", "约翰");
System.out.println("properties=" + properties);
}
}

总结—开发中如何选择集合实现类（记住）

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：

1）先判断存储的类型（一组对象 [单列] 或 一组键值对 [双列]）

2）一组对象 [单列]：Collection 接口

​ 允许重复：List

​ 增删多：LinkedList [底层维护了一个双向链表]

​ 改查多：ArrayList [底层维护 Object 类型的可变数组]

​ 不允许重复：Set

​ 无序：HashSet [底层是HashMap，维护了一个哈希表 即（数组 + 链表 + 红黑树）]

​ 排序：TreeSet [后面讲]

​ 插入和取出顺序一致：LinkedHashSet，维护数组 + 双向链表

3）一组键值对 [双列]：Map

​ 键无序：HashMap [底层是：哈希表 jdk7时：数组 + 链表；jdk8时：数组 + 链表 + 红黑树]

​ 键排序：TreeMap [后面讲]

​ 键插入和取出顺序一致：LinkedHashMap

​ 读取文件：Properties

TreeSet

package com.hwledu.set_;
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSet_ {
@SuppressWarnings({"all"})
public static void main(String[] args) {
// 1.当我们使用无参构造器，创建 TreeSet 时，它会默认使用元素的自然顺序来排序
// 2.老师希望添加的元素，按照字符串大小来排序
// 3.使用 TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)(前面讲 Arrays 的 sort 方法时也讲过)，并指定排序规则
// 4.简单看看源码 ↓
/*
1.构造器把传入的比较器对象，赋给了 TreeSet 的底层的 TreeMap 的属性 this.comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
2.在调用 treeSet.add("tom"), 在底层会执行到
if (cpr != null) { // cpr 就是我们的匿名内部类(对象)
do {
parent = t;
// 动态绑定到我们的匿名内部类(对象)compare
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else // 如果相等，即返回 0，这个 Key 就没有加入
return t.setValue(value);
} while (t != null);
}
*/
// TreeSet treeSet = new TreeSet();
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 下面 调用 String 的 compareTo 方法进行字符串大小比较
// return ((String) o2).compareTo((String) o1);
// 如果老韩要求加入的元素，按照长度大小排序
return ((String) o1).length() – ((String) o2).length();
}
});
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("sp");
treeSet.add("a");
System.out.println(treeSet);
}
}

TreeMap

package com.hwledu.map_;
import java.util.Comparator;
import java.util.TreeMap;

public class TreeMap_ {
@SuppressWarnings({"all"})
public static void main(String[] args) {
// 使用默认的构造器，创建TreeMap, 是无序的(也没有排序)
// 老韩要求：按照传入的 k(String) 的大小进行排序
// TreeMap treeMap = new TreeMap();
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 按照传入的 k(String) 的大小进行排序
// 按照 K(String) 的长度大小排序
//return ((String) o2).compareTo((String) o1);
return ((String) o2).length() – ((String) o1).length();
}
});
treeMap.put("jack", "杰克");
treeMap.put("tom", "汤姆");
treeMap.put("kristina", "克瑞斯提诺");
treeMap.put("smith", "斯密斯");
treeMap.put("hsp", "韩顺平");//加入不了

System.out.println("treemap=" + treeMap);
/*
源码：
1. 构造器. 把传入的实现了 Comparator接口的匿名内部类(对象)，传给给TreeMap的comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
2. 调用put方法
2.1 第一次添加, 把k-v 封装到 Entry对象，放入root
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
2.2 以后添加
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do { //遍历所有的key , 给当前key找到适当位置
parent = t;
cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类的compare
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else // 如果遍历过程中，发现准备添加 Key 和当前已有的 Key 相等，就不添加
return t.setValue(value);
} while (t != null);
}
*/
}
}

Collections 工具类

1）Collections 是一个操作 Set、List 和 Map 等集合的工具类

2）Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

下面介绍 Collections 工具类的常用方法（2组）

排序操作（均为 static 方法）

package com.hwledu.collections_;
import java.util.ArrayList;
import java.util.List;

public class Collections_{
@SuppressWarnings({"all"})
public static void main(String[] args) {
//先创建 ArrayList集合 用于测试 (后面的方法均在此集合基础上进行)
List list = new ArrayList();
list.add("jack");
list.add("vae");
list.add("smith");
list.add("Christopher");
System.out.println("list = " + list);
}
}

//reverse(List)：反转 List 中元素的顺序
Collections.reverse(list);
System.out.println("list = " + list);

//shuffle(list)：对List 集合元素进行随机排序
for (int i = 0; i < 4; i++) {
Collections.shuffle(list);
System.out.println("list = " + list);
}

//sort(list)：根据元素的自然顺序对指定 List 集合元素按升序排序
Collections.sort(list);
System.out.println("自然排序后：");
System.out.println("list = " + list);

//sort(List, Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
// 我们希望按照字符串的长度大小进行排序
Collections.sort(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//可以加入校验代码.
return ((String)o1).length() – (((String)o2)).length();
}
});
System.out.println("按照字符串长度大小进行排序 list = " + list);

//swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
Collections.swap(list, 0, 1);
System.out.println("交换后的情况 list = " + list);

//Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
System.out.println("自然顺序最大元素 = " + Collections.max(list));

//Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
//比如，我们要返回长度最大的元素
Object maxObject = Collections.max(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).length() – ((String)o2).length();
}
});
System.out.println("长度最大的元素=" + maxObject);

//Object min(Collection)
//Object min(Collection，Comparator)
//上面的两个方法，参考max即可

List list = new ArrayList();
list.add("jack");
list.add("vae");
list.add("smith");
list.add("Christopher");
list.add("vae");

//int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
System.out.println("vae出现的次数=" + Collections.frequency(list, "vae"));

List list = new ArrayList();
list.add("jack");
list.add("vae");
list.add("smith");
list.add("Christopher");

//void copy(List dest, List src)：将src中的内容复制到dest中
ArrayList dest = new ArrayList();
//为了完成一个完整拷贝，我们需要先给dest 赋值，大小和list.size()一样，否则会报错
for (int i = 0; i < list.size(); i++) {
dest.add(" ");
}
//拷贝
Collections.copy(dest, list);
System.out.println("dest = " + dest);

List list = new ArrayList();
list.add("jack");
list.add("vae");
list.add("smith");
list.add("Christopher");
list.add("Christopher");

//boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 list 对象的所有旧值
//如果list中，有Christopher 就替换成 克里斯
Collections.replaceAll(list, "Christopher", "克里斯");
System.out.println("list替换后 = " + list);

一些值得记录的课后作业