Java集合

目录

前言：

集合的特点：

 集合的分类：

Collection接口：

 概述:单列集合的顶级接口：

常用方法：

迭代器：

基本使用： 

迭代过程（从源码分析）：

​编辑

并发修改异常

List接口：

ArrayList：

常用方法：

注意点：

 ArrayList的创建和扩容（底层源码分析）：

创建：

这里就抛出了第一个注意点：

扩容：

总结一下：

LinkedList：

常用方法：

LinkedList的add方法（源码分析）：

 add方法：

 Collections：

 Collections和Collection的区别：

常用方法：

重点说一下这个：

1：定义Comparator接口是一个外部比较器接口

2：实现Comparable内部类接口

Set接口：

HashSet：

HashSet的去重机制：

LinkedHashSet：

TreeSet：

TreeSet的构造方法：

常用方法： 

哈希值：

哈希值概述和作用：

哈希值的计算：

这个时候我们有个问题？

还有一个问题：哈希表自身的哈希值是怎么算出来的呢？

Map接口：

HashMap：

特点：

稍微解释一下

HashMap常用方法：

HashMap的两种遍历方式：

1：先获取key再获取value：

2：同时获取key和value:

 哈希表结构存储过程（源码分析）：

加载因子：

resize()方法：

 总结：

TreeMap：

常用方法：

Java集合运用的例子： 

HashMap根据value的值进行排序：

二维数组的排列：

---

前言：

集合的概念：集合（Collection）是Java编程语言中一种非常重要的数据结构，用于存储和操作一组对象。在Java中，集合框架提供了一系列接口和类，用于表示和操作不同类型的集合，如列表（List）、集（Set）、映射（Map）等。

集合的特点：

  a.只能存储引用数据类型的数据
  b.长度可变
  c.集合中有大量的方法,方便我们操作

 集合的分类：

  a.单列集合:一个元素就一个组成部分:
    list.add("张三")
  b.双列集合:一个元素有两部分构成:  key 和 value
    map.put("涛哥","金莲") -> key,value叫做键值对

Collection接口：

 概述:单列集合的顶级接口：

常用方法：

boolean add(E e) : 将给定的元素添加到当前集合中(我们一般调add时,不用boolean接收,因为add一定会成功)
  boolean addAll(Collection c) :将另一个集合元素添加到当前集合中 (集合合并)
  void clear():清除集合中所有的元素
  boolean contains(Object o)  :判断当前集合中是否包含指定的元素
  boolean isEmpty() : 判断当前集合中是否有元素->判断集合是否为空
  boolean remove(Object o):将指定的元素从集合中删除
  int size() :返回集合中的元素个数。
  Object[] toArray(): 把集合中的元素,存储到数组中 

这些方法不用特殊去记，平常用到的时候就会记住了。

public class Demo01Collection {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        //boolean add(E e) : 将给定的元素添加到当前集合中(我们一般调add时,不用boolean接收,因为add一定会成功)
        collection.add("萧炎");
        collection.add("萧薰儿");
        collection.add("彩鳞");
        collection.add("小医仙");
        collection.add("云韵");
        collection.add("涛哥");
        System.out.println(collection);
        //boolean addAll(Collection<? extends E> c) :将另一个集合元素添加到当前集合中 (集合合并)
        Collection<String> collection1 = new ArrayList<>();
        collection1.add("张无忌");
        collection1.add("小昭");
        collection1.add("赵敏");
        collection1.add("周芷若");
        collection1.addAll(collection);
        System.out.println(collection1);
 
        //void clear():清除集合中所有的元素
        collection1.clear();
        System.out.println(collection1);
        //boolean contains(Object o)  :判断当前集合中是否包含指定的元素
        boolean result01 = collection.contains("涛哥");
        System.out.println("result01 = " + result01);
        //boolean isEmpty() : 判断当前集合中是否有元素->判断集合是否为空
        System.out.println(collection1.isEmpty());
        //boolean remove(Object o):将指定的元素从集合中删除
        collection.remove("涛哥");
        System.out.println(collection);
        //int size() :返回集合中的元素个数。
        System.out.println(collection.size());
        //Object[] toArray(): 把集合中的元素,存储到数组中
        Object[] arr = collection.toArray();
        System.out.println(Arrays.toString(arr));
    }
}

迭代器：

迭代器（Iterator）是Java中用来遍历集合（Collection）和容器（Container）对象的接口。迭代器提供了一种统一的方式访问集合中的元素，而不用暴露集合内部的结构。

迭代器通常包括以下几个常用方法：

