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()	返回包含当前集合中所有元素的数组

方法示例:

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()	移除迭代器中返回的最后一个元素。

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对象

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;
    }

    @Override
    public String toString() {
        return "Book{name='" + name + '\'' + ", author=" + author + ", price=" + price + '}';
    }
}

BookIterator类

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 基本语法

for(元素类型 元素名: 集合名或数组名){ 
  	//访问元素
}

3.3.3 应用实例

遍历数组: 通常只进行遍历元素，不要在遍历的过程中对数组元素进行修改。

public class ForEach1 {
    public static void main(String[] args) {
        int[] arr = {3, 5, 6, 58, 100};
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

遍历集合: 通常只进行遍历元素，不要在遍历的过程中对集合元素进行增加、删除、替换操作。

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;
    }

    @Override
    public 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()	返回列表中元素的迭代器

使用示例

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 种。

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:增强for
        System.out.println("=======2.增强for========");
        for (String s : list) {
            System.out.println(s);
        }

        //方式3:普通for
        System.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倍

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 。

    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 倍

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);
    }
}

• ① 使用无参构造器

  • 1. 创建一个大小为10 的Object数组–>elementData
       
  • 2. 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
       
  • 3. 执行添加操作, 其执行过程如下:如果elementData容量够,则直接添加元素,否则进行扩容之后再进行元素的添加。
       

• ② 使用有参构造器

  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);
      }
  }
  

  • 1. 创建一个初始化大小为8的Object数组–>elementData
       
  • 2. 在添加元素的过程中, 首先进行装箱操作, 此示例将 int --> Integer
       
  • 3. 执行添加操作, 其执行过程如下:如果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 三个属性。双向链表的示意图见下图。

    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 对象 表示双向链表的一个结点

public class Node {
    public Object item; // 数据
    public Node next; // 指向后一个节点
    public Node prev; // 指向前一个节点

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

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

模拟双向链表的操作

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 --> siri
        jack.next = tom;
        tom.next = siri;
        // siri --> tom --> jack
        siri.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-->siri
        Node 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.添加元素

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节点移动,并指向最新插入的元素]的核心代码:

    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++;
    }

插入第一个元素的图解:

插入第二个元素图解:

2.移除元素

  remove 不带参数的移除方法就是移除集合中 first 节点指向的元素，并且 first 顺延指向下一个元素。主要功能还是 unlinkFirst 方法，将 first 头指针指向下一个元素，并将要移除的元素置空。

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);
    }
}

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。

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.使用增强 for
        System.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 对象）。

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 的无参构造

    // 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 Map
    private 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 16
	
	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;

    /**
     * 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 表明元素是否添加成功。

    /**
     * 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) {// null
        return 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@522
        return 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 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;
        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 = null
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // 此时oldCap = 0
        int oldThr = threshold; // 此时 threshold = 0 即 oldThr = 0
        int 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 threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 给 newCap,newThr 赋值
            // newCap 顾名思义 newCapacity，表示新数组的容量 赋值为大小等于 16 的静态常量
            newCap = DEFAULT_INITIAL_CAPACITY;
            // newThr，顾名思义，newThreshold，表示临界值,其值=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;// 此时 其值=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 order
                        Node<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;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab; // 返回 newTab:HashMap$Node[16]@555
    }

Q: 所谓的临界值"Threshold"到底有什么用？

① Threshold是门槛的意思，是java设计者提供的一个临界值。

② 临界值 = （向下转型) 增长因子 * 默认初始容量 = 0.75 * 16 = 12

③ 为了尽可能防止线程阻塞情况的发生。如果一直到table数组满16才扩容，当数组可用空间已经不多时，假如这时候有许多线程同时向集合中添加元素，就可能因为扩容不及时造成阻塞。假如数组已添加了12个元素，到达临界值，数组就要准备开始扩容，未雨绸缪，就不容易发生阻塞，即起到一个缓冲的作用。

在向tab数组中插入元素后, putVal方法执行完毕, modCount记录修改次数的变量, if语句是判断当前集合中元素的个数是否超过临界值, 如果超过临界值就准备对数组再次进行扩容。最终返回 null表示插入元素成功了。

③ 当再次向集合中添加元素 null 值时, 元素 null是重复元素, 在底层肯定会被’干掉’。当前只分析 putVal 方法的执行过程。

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=0
        Node<K,V>[] tab; Node<K,V> p; int n, ;
    	)//table=HasgMap$Node[16]@555,此时集合不为null,不进入if条件 
        if ((tab = table) == null || (n = tab.length) == 0
            n = (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 = 0
            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) 依次和该链表的每个元素比较的过程中,如果有相同的情况,就直接break
                    if (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 key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent:fasle
                    e.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中

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;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

    @Override
    public 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.源码剖析

示例代码:

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 对象。

// 调用 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) {//16
        int n = cap - 1; // n=15
        n |= 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^30
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;// 0.75
        this.threshold = tableSizeFor(initialCapacity); // threshold=16
    }
}

此时LinkedHashSet的属性如下图:

② 加入第一个元素 String 类型的 “CSDN”,最终 Hashmap中的put方法返回 null值, 表明元素已经插入成功。其中底层最终是调用的 HashMap 中的 putVal方法。 如下图所示:

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 = null
        if ((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) 依次和该链表的每个元素比较的过程中,如果有相同的情况,就直接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;
        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 = null
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldTab=null,则oldCap=0
        int oldThr = threshold; // threshold=16
        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 = 16,此时newCap = 16
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else { // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;//16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12
        }
    	// 此时 newThr = 0
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;// 16 * 0.75=12
            newThr = (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条件语句,直接返回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 order
                        Node<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;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
=========================================================================================
// 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, 说明元素插入成功。

源码执行过程如下:

// 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 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;
        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 属性。

  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[指向后一个节点] 属性, 形成双向链表。

  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 的底层机制图:

  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;
      }
  
      @Override
      public String toString() {
          return "Phone{" +
                  "name='" + name + '\'' +
                  '}';
      }
  
      @Override
      public int hashCode() {
          return 100;
      }
  }
  

  上述代码的机制图:
  

9.3.3 应用实例

需求: 定义 Car 类, 包含private属性 name 和 price, 如果 name 和 price 一样, 则认为是相同元素, 就不能添加。

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));//OK
        linkedHashSet.add(new Car("奥迪", 300000));//OK
        linkedHashSet.add(new Car("法拉利", 10000000));//OK
        linkedHashSet.add(new Car("奥迪", 300000));//加入不了
        linkedHashSet.add(new Car("保时捷", 70000000));//OK
        linkedHashSet.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;
    }

    @Override
    public String toString() {
        return "Car{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    //重写 equals 方法 和 hashCode
    //当 name 和 price 相同时， 就返回相同的 hashCode 值, equals 返回 true
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Car car = (Car) o;
        return price == car.price && Objects.equals(name, car.name);
    }

    @Override
    public 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()	根据键删除映射关系

使用示例

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 对应的 value
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);
        
        // 返回 key 对应的 value
        Integer 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);
        
        // 判断是否包含 key
        boolean containsApple = map.containsKey("apple");
        System.out.println("Contains key 'apple': " + containsApple);
        
        // 判断是否包含 value
        boolean containsValue2 = map.containsValue(2);
        System.out.println("Contains value 2: " + containsValue2);
    }
}

10.3 Map的遍历方式

  首先我们需要把 map 转换为 set 进行遍历，可使用 entrySet 和 keySet 共2种方式进行转换。每一种情况都可以使用 迭代器iterator()遍历；增强for循环遍历；forEach+lambda循环遍历，将循环简化。

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 取出对应的 Value
        Set<String> keySet = map.keySet();
        // ① 增强 for
        System.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:获取所有的value
        Collection<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-v
        System.out.println("=================方式3:EntrySet方式=========================");
        Set<Map.Entry<String,String>> entrySet = map.entrySet();
        // ① 增强for
        System.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底层机制与源码实现

示例代码:

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; 。

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()方法

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 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;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

================================第一次数组扩容=========================================
// 对数组第一次扩容,数组大小为 16, 执行成功后, 返回新数组(大小为16)
final Node<K,V>[] resize() {
    	// oldTab，见名知意，oldTable
        Node<K,V>[] oldTab = table;
   		// oldCap见名知意，oldCapacity
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
    	// 此时 threshold = 0 oldThr，见名知意，oldThreshold
        int 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 threshold
            newCap = oldThr;
    	// 此时代码进入else分支
        else {               // zero initial threshold signifies using defaults
            // newCap变量初始化为了16，并且将newThr变量初始化为了16 * 0.75 = 12
            newCap = 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 = 12
        threshold = 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 order
                        Node<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;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

④ [第一次插入元素] 回到 putVal 方法, 执行完 resize 方法, 返回大小为 16 的数组, 继续往下执行代码。 if条件语句中，利用获取到的key的哈希值，根据特定算法可以得到一个索引值i，该索引之当前键值对在table数组中应该存放的位置。显然，此处p不为空，所以会直接将当前键值对包装成Node类型，然后加入到table数组该索引处。

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 = 16
            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 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;
        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出去，放弃添加当前元素。

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 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)
                    //进行了值的替换，将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不一样）。

演示代码:

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 {
    @Override
    public int hashCode() {
        return 400;
    }
 
    @Override
    public String toString() {
        return "Fruit{}";
    }
}

对于条件①: table数组的某索引处的链表中，元素的个数达到或超过8个；

对于条件②: table数组本身的长度达到或超过64个。

                  for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // TREEIFY_THRESHOLD = 8
                        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;
                }

	//  当在某条链表下挂载的元素达到8后，会进入treeifyBin方法进行二次判断
	final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // MIN_TREEIFY_CAPACITY = 64
        if (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 处元素进行交换

@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>() {

            @Override
            public 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)	返回指定集合中指定元素的出现次数

@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"));// 1
        System.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 对象的所有旧值

@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 中

@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.总结