1. hasNext(): 用于检查集合中是否还有下一个元素，如果有则返回true，否则返回false。

2. next(): 返回集合中的下一个元素，并将迭代器的位置向后移动。

3. remove(): 从集合中移除迭代器最后返回的元素（可选操作）。

基本使用： 

下面直接上一段代码来展示一下迭代器的基本使用:

public class Test01 {
    public static void main(String[] args) {
      ArrayList<String> list = new ArrayList<>();
     list.add("唐僧");
     list.add("孙悟空");
     list.add("猪八戒");
     list.add("沙僧");
 
     Iterator<String> iterator = list.iterator();
     while(iterator.hasNext()){
         String element = iterator.next();
         System.out.println(element);
     }
    }
}

 输出：

唐僧
孙悟空
猪八戒
沙僧

迭代过程（从源码分析）：

我们直接debug的形式进入

 

第一个：Itr：这个是ArrayList里面封装的一个内部类，实现了这个Iterator接口

---

第二个：cursor和lastRet是什么

我们根据后面的英文注释应该也能看出来

cursor：下一个要返回的元素的下标

lastRet：上一个返回元素的下标，没有就返回-1

---

第三个：next方法：就是返回集合下一个元素的方法

---

看到这里，我们也很容易分析出来，这个迭代过程就是通过两个下标指针的移动即可

并发修改异常

并发修改异常（ConcurrentModificationException）是指在使用迭代器遍历集合（如List、Set、Map等）的过程中，如果在迭代的过程中，通过集合的方法对集合的结构（增删元素）进行了修改，就会抛出并发修改异常。

说简单一点就是，有两个线程同时访问并且要修改这个集合的内容，这样就会导致结果不唯一。

说回迭代器，那这个迭代器是如何保证当有多个线程同时修改这个集合时，迭代器会抛出这个异常呢？

要想说明这个问题，我们需要模拟一个场景

还是用我们上面那个迭代器的例子，当我们遍历到这个猪八戒的时候，往这个list集合中插入一条记录：小白龙，这样就修改了集合的内容

当我们修改之后，控制台马上抛出了异常

我们还是打断点进去

我们在next这个方法打断点进去

 

最关键的就是这个方法：

 

我们点击这个方法，会发现有两个变量：

modCount和expectedModCount

我们发现抛出异常的原因就是因为这两个变量不同

那我们再找找这两个变量是什么

这两个变量是内部类Itr初始化好的，一开始就相同的两个量：

modCount：modCount是ArrayList类中的一个变量，它记录了对ArrayList结构进行修改的次数 

这个可以理解为：实际操作次数

expectedModCount：expectedModCount是Itr迭代器类中的一个变量，它记录了迭代器创建时ArrayList的modCount值

这个可以理解为：预期操作次数

 那问题就来了，明明一开始都已经相同了，那为什么后来就不同了呢？

我们点击list.add这个方法

从这里我们就能知道，当添加元素之后，这个modCount的值就会发生改变

---

有了这两个概念，我们就差不多可以推断出来了，在创建这个迭代器的时候，我们就初始化好了这两个值，并且相等，不过如果有其它线程改变了这个集合（crud）

那就好抛出并发修改异常这个问题。

通过这种机制，Java能够在迭代过程中检测到其他线程对集合进行的结构性修改，从而保证迭代的安全性。这种设计可以有效防止在迭代过程中出现并发修改导致的数据不一致性或异常情况。

---

最后讲一下怎么解决：

其实这个并发修改异常本身就是一个异常

其它线程去修改集合的值或者结构本来就是一件错误的事情，所以，不需要解决

List接口：

是Collection接口的子接口

常见的实现类:   ArrayList LinkedList

ArrayList：

ArrayList是List接口的实现类

特点：

1. 有索引 ：可以根据索引来操作元素
2. 线程不安全
3. 底层数据结构是数组
4. 元素可重复

常用方法：

package c_List;
 
import java.util.ArrayList;
import java.util.List;
 
public class Test01 {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();
        list.add("铁胆火车侠");
        list.add("喜洋洋");
        list.add("火影忍者");
        list.add("灌篮高手");
        list.add("网球王子");
//        boolean add(E e)  -> 将元素添加到集合中->尾部(add方法一定能添加成功的,所以我们不用boolean接收返回值)
        list.add("abab");
        System.out.println(list);
//        void add(int index, E element) ->在指定索引位置上添加元素
        list.add(1,"保安保安");
        System.out.println(list);
//        boolean remove(Object o) ->删除指定的元素,删除成功为true,失败为false
        list.remove("abab");
        System.out.println(list);
//        E remove(int index) -> 删除指定索引位置上的元素,返回的是被删除的那个元素
        Object remove = list.remove(2);
        System.out.println(remove);
        System.out.println(list);
//        E set(int index, E element) -> 将指定索引位置上的元素,修改成后面的element元素,并且返回被修改的元素
        Object object = list.set(0, "aabb");
        System.out.println(object);
        System.out.println(list);
//        E get(int index) -> 根据索引获取元素
        System.out.println(list.get(3));
//        int size()  -> 获取集合元素个数
        System.out.println(list.size());
    }
}

输出：

[铁胆火车侠, 喜洋洋, 火影忍者, 灌篮高手, 网球王子, abab]
[铁胆火车侠, 保安保安, 喜洋洋, 火影忍者, 灌篮高手, 网球王子, abab]
[铁胆火车侠, 保安保安, 喜洋洋, 火影忍者, 灌篮高手, 网球王子]
喜洋洋
[铁胆火车侠, 保安保安, 火影忍者, 灌篮高手, 网球王子]
铁胆火车侠
[aabb, 保安保安, 火影忍者, 灌篮高手, 网球王子]
灌篮高手
5

注意点：

我们看一个案例：

我们创建了一个泛型为Integer的ArrayList集合，然后我们往里存了一个2，我们调用remove方法中的删除指定元素的方法，竟然被报了越界异常

原因很简单：remove方法中也有一个默认索引的方法，我们直接传一个2进去默认是调用删除索引为2的那个元素值，这个集合只有一个元素，所以肯定不到2，所以直接报了越界处理

解决办法：

我们需要把这个2转化成Integer的包装类：Integer.valueOf(2)

 

 ArrayList的创建和扩容（底层源码分析）：

创建：

ArrayList构造方法:
  a.ArrayList() 构造一个初始容量为十的空列表
  b.ArrayList(int initialCapacity) 构造具有指定初始容量的空列表 

 还是老规矩，打断点进入：

 

进来之后我们看到两个变量：

element：这个就是我们底层的数组

DataDEFAULTCAPACITY_EMPTY_ELEMENTDATA这个是默认的空数组

 我们再这接着点一下，发现我们这个数组就初始化完了

那肯定有一个疑问，这个数组的长度是多少呢？

这里就抛出了第一个注意点：

不是一new底层就会创建初始容量为10的空列表,而是第一次add的时候才会创建初始化容量为10的空列表

我们可以接着往后继续debug

我们进入ArrayList的add方法

我们再进add方法中的add方法

 发现这里有一个grow

不过我们也要先判断一下，这个e：就是我们添加进来的元素 ：a

这个elementData就是我们底层的数组，刚才上面说了，这个时候这个底层数组是个空数组，没有元素

最后是这里的s：根据我们上一层的add方法，我们也能发现这是一个size

我们再进入两次grow方法，我们最后发现了这个数组大小的设置方法

这个方法也是后面ArrayList的扩容机制

我们仔细分析一下

首先先获取这个oldCapacity，这个肯定是0，因为我们还没往里面添值

然后进入两个判断：

oldCapacity > 0 这个很明显是false

下一个是：elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这个的作用就是：当判断elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，并不是表示要扩容的大小，而是表示数组elementData已经被用于存放元素，不再是用来标记默认容量为空的DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这个我感觉有点说法

首先我们在ArrayList构造方法中：

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

把当前底层数组赋值个了这个默认的空数组

我们知道，扩容的本质其实是copyOf这个方法，这个方法建了深拷贝了一个数组，然后将新建的数组赋值给这个当前底层数组，那这是时候elementData的地址其实就发生了改变，这个时候，我们的底层数组就已经不是这个默认的空数组了。

---

说了这么多，那我们肯定知道，我们现在还没对这个数组进行修改。

所以我们这个时候elementData还是等于原来的那个默认空数组的，所以这个条件也是false

就进入了这个else逻辑中

else的逻辑就非常简单，当你判断完现在的数组还是默认的空数组，说明没有被改动过

return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];

直接返回一个新的数组，DEFAULT_CAPACITY是10，如果你现在给进来的值比10大，那就取你的给进来的值，我们这里传进去的是一个a，长度只有1，所以，取默认值就行

扩容：

我们从上面的分析中得知，默认长度为10，那我们想要扩容，我们就得超过10，所以，这里我添加了11个元素。

我们再次进入

我们还是咔咔咔点到那个熟悉的grow方法：

就会进入这个newLength方法

我们会看到这个方法有三个值：

oldLength就是当前的底层数组的长度

minGrowth就是需要扩容的最小长度

preGrowth就是默认的扩容大小

 这一段代码和StringBuilder的扩容逻辑Java的字符串-CSDN博客一样

不过这里的preGrowth不一样，在ArrayList中传入的默认的扩容大小是原数组长度的一半

意思就是扩容之后的数组长度会变成原来的1.5倍。

至此源码分析完毕。

---

总结一下：

1：不是一new底层就会创建初始容量为10的空列表,而是第一次add的时候才会创建初始化容量为10的空列表
2：ArrayList底层是数组,那么为啥还说集合长度可变呢?
    ArrayList底层会自动扩容-> Arrays.copyOf    
3：扩容多少倍?
    1.5倍

LinkedList：

LinkedList是List接口的实现类

特点：

1. 无索引
2. 线程不安全
3. 底层数据结构是双向链表
4. 元素可重复

常用方法：

直接上一段代码：

public class Demo05LinkedList {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("吕布");
        linkedList.add("刘备");
        linkedList.add("关羽");
        linkedList.add("张飞");
        linkedList.add("貂蝉");
        System.out.println(linkedList);
 
        linkedList.addFirst("孙尚香");
        System.out.println(linkedList);
 
        linkedList.addLast("董卓");
        System.out.println(linkedList);
 
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
 
        linkedList.removeFirst();
        System.out.println(linkedList);
 
        linkedList.removeLast();
        System.out.println(linkedList);
 
        System.out.println("======================");
 
        Iterator<String> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
 
        System.out.println("=======================");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

LinkedList的add方法（源码分析）：

首先在讲add方法的时候，我们需要先来看一下LinkedList的成员和Node（结点）的成员

1.LinkedList底层成员
  transient int size = 0;  元素个数
  transient Node first; 第一个节点对象
  transient Node last;  最后一个节点对象
  
2.Node代表的是节点对象
   private static class Node {
        E item;//节点上的元素
        Node next;//记录着下一个节点地址
        Node prev;//记录着上一个节点地址

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

 add方法：

还是老规矩debug

 

这段代码的逻辑：

首先先新建一个结点l，将这个时候的last赋值给这个l，这个last是 这个链表的最后一个结点

然后这就新建了一个结点

这里分别有三个参数，

prev指向这个结点的前一个结点

item就是这个结点的值

next指向这个结点的后一个结点

然后我们回到原来的逻辑：

将这个新的结点赋值给这个链表的最后一个结点

然后我们看下一行的判断，如果这个l是null，那就将头结点指向这个新结点

这个是什么意思？

就是判断我们是否是第一个结点

我们想，如果我们是第一个结点，这个链表的第一个结点对象和最后一个都是第一个结点。

当我们传入的结点的值是b的时候，这个时候就会利用到链表的尾插法了

 

我们用last指向b元素 ，l指向a元素 

当我们创建新的结点的时候，我们把l传进去了，在创建这个新的结点的时候，我们将a做为我们的前一个结点

我们仔细看这两个地址值：

730是a元素的地址值

745是b元素的地址值

接着我们判断l == null  --->判断现在插入的元素是否是第一个元素

很显然不是：

接着：l.next = newNode

a的下一个元素指向b

如图：

 至此这个双向链表就接上了。

 Collections：

 Collections和Collection的区别：

Collection是接口，是所有集合的父接口，里面提供了集合的增删改查的接口

Collections是工具类，它提供了对集合类操作的一些静态方法（类名直接调用），比如排序、查找、替换等，提高开发效率

常用方法：

  static boolean addAll(Collection c, T... elements)->批量添加元素 
  static void shuffle(List list) ->将集合中的元素顺序打乱
  static void sort(List list) ->将集合中的元素按照默认规则排序
  static void sort(List list, Comparator c)->将集合中的元素按照指定规则排序 

---

addAll()方法：

        ArrayList<String> list = new ArrayList<>();
        //static <T> boolean addAll(Collection<? super T> c, T... elements)->批量添加元素
        Collections.addAll(list,"张三","李四","王五","赵六","田七","朱八");
        System.out.println(list);

shuffle()方法内部实现了洗牌算法洗牌算法理解-CSDN博客

还有这个sort，如果没有指定排序方式是默认升序排序，如果是字符串的话就是根据ASCII码表

重点说一下这个：

static void sort(List list, Comparator c)->将集合中的元素按照指定规则排序 

 这个方法的主要作用就是将集合中的元素按照我们指定的规则排序

比较规则：

int compare(T o1,T o2)
                o1-o2 -> 升序
                o2-o1 -> 降序   

方法: int compareTo(T o) -> this-o (升序)   o-this(降序)

下面有两种方法：

1：定义Comparator接口是一个外部比较器接口

看下面这段代码：

package e_Collections;
 
public class Person {
    private String name;
    private int age;
 
    public Person(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 "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

        ArrayList<Person> list = new ArrayList<>();
        list.add(new Person("a",18));
        list.add(new Person("b",16));
        list.add(new Person("c",20));
        Collections.sort(list, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o1.getAge()- o2.getAge();
            }
        });
        System.out.println(list);

我创建了一个类Person，里面实现了一些JavaBean的方法

然后我在测试类中创建了一个列表list 

Collection.sort中用了一个使用匿名内部类的方式创建了一个Comparator对象的实例

在重写的compare方法中规定了比较的规则。升序排列。

输出结果：

[Person{name='b', age=16}, Person{name='a', age=18}, Person{name='c', age=20}]

2：实现Comparable内部类接口

package e_Collections;
 
public class Student implements Comparable<Student>{
    private String name;
    private int score;
 
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public int getScore() {
        return score;
    }
 
    public void setScore(int score) {
        this.score = score;
    }
 
    @Override
    public int compareTo(Student o) {
        return this.getScore()-o.getScore();
    }
 
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
}

        ArrayList<Student> studentArrayList = new ArrayList<>();
        studentArrayList.add(new Student("a",100));
        studentArrayList.add(new Student("b",10));
        studentArrayList.add(new Student("c",110));
        Collections.sort(studentArrayList);
        System.out.println(studentArrayList);

我创建了一个类Student实现了Comparable接口

并且重写了compareTo方法

在测试类中直接Collection.sort对学生列表进行排序。

输出结果：

[Student{name='b', score=10}, Student{name='a', score=100}, Student{name='c', score=110}]

 这里我顺带说一下：

我们点到String类中

String也实现了这个Comparable接口。 

Set接口：

常用的实现类：HashSet 和 LinkedHashSet

Set和Map密切相关的
Map的遍历需要先变成单列集合,只能变成set集合

为什么说和Map密切相关：

当我们创建一个HashSet对象，点进来竟然是一个HashMap对象

 LinkedHashSet点进来也是LinkedHashMap

HashSet：

1：特点:
          a.元素唯一（HashSet有去重机制）
          b.元素无序（所谓元素无需，其实是因为哈希表的存储方式是根据元素的哈希码来确定存储位置，和后面的hasCode有关
          c.无索引（没有提供索引的方法，用增强for和迭代器遍历即可）
          d.线程不安全
2：数据结构:哈希表
          a.jdk8之前:哈希表 = 数组+链表
          b.jdk8之后:哈希表 = 数组+链表+红黑树
                    加入红黑树目的:查询快
3：方法:和Collection一样
4：遍历:
          a.增强for
          b.迭代器

HashSet的去重机制：

HashSet的存储去重复的过程

先计算元素的哈希值(重写hashCode方法),再比较内容(重写equals方法)

这个很好理解我们来看下面这段代码

public class Test02 {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("abc");
        set.add("通话");
        set.add("重地");
        set.add("abc");
        System.out.println(set);//[通话, 重地, abc]
 
    }
}

首先我们往这个HashSet中插入了两个abc

String重写了hasCode方法，这两个abc算出的哈希值是相同的，所以，HashSet会去重，就只会记录一个abc

接着就是一个比较离谱的点了："重地"和"通话"这两个字符串的哈希值相同，这个问题我也问了GPT，应该就是计算哈希值的时候，刚刚碰巧算出来相同。

这两个字符串的哈希值相同，HashSet就会用equals去比较这两个字符串的内容，发现不一样，也会去重。

LinkedHashSet：

这个也是一个Set接口的实现类。

1：特点:
          a.元素唯一
          b.元素有序
          c.无索引
          d.线程不安全
2：数据结构:
          哈希表+双向链表
3：使用:和HashSet一样 

使用起来差不多，不过多赘述

TreeSet：

TreeSet是一个Set接口的实现类 

它基于红黑树（Red-Black Tree）实现，可以保持元素的自然顺序或者指定的顺序进行排序

TreeSet和Set集合最大的一个不同点就是有序

TreeSet的构造方法：

  TreeSet() -> 构造一个新的空 set，该 set 根据其元素的自然顺序进行排序 -> ASCII 
  TreeSet(Comparator<? super E> comparator)构造一个新的空 TreeSet，它根据指定比较器进行排序  

我们从这个构造方法也能看出来，我们可以用Comparator接口来指定TreeSet的排序规则

常用方法： 

1. add(E e): 向TreeSet中添加元素e。
2. remove(Object o): 从TreeSet中移除指定的元素o。
3. contains(Object o): 判断TreeSet中是否包含指定元素o。
4. first(): 返回TreeSet中的第一个元素（最小的元素）。
5. last(): 返回TreeSet中的最后一个元素（最大的元素）。
6. iterator(): 返回TreeSet的迭代器，可以遍历TreeSet中的元素。

哈希值：

在上面反复出现了一个概念：哈希值，这到底是什么嘞？

哈希值概述和作用：

概述:是由计算机算出来的一个十进制数,可以看做是对象的地址值

那这个算出来的地址值有什么用呢？

首先我们知道：哈希表的存储方式是根据元素的哈希码来确定存储位置的

每个对象都有一个 hashCode() 方法，该方法用于计算对象的哈希码（hash code）

每个对象如果要存储到哈希表中，哈希表根据这个hashCode方法算出来的哈希值快速找到这个元素应该存在哪里。

哈希值的计算：

以字符串abc举例：

我们直接按照ctrl进入这个hashCode方法

这里有两个变量 ：hash和hashIsZero

我们不需要太去管只需要知道这两个变量的默认值，并且这个判断条件为真即可 根据下面那个三目运算，我们知道我们会进入StringLatin1.hashCode(value)这个方法

直接跑到StringLatin1.hashCode(value)底层源码,计算abc的哈希值-> 0xff这个十六进制对应的十进制255
任何数据和255做&运算,都是原值
    
第一圈:
  h = 31*0+97 = 97
第二圈:
  h = 31*97+98 = 3105
第三圈:
  h = 31*3105+99 = 96354

问题:在计算哈希值的时候,有一个定值就是31,为啥?
     31是一个质数,31这个数通过大量的计算,统计,认为用31,可以尽量降低内容不一样但是哈希值一样的情况
    
     内容不一样,哈希值一样(哈希冲突,哈希碰撞)

 这样就能算出哈希值了

这个时候我们有个问题？

我们在上面知道如果单纯的去比哈希值，有可能会出现上面"重地"和"通话"这种值不一样，但哈希值一样的bug，那为什么String还要去重写hashCode方法呢？

原因：提高了哈希表的效率

字符串类重写了 hashCode() 方法，使得其哈希码根据字符串的内容计算得到，这样相同内容的字符串将会有相同的哈希码，有利于提高哈希表的性能。

换句话说，如果你要把这个字符串存到哈希表中，重写了这个方法就会快很多。

---

还有一个问题：哈希表自身的哈希值是怎么算出来的呢？

首先我们看这端代码：

package a_set;
 
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
 
public class Test01 {
    public static void main(String[] args) {
        LinkedHashSet<String> set1 = new LinkedHashSet<>();
        HashSet<String> set = new HashSet<>();
        set.add("张三");
        set.add("李四");
        set.add("王五");
        set.add("赵六");
        set.add("田七");
        set.add("张三");
        System.out.println(set.hashCode());
        System.out.println("========================");
        HashSet<String> set2 = new HashSet<>();
        set2.add("张三");
        set2.add("李四");
        set2.add("王五");
        set2.add("赵六");
        set2.add("田七");
        set2.add("张三");
        System.out.println(set2.hashCode());
    }
}

算出这两个HashSet的哈希值是一样的

我一开始以为是HashSet重写了hashCode方法，点进去其实没有

然后我就问了GPT：

HashSet 的 hashCode() 方法会根据集合中的元素来计算一个整体的哈希值。这个哈希值是根据集合中的每个元素的哈希值进行计算的，从而保证 HashSet 对象整体的哈希值能够唯一区分不同的 HashSet 对象实例。

理解起来就是，哈希表的哈希值是由哈希表中存的元素来决定的。所以这两个元素相同的哈希表的哈希值才相同 

Map接口：

概述:是双列集合的顶级接口

HashMap：

特点：

          a.key唯一,value可重复 -> 如果key重复了,会发生value覆盖
          b.无序
          c.无索引
          d.线程不安全
          e.可以存null键null值

稍微解释一下

a.如何保证这个key唯一呢？

在将HashSet的去重机制的时候，我们看过源码，创建HashSet就等于创建了一个HashMap

所以，这里的HashMap的去重机制和HashSet是一样的

先比较哈希值（hashCode），再比较内容（equals）

这也能给我们一点启发，如果我们想自定义类来充当HashMap的key，我们也要重写hashCode和equals方法

b.怎么理解无序呢？

所谓元素无序，其实是因为哈希表的存储方式是根据元素的哈希码来确定存储位置

每个元素内容的不同算出来来的hashCode也不同。

c.为什么说是无索引？

我们知道HashMap底层是由数组+哈希表+红黑树组成的，

那既然有数组那为什么会说HashMap是无索引的呢

因为HashMap中的数组每个元素上有可能是链表，如果2索引上有一条链表,那么我们要是按照索引2获取,咱们获取哪个元素呢?所以就取消了按照索引操作的机制

HashMap常用方法：

方法:
  V put(K key, V value)  -> 添加元素,返回的是
  V remove(Object key)  ->根据key删除键值对,返回的是被删除的value
  V get(Object key) -> 根据key获取value
  boolean containsKey(Object key)  -> 判断集合中是否包含指定的key
  Collection values() -> 获取集合中所有的value,转存到Collection集合中
      
  Set keySet()->将Map中的key获取出来,转存到Set集合中  
  Set> entrySet()->获取Map集合中的键值对,转存到Set集合中 

HashMap的两种遍历方式：

1：先获取key再获取value：

 Set keySet()->将Map中的key获取出来,转存到Set集合中  

看代码即可：

public class Demo03HashMap {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("猪八", "嫦娥");
        map.put("猪八", "高翠兰");
        map.put("后裔","嫦娥");
        map.put("二郎神","嫦娥");
        map.put("唐僧","女儿国国王");
        map.put("涛哥","金莲");
 
        Set<String> set = map.keySet();//获取所有的key,保存到set集合中
        for (String key : set) {
            //根据key获取value
            System.out.println(key+".."+map.get(key));
        }
 
    }
}

2：同时获取key和value:

 Set> entrySet()->获取Map集合中的键值对,转存到Set集合中

public class Demo04HashMap {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("猪八", "嫦娥");
        map.put("猪八", "高翠兰");
        map.put("后裔","嫦娥");
        map.put("二郎神","嫦娥");
        map.put("唐僧","女儿国国王");
        map.put("涛哥","金莲");
 
        /*
          Set集合中保存的都是"结婚证"-> Map.Entry
          我们需要将"结婚证"从set集合中遍历出来
         */
        Set<Map.Entry<String, String>> set = map.entrySet();
        for (Map.Entry<String, String> entry : set) {
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key+"..."+value);
        }
    }
}

 哈希表结构存储过程（源码分析）：

先贴一个哈希表存储过程中的常用变量：

default_initial_capacity:HashMap默认容量  16
default_load_factor:HashMap默认加载因子   0.75f
threshold:扩容的临界值   等于   容量*0.75 = 12  第一次扩容
treeify_threshold:链表长度默认值,转为红黑树:8
min_treeify_capacity:链表被树化时最小的数组容量:64

 创建HashMap

因为HashMap底层数据数据结构:哈希表

所以我们这里分析哈希表结构的存储过程的时候，直接用HashMap

 

我们按住ctrl进去之后，我们发现无参创建HashMap对象的时候就只做了一件事 

定义了这个加载因子：

加载因子：

加载因子的主要作用就是用来确定哈希表的大小和什么时候进行扩容

公式：加载因子 = 元素数量 / 哈希表容量

并且这个加载因子不管后续如何扩容都是不会发生改变的

所以我们可以由这个公式推出，当哈希表的容量到12的时候，哈希表就会自动扩容

回归我们的代码：

我们发现我们创建HashMap对象的时候，好像就初始化了这个加载因子，并没有创建底层的数组

其实哈希表真正有底层数组的时候是调用put方法。

我们还是打断点进去：

我们进来之后就会发现这个put方法调用了一个putVal方法，里面还有一个hash方法，这个hash方法就是算一下这个key（abc）的哈希值 ： 96355

我们进入putVal方法：

我们会发现有一个tab数组，这应该就是底层数组

然后还有一个table数组，这个默认是空数组

因为我们这个数组什么都没有，我们肯定是null，所以判断条件肯定为真

接着我们进入resize()方法

resize()方法：

resize方法是用来进行哈希表的扩容操作的。当HashMap中的元素数量达到扩容阈值时，HashMap会调用resize方法来对哈希表进行扩容

我们看resize()方法的中扩容计算部分的源码：

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
}

我们判断如果这个时候哈希表村存储的元素已经超过阈值了，我们就要去扩容，

扩容多少呢？

newThr = oldThr << 1

扩容两倍

 接着往下走：

前面两个if都可以跳过

到了这个else，

我们可以知道新容量就是默认容量

这个newThr就是一个阈值，由加载因子算出来的阈值，用于判断现在是否需要扩容

我们发现这个阈值就是用默认长度*加载因子

到这一步确定好了底层数组的容量，就可以创建新的数组了newTab

返回新的数组之后，我们就继续回到putVal

这个时候，我们就有一个疑问了，这个abc这个元素存在这个数组的什么地方？

 就是通过和hash值进行与运算得出。

tab[i] = newNode(hash, key, value, null);->将元素放在数组中  i就是索引

 i = (n - 1) & hash
     0000 0000 0000 0000 0000 0000 0000 1111->15
                                                    &   0&0=0 0&1=0 1&1=1
     0000 0000 0000 0001 0111 1000 0110 0011->96355
--------------------------------------------------------
     0000 0000 0000 0000 0000 0000 0000 0011->3

这里的i就是数组的下标

至此插入第一个元素就完成了。

当我们要往里面插第二个元素的时候，这时的tab就不是null了

第二个元素下标：

     0000 0000 0000 0000 0000 0000 0000 1111->15
                                                    &   0&0=0 0&1=0 1&1=1
     0000 0000 0001 0001 1111 1111 0001 0010->1179410
--------------------------------------------------------
     0000 0000 0000 0000 0000 0000 0000 0010->2

 总结：

1. 在不指定长度时,哈希表中的数组默认长度为16,HashMap创建出来,一开始没有创建长度为16的数组，一开始只赋值了一个加载因子
2.   什么时候创建的长度为16的数组呢?在第一次put的时候,底层会创建长度为16的数组
3.   哈希表中有一个[加载因子]->默认为0.75(加载因子)->代表当元素存储到百分之75的时候要扩容了->2倍
4.   如果对个元素出现了哈希值一样,内容不一样时,就会在同一个索引上以链表的形式存储,当链表长度达到8并且当前数组长度>=64时,链表就会改成使用红黑树存储
5.     如果后续删除元素,那么在同一个索引位置上的元素个数小于6,红黑树会变回链表
6.   加入红黑树目的:查询快

TreeMap：

这个就先简单介绍一下，我感觉我都没咋用过这个数据结构

这个TreeMap的理解可以和上面的TreeSet一样

TreeMap中的键是有序的，按照升序排序。如果使用自定义比较器，则按照比较器定义的顺序排序

常用方法：

1. put(K key, V value): 向TreeMap中插入键值对。
2. remove(Object key): 从TreeMap中移除指定键对应的值。
3. get(Object key): 获取指定键对应的值。
4. firstKey(): 返回TreeMap中的第一个键。
5. lastKey(): 返回TreeMap中的最后一个键。
6. keySet(): 返回TreeMap中所有键的集合。

---

Java集合运用的例子： 

写道这里整体的Java集合中知识点我已经写完啦

下面分享几个我在写算法题的时候，看到别人的对集合的一些高端操作把

HashMap根据value的值进行排序：

package a_map;
 
import java.util.ArrayList;
import java.util.*;
 
public class Test01 {
    public static void main(String[] args) {
        //HashMap根据value的值进行排序：
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(2, 25);
        hashMap.put(3, 30);
        hashMap.put(5, 20);
        hashMap.put(8, 35);
        ArrayList<Map.Entry<Integer, Integer>> arrayList = new ArrayList>(hashMap.entrySet());
        Collections.sort(arrayList, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue()-o2.getValue();
            }
        });
        System.out.println(arrayList);
    }
}

这段代码的整体逻辑就是：从需求出发，

我们要对HashMap根据value的值进行排序，根据HashMap的遍历方式中我们想到了一种方法

获得HashMap的entrySet对象，这个对象里就有value的值，

然后再开一个列表存储HashMap的entrySet对象

然后利用Collections的sort方法，重写比较器接口，定义规则即可

输出：

[5=20, 2=25, 3=30, 8=35]

二维数组的排列：

package a_map;
 
import java.util.ArrayList;
import java.util.*;
 
public class Test01 {
    public static void main(String[] args) {
        int[][] intervals = {{2,3},{5,5},{2,2},{3,4},{3,4}};
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        for (int[] interval : intervals) {
            for (int i : interval) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}

输出：

2 3 
2 2 
3 4 
3 4 
5 5