Java-集合框架（刨析源码，深层讲解）

╰半夏微凉° 2024-04-28 08:11 110阅读 0赞

#### Java 集合框架 ####

*  前言
 *   *  一、引入
     *  二、概述
     *  三、Collection接口
     *   *  1. 概述
         *  2. 方法
         *   *  2.1 添加
             *  2.2 获取有效元素的个数
             *  2.3 清空集合
             *  2.4 判断是否是空集合
             *  2.5 判断是否包含某个元素
             *  2.6 删除
             *  2.7 取两个集合的交集
             *  2.8 判断集合是否相等
             *  2.9 转成对象数组
             *  2.10 获取集合对象的哈希值
             *  2.11 遍历
             *  2.12 代码演示
         *  3. Collection子接口之一：List接口
         *   *  3.1 概述
             *  3.2 方法
             *   *  3.2.1 代码演示
             *  3.3 List实现类之一：ArrayList
             *   *  3.3.1 概述
                 *  3.3.2 源码分析
             *  3.4 List实现类之二：LinkedList
             *   *  3.4.1 概述
                 *  3.4.2 源码分析
             *  3.5 List实现类之三：Vector
             *   *  3.5.1 概述
                 *  3.5.2 源码分析
             *  3.6 ArrayList、LinkedList、Vector三者的异同？
         *  4. Collection子接口之二：Set接口
         *   *  4.1 概述
             *  4.2 Set实现类之一：HashSet
             *   *  4.2.1 概述
                 *  4.2.2 添加元素的过程
                 *  4.2.3 代码演示
             *  4.3 Set实现类之二：LinkedHashSet
             *   *  4.3.1 概述
                 *  4.3.2 代码演示
             *  4.4 Set实现类之三：TreeSet
             *   *  4.4.1 概述
                 *  4.4.2 排序---自然排序
                 *  4.4.3 排序---定制排序
                 *  4.4.4 代码演示
     *  四、Map接口
     *   *  1. 概述
         *  2. Map中定义的方法
         *   *  2.1 代码演示
         *  3. Map实现类之一：HashMap
         *   *  3.1 概述
             *  3.2 HashMap 的底层实现原理
             *  3.3 HashMap 源码中的重要常量
             *  3.4 HashMap的存储结构：JDK 1.8之前
         *  4. Map实现类之二：LinkedHashMap
         *   *  4.1 概述
             *  4.2 底层结构
         *  5. Map实现类之三：TreeMap
         *   *  5.1 概述
             *  5.2 代码演示
         *  6. Map实现类之四：Hashtable
         *   *  6.1 概述
         *  7. Map实现类之四：Properties
         *   *  7.1 概述
             *  7.2 代码演示
     *  五、 Collections工具类
     *   *  1. 概述
         *  2. Collections工具类方法
         *  3. 代码演示

--------------------

## 前言 ##

本博主将用CSDN记录软件开发求学之路上亲身所得与所学的心得与知识，有兴趣的小伙伴可以关注博主！  
也许一个人独行，可以走的很快，但是一群人结伴而行，才能走的更远！让我们在成长的道路上互相学习，欢迎关注！

### 一、引入 ###

> （1） 一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。

> （2）另一方面，使用`Array`存储对象方面具有一些弊端，而Java集合就像一种容器，可以动态地把多个对象的引用放入容器中。
> 
> ⭕ 数组在内存存储方面的特点：
> 
>  *  数组初始化以后，长度就确定了。
>  *  数组声明的类型，就决定了进行元素初始化时的类型。  
>     比如：`String[] arr;int[] arr1;Object[] arr2;`
> 
> ⭕ 数组在存储数据方面的弊端：
> 
>  *  数组初始化以后，长度就不可变了，不便于扩展。
>  *  数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。
>  *  获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用。
>  *  数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

### 二、概述 ###

> （1）Java集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的关联数组。

> （2）体系分布：  
> Java 集合可分为 `Collection` 和 `Map`两种体系。

> ⭕ `Collection`接口：单列数据，定义了存取一组对象的方法的集合。  
> ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16]  
> （实线表示“继承”，虚线表示“实现”）  
> ● `List`：元素有序、可重复的集合。–>“动态”数组
> 
>  *  `ArrayList`
>  *  `LinkedList`
>  *  `Vector`
> 
> ● `Set`：元素无序、不可重复的集合
> 
>  *  `HashSet`
>  *  `LinkedHashSet`
>  *  `TreeSet`

> ⭕ `Map`接口：双列数据，保存具有映射关系“`key-value对`”的集合  
> ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
> （实线表示“继承”，虚线表示“实现”）  
> ● `HashMap`  
> ● `LinkedHashMap`  
> ● `TreeMap`  
> ● `Hashtable`  
> ● `Properties`

### 三、Collection接口 ###

#### 1. 概述 ####

> （1）`Collection`接口是 `List`、`Set` 和 `Queue`接口的**父接口**，该接口里定义的方法既可用于操作`Set`集合，也可用于操作 `List` 和 `Queue` 集合。

> （2）`JDK`不提供此接口的任何直接实现，而是提供更具体的子接口（如:`Set`和`List`）实现。

> （3）在 Java5 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都当成 `Object` 类型处理；从`JDK 5.0`增加了**泛型**以后，Java 集合可以记住容器中对象的数据类型。

#### 2. 方法 ####

##### 2.1 添加 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法一</th> 
   <th align="center">方法二</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>add(Object obj)</code></td> 
   <td align="center"><code>addAll(Collection coll)</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.2 获取有效元素的个数 #####

##### 2.3 清空集合 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>void clear()</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.4 判断是否是空集合 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>boolean isEmpty()</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.5 判断是否包含某个元素 #####

<table> 
 <thead> 
  <tr> 
   <th>方法一</th> 
   <th>方法二</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>boolean contains(Object obj)</code></td> 
   <td><code>boolean containsAll(Collection c)</code></td> 
  </tr> 
 </tbody> 
</table>

> 通过调用元素的equals方法来（挨个）比较判断是否是同一个对象

##### 2.6 删除 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法一</th> 
   <th align="center">方法二</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>boolean remove(Object obj)</code></td> 
   <td align="center"><code>boolean removeAll(Collection coll)</code></td> 
  </tr> 
 </tbody> 
</table>

> 通过调用元素的`equals`方法来判断是否是要删除的某个元素，只会删除找到的第一个元素/删除当前集合里的指定某个子集合，即取当前集合的差集

##### 2.7 取两个集合的交集 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>boolean retainAll(Collection c)</code></td> 
  </tr> 
 </tbody> 
</table>

> 把交集的结果存在当前集合中

##### 2.8 判断集合是否相等 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>boolean equals(Object obj)</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.9 转成对象数组 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>Object[] toArray()</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.10 获取集合对象的哈希值 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>hashCode()</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.11 遍历 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>iterator()</code></td> 
  </tr> 
 </tbody> 
</table>

> 返回迭代器对象，用于集合遍历

##### 2.12 代码演示 #####

@Test
    public void test1(){
         
            Collection coll = new ArrayList();
    
            //add(Object e):将元素e添加到集合coll中
            coll.add("AA");
            coll.add("BB");
            coll.add(123);//自动装箱
            coll.add(new Date());
    
            //size():获取添加的元素的个数
            System.out.println(coll.size());//4
    
            //addAll(Collection coll1):将coll1集合中的元素添加到当前的集合中
            Collection coll1 = new ArrayList();
            coll1.add(456);
            coll1.add("CC");
            coll.addAll(coll1);
    
            System.out.println(coll.size());//6
            System.out.println(coll);//[AA, BB, 123, Tue Apr 19 22:51:41 CST 2022, 456, CC]
    
            //clear():清空集合元素
            coll.clear();
    
            //isEmpty():判断当前集合是否为空
            System.out.println(coll.isEmpty());//true
        }

@Test
       public void test2(){
         
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
    //        Person p = new Person("Jerry",20);
    //        coll.add(p);
            coll.add(new Person("Jerry",20));
            coll.add(new String("Tom"));
            coll.add(false);
            //1.contains(Object obj):判断当前集合中是否包含obj
            //我们在判断时会调用obj对象所在类的equals()。
            boolean contains = coll.contains(123);
            System.out.println(contains);//true
            System.out.println(coll.contains(new String("Tom")));//true
    //        System.out.println(coll.contains(p));//true
            System.out.println(coll.contains(new Person("Jerry",20)));//false 
    
            //2.containsAll(Collection coll1):判断形参coll1中的所有元素是否都存在于当前集合中。
            Collection coll1 = Arrays.asList(123,4567);
            System.out.println(coll.containsAll(coll1));//false
        }

@Test
        public void test3(){
         
            //3.remove(Object obj):从当前集合中移除obj元素。
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry",20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            coll.remove(1234);
            System.out.println(coll);//[123, 456, Person@621be5d1, Tom, false]
    
            coll.remove(new Person("Jerry",20));
            System.out.println(coll);//[123, 456, Person@621be5d1, Tom, false]
    
            //4. removeAll(Collection coll1):差集：从当前集合中移除coll1中所有的元素。
            Collection coll1 = Arrays.asList(123,456);
            coll.removeAll(coll1);
            System.out.println(coll);//[Person@621be5d1, Tom, false]
        }

@Test
        public void test4(){
         
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry",20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //5.retainAll(Collection coll1):交集：获取当前集合和coll1集合的交集，并返回给当前集合
           Collection coll1 = Arrays.asList(123,456,789);
           coll.retainAll(coll1);
           System.out.println(coll);//[123, 456]
    
            //6.equals(Object obj):要想返回true，需要当前集合和形参集合的元素都相同。
            Collection coll2 = new ArrayList();
            coll2.add(456);
            coll2.add(123);
            coll2.add(new Person("Jerry",20));
            coll2.add(new String("Tom"));
            coll2.add(false);
            System.out.println(coll.equals(coll2));//false
        }

@Test
        public void test5() {
         
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //7.hashCode():返回当前对象的哈希值
            System.out.println(coll.hashCode());//1412105286
    
            //8.集合 --->数组：toArray()
            Object[] arr = coll.toArray();
            for (int i = 0; i < arr.length; i++) {
         
                System.out.println(arr[i]);
            }
            //123
            //456
            //Person@621be5d1
            //Tom
            //false
    
            //拓展：数组 --->集合:调用Arrays类的静态方法asList()
            List<String> list = Arrays.asList(new String[]{
         "AA", "BB", "CC"});
            System.out.println(list);//[AA, BB, CC]
    
            List arr1 = Arrays.asList(new int[]{
         123, 456});
            System.out.println(arr1.size());//1
    
            List arr2 = Arrays.asList(new Integer[]{
         123, 456});
            System.out.println(arr2.size());//2
        }
    }

#### 3. Collection子接口之一：List接口 ####

##### 3.1 概述 #####

> （1）鉴于Java中数组用来存储数据的局限性，我们通常使用`List`替代数组。

> （2）`List`集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引，即“动态”数组,替换原有的数组。

> （3）`List`容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

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

##### 3.2 方法 #####

> `List`除了从`Collection`集合继承的方法外，`List` 集合里还添加了一些根据索引来操作集合元素的方法。

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>void add(int index, Object ele)</code></td> 
   <td>在<code>index</code>位置插入<code>ele</code>元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean addAll(int index, Collection eles)</code></td> 
   <td>从<code>index</code>位置开始将集合<code>eles</code>中的所有元素添加进来</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object get(int index)</code></td> 
   <td>获取指定<code>index</code>位置的元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>int indexOf(Object obj)</code></td> 
   <td>返回<code>obj</code>在集合中首次出现的位置</td> 
  </tr> 
  <tr> 
   <td align="center"><code>int lastIndexOf(Object obj)</code></td> 
   <td>返回<code>obj</code>在当前集合中末次出现的位置</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object remove(int index)</code></td> 
   <td>移除指定<code>index</code>位置的元素，并返回此元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object set(int index, Object ele)</code></td> 
   <td>设置指定<code>index</code>位置的元素为<code>ele</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>List subList(int fromIndex, int toIndex)</code></td> 
   <td>返回从<code>fromIndex</code>到<code>toIndex</code>位置的子集合</td> 
  </tr> 
 </tbody> 
</table>

**常用方法总结：**

<table> 
 <thead> 
  <tr> 
   <th>作用</th> 
   <th>方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td><code>add(Object obj)</code></td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td><code>remove(int index) / remove(Object obj)</code></td> 
  </tr> 
  <tr> 
   <td>改</td> 
   <td><code>set(int index, Object ele)</code></td> 
  </tr> 
  <tr> 
   <td>查</td> 
   <td><code>get(int index)</code></td> 
  </tr> 
  <tr> 
   <td>插</td> 
   <td><code>add(int index, Object ele)</code></td> 
  </tr> 
  <tr> 
   <td>长度</td> 
   <td><code>size()</code></td> 
  </tr> 
  <tr> 
   <td>遍历</td> 
   <td>①<code>Iterator</code>迭代器方式 ② 增强<code>for</code>循环 ③ 普通的循环</td> 
  </tr> 
 </tbody> 
</table>

###### 3.2.1 代码演示 ######

@Test
            public void test1(){
         
                ArrayList list = new ArrayList();
                list.add(123);
                list.add(456);
                list.add("AA");
                list.add(new Person("Tom",12));
                list.add(456);
        
                System.out.println(list);//[123, 456, AA, Person@621be5d1, 456]
        
                //void add(int index, Object ele):在index位置插入ele元素
                list.add(1,"BB");
                System.out.println(list);//[123, BB, 456, AA, Person@621be5d1, 456]
                
                //boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
                List list1 = Arrays.asList(1, 2, 3);
                list.addAll(list1);
        //        list.add(list1);
                System.out.println(list.size());//9
        
                //Object get(int index):获取指定index位置的元素
                System.out.println(list.get(0));//123
        
            }

@Test
        public void test2(){
         
            ArrayList list = new ArrayList();
            list.add(123);
            list.add(456);
            list.add("AA");
            list.add(new Person("Tom",12));
            list.add(456);
            //int indexOf(Object obj):返回obj在集合中首次出现的位置。如果不存在，返回-1.
            int index = list.indexOf(4567);
            System.out.println(index);//-1
    
            //int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置。如果不存在，返回-1.
            System.out.println(list.lastIndexOf(456));//4
    
            //Object remove(int index):移除指定index位置的元素，并返回此元素
            Object obj = list.remove(0);
            System.out.println(obj);//123
            System.out.println(list);//[456, AA, Person@621be5d1, 456]
    
            //Object set(int index, Object ele):设置指定index位置的元素为ele
            list.set(1,"CC");
            System.out.println(list);//[456, CC, Person@621be5d1, 456]
    
            //List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开区间的子集合
            List subList = list.subList(2, 4);
            System.out.println(subList);//[Person@621be5d1, 456]
            System.out.println(list);//[456, CC, Person@621be5d1, 456]
        }

@Test
        public void test3(){
         
            ArrayList list = new ArrayList();
            list.add(123);
            list.add(456);
            list.add("AA");
    
            //方式一：Iterator迭代器方式
            Iterator iterator = list.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
            //123
            //456
            //AA
            
    
            //方式二：增强for循环
            for(Object obj : list){
         
                System.out.println(obj);
            }
            //123
            //456
            //AA
    
    
    
            //方式三：普通for循环
            for(int i = 0;i < list.size();i++){
         
                System.out.println(list.get(i));
            }
            //123
            //456
            //AA
        }

##### 3.3 List实现类之一：ArrayList #####

###### 3.3.1 概述 ######

> ⭕ 作为`List`接口的主要实现类；

> ⭕ 线程不安全的，效率高；

> ⭕ 底层使用`Object[] elementData`存储。

###### 3.3.2 源码分析 ######

⭕ **jdk 7：**

> ?空参的构造器中，底层默认创建了长度是10的`Object[]`数组`elementData`。

ArrayList list = new ArrayList();
     list.add(123);//elementData[0] = new Integer(123);

> ?如果此次的添加导致底层`elementData`数组容量不够，则扩容。  
> 默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。

> ?建议开发中使用带参的构造器：默认创建指定长度的数组 。

ArrayList list = new ArrayList(int capacity)//默认创建指定长度的数组

⭕ **jdk 8：**

> ?底层`Object[] elementData`初始化为\{\}，并没有创建长度为10的数组

ArrayList list = new ArrayList();

> ?第一次调用`add()`时，底层才创建了长度10的数组，并将数据123添加`elementData[0]`

list.add(123);

> ?后续的添加和扩容操作与`jdk7`相同。

结论：jdk7中的`ArrayList`的对象的创建类似于单例的饿汉式，而jdk8中的`ArrayList`的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

##### 3.4 List实现类之二：LinkedList #####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_16_color_FFFFFF_t_70_g_se_x_16]

###### 3.4.1 概述 ######

> ⭕ 对于频繁的插入、删除操作，使用此类效率比`ArrayList`高；

> ⭕ 底层使用双向链表存储。
> 
> ⭕ `LinkedList`：双向链表，内部没有声明数组，而是定义了`Node`类型的`first`和`last`，  
> 用于记录首末元素。同时，定义内部类`Node`，作为`LinkedList`中保存数据的基本结构。

> ⭕ `Node`除了保存数据，还定义了两个变量：  
> `prev`变量记录前一个元素的位置  
> `next`变量记录下一个元素的位置

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_17_color_FFFFFF_t_70_g_se_x_16]

###### 3.4.2 源码分析 ######

LinkedList list = new LinkedList(); //内部声明了Node类型的first和last属性，默认值为null
    
    list.add(123);//将123封装到Node中，创建了Node对象。 
    
    //Node定义为：（体现了LinkedList的双向链表的说法）
    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;
            }
    }

##### 3.5 List实现类之三：Vector #####

###### 3.5.1 概述 ######

> ⭕ 作为`List`接口的古老实现类。

> ⭕ 线程安全的，效率低。

> ⭕ 底层使用`Object[] elementData`存储。

> ⭕在各种`list`中，最好把`ArrayList`作为缺省选择。当插入、删除频繁时，使用`LinkedList`；`Vector`总是比`ArrayList`慢，所以尽量避免使用。

> ⭕新增方法：

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>void addElement(Object obj)</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>void insertElementAt(Object obj,int index)</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>void setElementAt(Object obj,int index)</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>void removeElement(Object obj)</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>void removeAllElements()</code></td> 
  </tr> 
 </tbody> 
</table>

###### 3.5.2 源码分析 ######

> `jdk7`和`jdk8`中通过`Vector()`构造器创建对象时，底层都创建了长度为10的数组。 在扩容方面，默认扩容为原来的数组长度的2倍。

##### 3.6 ArrayList、LinkedList、Vector三者的异同？ #####

> ⭕ 同：  
> ① 三个类都是实现了`List`接口。  
> ② 存储数据的特点相同：存储有序的、可重复的数据。

> ⭕ 不同：见上

#### 4. Collection子接口之二：Set接口 ####

##### 4.1 概述 #####

> ⭕ `Set`接口是`Collection`的子接口，`set`接口没有提供额外的方法。

> ⭕ 存储无序的、不可重复的数据。`Set` 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 `Set` 集合中，则添加操作失败。

> ⭕ `Set` 判断两个对象是否相同不是使用 `==` 运算符，而是根据 `equals() 方法`。

> ⭕ 要求：  
> 向`Set`(主要指：`HashSet`、`LinkedHashSet`)中添加的数据，其所在的类一定要重写`hashCode()`和`equals()`，且重写的`hashCode()`和`equals()`尽可能保持一致性：相等的对象必须具有相等的散列码。  
> 重写两个方法的小技巧：对象中用作 `equals()` 方法比较的 `Field`，都应该用来计算 `hashCode` 值。

> ⭕ 重写 `hashCode()` 方法的基本原则
> 
>  *  在程序运行时，同一个对象多次调用 `hashCode()` 方法应该返回相同的值。  
>     \- 当两个对象的 `equals()` 方法比较返回 `true` 时，这两个对象的 `hashCode()`方法的返回值也应相等。
>  *  对象中用作 `equals()` 方法比较的 `Field`，都应该用来计算 `hashCode` 值。

> ⭕ 重写 `equals()` 方法的基本原则
> 
> 以自定义的`Customer`类为例，何时需要重写`equals()`？
> 
> 当一个类有自己特有的“逻辑相等”概念,当改写`equals()`的时候，总是要改写`hashCode()`，根据一个类的`equals()`方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据`Object.hashCode()`方法， 它们仅仅是两个对象。  
> 因此，违反了“相等的对象必须具有相等的散列码”。

结论：重写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

##### 4.2 Set实现类之一：HashSet #####

###### 4.2.1 概述 ######

> 存储无序的、不可重复的数据。
> 
>  *  无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
>  *  不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

###### 4.2.2 添加元素的过程 ######

> 我们向`HashSet`中添加元素`a`,首先调用元素`a`所在类的`hashCode()`方法，计算元素`a`的哈希值，此哈希值接着通过某种算法计算出在`HashSet`底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：
> 
> 1.  如果此位置上没有其他元素，则元素a添加成功。 —>情况1
> 2.  如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素`a`与元素`b`的`hash`值：  
>     2.1 如果`hash`值不相同，则元素`a`添加成功。—>情况2  
>     2.2 如果`hash`值相同，进而需要调用元素`a`所在类的`equals()`方法：  
>     `equals()`返回`true`,元素`a`添加失败  
>     `equals()`返回`false`,则元素`a`添加成功。—>情况3
> 
> 对于添加成功的情况2和情况3而言：元素`a`与已经存在指定索引位置上数据以链表的方式存储。  
> `jdk 7` :元素a放到数组中，指向原来的元素。  
> `jdk 8` :原来的元素在数组中，指向元素a  
> 口诀：七上八下

![在这里插入图片描述][77939c8d975a4f03aa4411931bf62374.png]

###### 4.2.3 代码演示 ######

@Test
        public void test(){
         
            Set set = new HashSet();
            set.add(456);
            set.add(123);
            set.add(123);
            set.add("AA");
            set.add("CC");
            set.add(new User("Tom",12));
            set.add(new User("Tom",12));
            set.add(129);
    
            Iterator iterator = set.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
            //AA
            //CC
            //129
            //456
            //User@621be5d1
            //User@573fd745
            //123
        }

##### 4.3 Set实现类之二：LinkedHashSet #####

###### 4.3.1 概述 ######

> ⭕ `LinkedHashSet` 是 `HashSet` 的子类。

> ⭕ `LinkedHashSet` 根据元素的`hashCode`值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。

> ⭕ `LinkedHashSet`插入性能略低于 `HashSet`，但在迭代访问`Set`里的全部元素时有很好的性能。对于频繁的遍历操作，`LinkedHashSet`效率高于`HashSet`。

> ⭕ `LinkedHashSet` 不允许集合元素重复。

###### 4.3.2 代码演示 ######

@Test
        public void test(){
         
            Set set = new LinkedHashSet();
            set.add(456);
            set.add(123);
            set.add(123);
            set.add("AA");
            set.add("CC");
            set.add(new User("Tom",12));
            set.add(new User("Tom",12));
            set.add(129);
    
            Iterator iterator = set.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
            //456
            //123
            //AA
            //CC
            //User@621be5d1
            //User@573fd745
            //129
            //
            //Process finished with exit code 0
        }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASXJfSGV5_size_20_color_FFFFFF_t_70_g_se_x_16]

##### 4.4 Set实现类之三：TreeSet #####

###### 4.4.1 概述 ######

> ⭕ `TreeSet`是`SortedSet`接口的实现类，`TreeSet`可以确保集合元素处于排序状态。

> ⭕ `TreeSet`底层使用红黑树结构存储数据。

> ⭕ 向`TreeSet`中添加的数据，要求是相同类的对象。

> ⭕ `TreeSet` 两种排序方法：自然排序和定制排序。默认情况下，`TreeSet`采用自然排序。
> 
>  *  自然排序  
>     `TreeSet` 会调用集合元素的 `compareTo(Object obj)` 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列
>  *  定制排序  
>     比较两个对象是否相同的标准为：`compare()`返回0，不再是`equals().`
> 
> 特点：有序，查询速度比List快

###### 4.4.2 排序—自然排序 ######

> ⭕ 如果试图把一个对象添加到 `TreeSet` 时，则该对象的类必须实现 `Comparable` 接口，实现 `Comparable` 的接口的类必须实现`compareTo(Object obj)` 方法，两个对象即通过`compareTo(Object obj)` 方法的返回值来比较大小。

> ⭕ 向 `TreeSet` 中添加元素时，只有第一个元素无须比较`compareTo()`方法，后面添加的所有元素都会调用`compareTo()`方法进行比较。

> ⭕ 因为只有相同类的两个实例才会比较大小，所以向 `TreeSet` 中添加的应该是同 一个类的对象。

> ⭕ 对于 `TreeSet` 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 `compareTo(Object obj)`方法比较返回值。

> ⭕ 当需要把一个对象放入 `TreeSet` 中，重写该对象对应的 `equals()` 方法时，应保证该方法与 `compareTo(Object obj)` 方法有一致的结果：如果两个对象通过 `equals()` 方法比较返回 `true`，则通过 `compareTo(Object obj)`方法比较应返回 0。否则，让人难以理解。

###### 4.4.3 排序—定制排序 ######

> ⭕ `TreeSet`的自然排序要求元素所属的类实现`Comparable`接口，如果元素所属的类没有实现`Comparable`接口，或不希望按照升序(默认情况)的方式排列元素或希望按照 其它属性大小进行排序，则考虑使用定制排序。

> ⭕ 定制排序，通过`Comparator`接口来实现。需要重写`compare(T o1,T o2)`方法。

> ⭕ 利用`int compare(T o1,T o2)`方法，比较`o1`和`o2`的大小：如果方法返回正整数，则表示`o1`大于`o2`；如果返回0，表示相等；返回负整数，表示`o1`小于`o2`。

> ⭕ 要实现定制排序，需要将实现`Comparator`接口的实例作为形参传递给`TreeSet`的构 造器。此时，仍然只能向`TreeSet`中添加类型相同的对象。否则发生`ClassCastException`异常。

> ⭕ 使用定制排序判断两个元素相等的标准是：通过`Comparator`比较两个元素返回了0。

###### 4.4.4 代码演示 ######

@Test
        public void test(){
         
            Comparator com = new Comparator() {
         
                //按照年龄从小到大排列
                @Override
                public int compare(Object o1, Object o2) {
         
                    if(o1 instanceof User && o2 instanceof User){
         
                        User u1 = (User)o1;
                        User u2 = (User)o2;
                        return Integer.compare(u1.getAge(),u2.getAge());
                    }else{
         
                        throw new RuntimeException("输入的数据类型不匹配");
                    }
                }
            };
    
            TreeSet set = new TreeSet(com);
            set.add(new User("Tom",12));
            set.add(new User("Jerry",32));
            set.add(new User("Jim",2));
            set.add(new User("Mike",65));
            set.add(new User("Mary",33));
            set.add(new User("Jack",33));
            set.add(new User("Jack",56));
    
    
            Iterator iterator = set.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
            //User@621be5d1
            //User@573fd745
            //User@15327b79
            //User@4f2410ac
            //User@722c41f4
            //User@5b80350b
    
        }

@Test
        public void test1(){
         
            TreeSet set = new TreeSet();
    
            //失败：不能添加不同类的对象
    //        set.add(123);
    //        set.add(456);
    //        set.add("AA");
    //        set.add(new User("Tom",12));
    
                //举例一：
    //        set.add(34);
    //        set.add(-34);
    //        set.add(43);
    //        set.add(11);
    //        set.add(8);
    
            //举例二：
            set.add(new User("Tom",12));
            set.add(new User("Jerry",32));
            set.add(new User("Jim",2));
            set.add(new User("Mike",65));
            set.add(new User("Jack",33));
            set.add(new User("Jack",56));
    
    
            Iterator iterator = set.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
    
        }

### 四、Map接口 ###

#### 1. 概述 ####

> ⭕ `Map`接口与`Collection`接口并列存在。用于保存具有映射关系的数据:`key-value` —类似于高中的函数：y = f(x)。

> ⭕ `Map`中的`key`和`value`都可以是任何引用类型的数据。

> ⭕ `Map`中的`key`:无序的、不可重复的，使用`Set`存储所有的`key`，常用`String`类作为`Map`的“键” —> `key`所在的类要重写`equals()`和`hashCode()`（以`HashMap`为例）

> ⭕ `Map`中的`value`:无序的、可重复的，使用`Collection`存储所有的`value` —>`value`所在的类要重写`equals()`

> ⭕ 一个键值对：`key-value`构成了一个`Entry`对象。`Map`中的`entry`:无序的、不可重复的，使用`Set`存储所有的`entry`

> ⭕ `key`和`value`之间存在单向一对一关系，即通过指定的`key`总能找到唯一的、确定的 `value`

> ⭕ `Map`接口的常用实现类：`HashMap`、`TreeMap`、`LinkedHashMap`和`Properties`。其中，`HashMap`是`Map`接口使用频率最高的实现类。

#### 2. Map中定义的方法 ####

> ⭕ 添加、删除、修改操作：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>Object put(Object key,Object value)</code></td> 
   <td>将指定<code>key-value</code>添加到(或修改)当前<code>map</code>对象中</td> 
  </tr> 
  <tr> 
   <td><code>void putAll(Map m)</code></td> 
   <td>将<code>m</code>中的所有<code>key-value</code>对存放到当前<code>map</code>中</td> 
  </tr> 
  <tr> 
   <td><code>Object remove(Object key)</code></td> 
   <td>移除指定<code>key</code>的<code>key-value</code>对，并返回<code>value</code></td> 
  </tr> 
  <tr> 
   <td><code>void clear()</code></td> 
   <td>清空当前<code>map</code>中的所有数据</td> 
  </tr> 
 </tbody> 
</table>

> ⭕ 元素查询的操作：

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th align="center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>Object get(Object key)</code></td> 
   <td align="center">获取指定<code>key</code>对应的<code>value</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean containsKey(Object key)</code></td> 
   <td align="center">是否包含指定的<code>key</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean containsValue(Object value)</code></td> 
   <td align="center">是否包含指定的<code>value</code></td> 
  </tr> 
  <tr> 
   <td align="center"><code>int size()</code></td> 
   <td align="center">返回<code>map</code>中<code>key-value</code>对的个数</td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean isEmpty()</code></td> 
   <td align="center">判断当前<code>map</code>是否为空</td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean equals(Object obj)</code></td> 
   <td align="center">判断当前<code>map</code>和参数对象<code>obj</code>是否相等</td> 
  </tr> 
  <tr> 
   <td align="center"><code>getOrDefault(Object key, V defaultValue)</code></td> 
   <td align="center">当Map集合中存在这个key时，就使用这个key对应的value值，否则就使用默认值defaultValue，意味着就算出现key to null这种键值对时，依然返回null而不是默认值</td> 
  </tr> 
 </tbody> 
</table>

> ⭕ 元视图操作的方法：

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th align="center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>Set keySet()</code></td> 
   <td align="center">返回所有<code>key</code>构成的<code>Set</code>集合</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Collection values()</code></td> 
   <td align="center">返回所有<code>value</code>构成的<code>Collection</code>集合</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Set entrySet()</code></td> 
   <td align="center">返回所有<code>key-value</code>对构成的<code>Set</code>集合</td> 
  </tr> 
 </tbody> 
</table>

> ⭕ 总结：常用方法：

<table> 
 <thead> 
  <tr> 
   <th align="center">作用</th> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">添加</td> 
   <td align="center"><code>put(Object key,Object value)</code></td> 
  </tr> 
  <tr> 
   <td align="center">删除</td> 
   <td align="center"><code>remove(Object key)</code></td> 
  </tr> 
  <tr> 
   <td align="center">修改</td> 
   <td align="center"><code>put(Object key,Object value)</code></td> 
  </tr> 
  <tr> 
   <td align="center">查询</td> 
   <td align="center"><code>get(Object key)</code></td> 
  </tr> 
  <tr> 
   <td align="center">长度</td> 
   <td align="center"><code>size()</code></td> 
  </tr> 
  <tr> 
   <td align="center">遍历</td> 
   <td align="center"><code>keySet() / values() / entrySet()</code></td> 
  </tr> 
 </tbody> 
</table>

##### 2.1 代码演示 #####

@Test
        public void test1(){
         
            Map map = new HashMap();
    //        map = new Hashtable();
            map.put(null,123);
    
        }

@Test
        public void test2(){
         
            Map map = new HashMap();
            map = new LinkedHashMap();
            map.put(123,"AA");
            map.put(345,"BB");
            map.put(12,"CC");
    
            System.out.println(map);//{123=AA, 345=BB, 12=CC}
        }

/*
         添加、删除、修改操作：
     Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
     void putAll(Map m):将m中的所有key-value对存放到当前map中
     Object remove(Object key)：移除指定key的key-value对，并返回value
     void clear()：清空当前map中的所有数据
         */
        @Test
        public void test3(){
         
            Map map = new HashMap();
            //添加
            map.put("AA",123);
            map.put(45,123);
            map.put("BB",56);
            //修改
            map.put("AA",87);
    
            System.out.println(map);//{AA=87, BB=56, 45=123}
    
            Map map1 = new HashMap();
            map1.put("CC",123);
            map1.put("DD",123);
    
            map.putAll(map1);
    
            System.out.println(map);//{AA=87, BB=56, CC=123, DD=123, 45=123}
    
            //remove(Object key)
            Object value = map.remove("CC");
            System.out.println(value);//123
            System.out.println(map);//{AA=87, BB=56, DD=123, 45=123}
    
            //clear()
            map.clear();//与map = null操作不同
            System.out.println(map.size());//0
            System.out.println(map);//{}
        }

/*
     元素查询的操作：
     Object get(Object key)：获取指定key对应的value
     boolean containsKey(Object key)：是否包含指定的key
     boolean containsValue(Object value)：是否包含指定的value
     int size()：返回map中key-value对的个数
     boolean isEmpty()：判断当前map是否为空
     boolean equals(Object obj)：判断当前map和参数对象obj是否相等
         */
        @Test
        public void test4(){
         
            Map map = new HashMap();
            map.put("AA",123);
            map.put(45,123);
            map.put("BB",56);
            // Object get(Object key)
            System.out.println(map.get(45));//123
            //containsKey(Object key)
            boolean isExist = map.containsKey("BB");
            System.out.println(isExist);//true
    
            isExist = map.containsValue(123);
            System.out.println(isExist);//true
    
            map.clear();
    
            System.out.println(map.isEmpty());//true
    
        }

/*
     元视图操作的方法：
     Set keySet()：返回所有key构成的Set集合
     Collection values()：返回所有value构成的Collection集合
     Set entrySet()：返回所有key-value对构成的Set集合
    
         */
    
    
        @Test
        public void test5(){
         
            Map map = new HashMap();
            map.put("AA",123);
            map.put(45,1234);
            map.put("BB",56);
    
            //遍历所有的key集：keySet()
            Set set = map.keySet();
            Iterator iterator = set.iterator();
            while(iterator.hasNext()){
         
                System.out.println(iterator.next());
            }
            //AA
            //BB
            //45
            
            
            System.out.println();
            //遍历所有的value集：values()
            Collection values = map.values();
            for(Object obj : values){
         
                System.out.println(obj);
            }
            //123
            //56
            //1234
            
            
            System.out.println();
            //遍历所有的key-value
            //方式一：entrySet()
            Set entrySet = map.entrySet();
            Iterator iterator1 = entrySet.iterator();
            while (iterator1.hasNext()){
         
                Object obj = iterator1.next();
                //entrySet集合中的元素都是entry
                Map.Entry entry = (Map.Entry) obj;
                System.out.println(entry.getKey() + "---->" + entry.getValue());
            }
            //AA---->123
            //BB---->56
            //45---->1234
            
            
            System.out.println();
            //方式二：
            Set keySet = map.keySet();
            Iterator iterator2 = keySet.iterator();
            while(iterator2.hasNext()){
         
                Object key = iterator2.next();
                Object value = map.get(key);
                System.out.println(key + "=====" + value);
            }
            //AA=====123
            //BB=====56
            //45=====1234
    
        }

#### 3. Map实现类之一：HashMap ####

##### 3.1 概述 #####

> ⭕ `HashMap`作为`Map`的主要实现类，线程不安全的，效率高，可存储`null`的`key`和`value`

> ⭕ `HashMap`是 `Map`接口使用频率最高的实现类。

> ⭕ 允许使用`null`键和`null`值，与`HashSet`一样，不保证映射的顺序。

> ⭕ 所有的`key`构成的集合是`Set`:无序的、不可重复的。所以，`key`所在的类要重写： `equals()`和`hashCode()`

> ⭕ 所有的`value`构成的集合是`Collection`:无序的、可以重复的。所以，`value`所在的类要重写：`equals()`

> ⭕ 一个`key-value`构成一个`entry`，所有的`entry`构成的集合是`Set`:无序的、不可重复的

> ⭕ `HashMap` 判断两个 `key` 相等的标准是：两个 `key` 通过 `equals()` 方法返回 `true`， `hashCode` 值也相等。

> ⭕ `HashMap` 判断两个 `value`相等的标准是：两个 `value` 通过 `equals()` 方法返回 `true`。

> ⭕ `HashMap`的存储结构  
> `JDK 7`及以前版本：`HashMap`是数组+链表结构(即为链地址法)  
> `JDK8`版本发布以后：`HashMap`是数组+链表+红黑树实现。

##### 3.2 HashMap 的底层实现原理 #####

⭕ **jdk7：**

> ? `HashMap map = new HashMap()`:在实例化以后，底层创建了长度是16的一维数组`Entry[] table`。
> 
> ? map.put(key1,value1):…可能已经执行过多次put…
> 
> 首先，调用`key1`所在类的`hashCode()`计算key1哈希值，此哈希值经过某种算法计算以  
> 后，得到在`Entry`数组中的存放位置。
> 
> 1.  如果此位置上的数据为空，此时的`key1-value1`添加成功。 \----情况1
> 2.  如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较`key1`和已经存在的一个或多个数据的哈希值：  
>     2.1  
>     如果`key1`的哈希值与已经存在的数据的哈希值都不相同，此时`key1-value1`添加成功。-—情况2   
>     2.2  
>     如果`key1`的哈希值和已经存在的某一个数据`key2-value2`的哈希值相同，继续比较：调用`key1`所在类的`equals(key2)`方法，比较：  
>     如果`equals()`返回`false`:此时`key1-value1`添加成功。\----情况3   
>     如果`equals()`返回`true`:使用`value1`替换`value2`。
> 
> ? 补充：关于情况2和情况3：此时`key1-value1`和原来的数据以链表的方式存储。  
> 在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

⭕ **`jdk8` 相较于`jdk7`在底层实现方面的不同：**

> ? `new HashMap()`:底层没有创建一个长度为16的数组。  
> ? `jdk 8`底层的数组是：`Node[]`,而非`Entry[]`。  
> ? 首次调用`put()`方法时，底层创建长度为16的数组。  
> ? `jdk7`底层结构只有：数组+链表。`jdk8`中底层结构：数组+链表+红黑树。  
> ? 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）  
> ? 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

##### 3.3 HashMap 源码中的重要常量 #####

<table> 
 <thead> 
  <tr> 
   <th align="center">常量</th> 
   <th align="center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>DEFAULT_INITIAL_CAPACITY</code></td> 
   <td align="center"><code>HashMap</code>的默认容量，16</td> 
  </tr> 
  <tr> 
   <td align="center"><code>MAXIMUM_CAPACITY</code></td> 
   <td align="center"><code>HashMap</code>的最大支持容量，2^30</td> 
  </tr> 
  <tr> 
   <td align="center"><code>DEFAULT_LOAD_FACTOR</code></td> 
   <td align="center"><code>HashMap</code>的默认加载因子</td> 
  </tr> 
  <tr> 
   <td align="center"><code>TREEIFY_THRESHOLD</code></td> 
   <td align="center"><code>Bucket</code>中链表长度大于该默认值，转化为红黑树</td> 
  </tr> 
  <tr> 
   <td align="center"><code>UNTREEIFY_THRESHOLD</code></td> 
   <td align="center"><code>Bucket</code>中红黑树存储的<code>Node</code>小于该默认值，转化为链表</td> 
  </tr> 
  <tr> 
   <td align="center"><code>MIN_TREEIFY_CAPACITY</code></td> 
   <td align="center">桶中的<code>Node</code>被树化时最小的<code>hash</code>表容量。（当桶中<code>Node</code>的数量达到需要变红黑树时，若<code>hash</code>表容量小于<code>MIN_TREEIFY_CAPACITY</code>时，此时应执行<code>resize</code>扩容操作这个<code>MIN_TREEIFY_CAPACITY</code>的值至少是<code>TREEIFY_THRESHOLD</code>的4倍。）</td> 
  </tr> 
  <tr> 
   <td align="center"><code>table</code></td> 
   <td align="center">存储元素的数组，总是2的n次幂</td> 
  </tr> 
  <tr> 
   <td align="center"><code>entrySet</code></td> 
   <td align="center">存储具体元素的集</td> 
  </tr> 
  <tr> 
   <td align="center"><code>size</code></td> 
   <td align="center">HashMap中存储的键值对的数量</td> 
  </tr> 
  <tr> 
   <td align="center"><code>modCount</code></td> 
   <td align="center">HashMap扩容和结构改变的次数。</td> 
  </tr> 
  <tr> 
   <td align="center"><code>threshold</code></td> 
   <td align="center">扩容的临界值，=容量*填充因子</td> 
  </tr> 
  <tr> 
   <td align="center"><code>loadFactor</code></td> 
   <td align="center">填充因子</td> 
  </tr> 
 </tbody> 
</table>

##### 3.4 HashMap的存储结构：JDK 1.8之前 #####

> ⭕ `HashMap`的内部存储结构其实是数组和链表的结合。当实例化一个`HashMap`时，系统会创建一个长度为`Capacity`的`Entry`数组，这个长度在哈希表中被称为容量 `(Capacity)`，在这个数组中可以存放元素的位置我们称之为“桶”`(bucket)`，每个`bucket`都有自己的索引，系统可以根据索引快速的查找`bucket`中的元素。

> ⭕ 每个`bucket`中存储一个元素，即一个`Entry`对象，但每一个`Entry`对象可以带一个引  
> 用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个`Entry`链。 而且新添加的元素作为链表的`head`。

> ⭕ 添加元素的过程：  
> 向`HashMap`中添加`entry1(key，value)`，需要首先计算`entry1`中`key`的哈希值(根据`key`所在类的`hashCode()`计算得到)，此哈希值经过处理以后，得到在底层`Entry[]`数组中要存储的位置i。如果位置i上没有元素，则`entry1`直接添加成功。如果位置i上已经存在`entry2`(或还有链表存在的`entry3`，`entry4`)，则需要通过循环的方法，依次比较`entry1`中`key`和其他的`entry`。如果彼此`hash`值不同，则直接添加成功。如果  
> `hash`值不同，继续比较二者是否`equals`。如果返回值为`true`，则使用`entry1`的`value`  
> 去替换`equals`为`true`的`entry`的`value`。如果遍历一遍以后，发现所有的`equals`返回都  
> 为`false`,则`entry1`仍可添加成功。`entry1`指向原有的`entry`元素。

> ⭕ `HashMap`的扩容 :  
> 当`HashMap`中的元素越来越多的时候，`hash`冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对`HashMap`的数组进行扩容，而在`HashMap`数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算 其在新数组中的位置，并放进去，这就是`resize`。

> ⭕ 那么`HashMap`什么时候进行扩容呢？  
> 当`HashMap`中的元素个数超过数组大小(数组总大小`length`,不是数组中个数  
> `size`)*`loadFactor` 时 ， 就会进行数组扩容 ，`loadFactor` 的默认值`(DEFAULT_LOAD_FACTOR)`为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小`(DEFAULT_INITIAL_CAPACITY)`为16，那么当`HashMap`中元素个数超过16*0.75=12（这个值就是代码中的`threshold`值，也叫做临界值）的时候，就把数组的大小扩展为  
> 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知`HashMap`中元素的个数， 那么预设元素的个数能够有效的提高`HashMap`的性能。

> ⭕ `HashMap`的内部存储结构其实是数组+链表+树的结合。  
> 当实例化一个`HashMap`时，会初始化`initialCapacity`和`loadFactor`，在`put`第一对映射关系时，系统会创建一个长度为`initialCapacity`的`Node`数组，这个长度在哈希表中被称为容量`(Capacity)`，在这个数组中可以存放元素的位置我们称之为“桶”(`bucket`)，每个`bucket`都有自己的索引，系统可以根据索引快速的查找`bucket`中的元素。

> ⭕ 每个`bucket`中存储一个元素，即一个`Node`对象，但每一个`Node`对象可以带一个引用变量`next`，用于指向下一个元素，因此，在一个桶中，就有可能生成一个`Node`链。也可能是一个一个`TreeNode`对象，每一个`TreeNode`对象可以有两个叶子结点`left`和`right`，因此，在一个桶中，就有可能生成一个`TreeNode`树。而新添加的元素作为链表的`last`，或树的叶子结点。

> ⭕ 那么`HashMap`什么时候进行扩容和树形化呢？  
> 当`HashMap`中的元素个数超过数组大小(数组总大小`length`,不是数组中个数  
> `size`)*`loadFactor` 时 ， 就会进行数组扩容 ， `loadFactor` 的默认 值  
> `(DEFAULT_LOAD_FACTOR)`为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小`(DEFAULT_INITIAL_CAPACITY)`为16，那么当`HashMap`中元素个数超过16*0.75=12（这个值就是代码中的`threshold`值，也叫做临界值） 的时候，就把数组的大小扩展为  
> 2\*16=32，即扩大一倍，然后重新计算每个元 素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知`HashMap`中元素的个数，那么预设元素的个数能够有效的提高`HashMap`的性能。

> ⭕ 当`HashMap`中的其中一个链的对象个数如果达到了8个，此时如果`capacity`没有  
> 达到64，那么`HashMap`会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由`Node`变成`TreeNode`类型。当然，如果当映射关系被移除后，下次`resize`方法时判断树的结点个数低于6个，也会把树再转为链表。

> ⭕ 关于映射关系的`key`是否可以修改？answer：不要修改  
> 映射关系存储到`HashMap`中会存储`key`的`hash`值，这样就不用在每次查找时重新计算  
> 每一个`Entry`或`Node（TreeNode）`的`hash`值了，因此如果已经`put`到`Map`中的映射关系，再修改`key`的属性，而这个属性又参与`hashcode`值的计算，那么会导致匹配不上。

> ⭕ 总结：  
> ? `HashMap map = new HashMap()`;//默认情况下，先不创建长度为16的数组  
> ? 当首次调用`map.put()`时，再创建长度为16的数组  
> ? 数组为`Node`类型，在`jdk7`中称为`Entry`类型  
> ? 形成链表结构时，新添加的`key-value`对在链表的尾部（七上八下）  
> ? 当数组指定索引位置的链表长度>8时，且`map`中的数组的长度> 64时，此索引位置 上的所有`key-value`对使用红黑树进行存储。

> ⭕ 面试题：负载因子值的大小，对`HashMap`有什么影响?  
> ? 负载因子的大小决定了`HashMap`的数据密度。  
> ? 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。  
> ? 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。  
> ? 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。

#### 4. Map实现类之二：LinkedHashMap ####

##### 4.1 概述 #####

> ⭕ `LinkedHashMap` 是 `HashMap` 的子类 。

> ⭕ 在`HashMap`存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。

> ⭕ 与`LinkedHashSet`类似，`LinkedHashMap` 可以维护 `Map` 的迭代 顺序：迭代顺序与 `Key-Value`对的插入顺序一致，保证在遍历`map`元素时，可以按照添加的顺序实现遍历。  
> 原因：在原有的`HashMap`底层结构基础上，添加了一对指针，指向前一个和后一个元素。

> ⭕ 对于频繁的遍历操作，此类执行效率高于`HashMap`。

##### 4.2 底层结构 #####

> ⭕ `HashMap`中的内部类：`Node`

static class Node<K,V> implements Map.Entry<K,V> {
         
    final int hash;
    final K key;
    V value;
    Node<K,V> next; }

> ⭕ `LinkedHashMap`中的内部类：`Entry`

static class Entry<K,V> extends HashMap.Node<K,V> {
         
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
         
    super(hash, key, value, next);
    } 
    }

#### 5. Map实现类之三：TreeMap ####

##### 5.1 概述 #####

> ⭕ `TreeMap`存储 `Key-Value` 对时，需要根据 `key-value` 对进行排序。

> ⭕ `TreeMap` 可以保证所有的 `Key-Value` 对处于有序状态。

> ⭕ `TreeSet`底层使用红黑树结构存储数据。

> ⭕ 保证按照添加的`key-value`对进行排序，实现排序遍历。此时考虑`key`的自然排序或定制排序：
> 
> ?自然排序：`TreeMap` 的所有的 `Key` 必须实现 `Comparable` 接口，而且所有的 `Key` 应该是同一个类的对象，否则将会抛出`ClasssCastException`
> 
> ?定制排序：创建 `TreeMap` 时，传入一个 `Comparator` 对象，该对象负责对`TreeMap` 中的所有 `key`进行排序。此时不需要 `Map` 的 `Key` 实现`Comparable` 接口

> ⭕ `TreeMap`判断两个key相等的标准：两个key通过`compareTo()`方法或者`compare()`方法返回0。

##### 5.2 代码演示 #####

public class TreeMapTest {
         
    
        //向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
        //因为要按照key进行排序：自然排序 、定制排序
        //自然排序
        @Test
        public void test1(){
         
            TreeMap map = new TreeMap();
            User u1 = new User("Tom",23);
            User u2 = new User("Jerry",32);
            User u3 = new User("Jack",20);
            User u4 = new User("Rose",18);
    
            map.put(u1,98);
            map.put(u2,89);
            map.put(u3,76);
            map.put(u4,100);
    
            Set entrySet = map.entrySet();
            Iterator iterator1 = entrySet.iterator();
            while (iterator1.hasNext()){
         
                Object obj = iterator1.next();
                Map.Entry entry = (Map.Entry) obj;
                System.out.println(entry.getKey() + "---->" + entry.getValue());
    
            }
        }
    
        //定制排序
        @Test
        public void test2(){
         
            TreeMap map = new TreeMap(new Comparator() {
         
                @Override
                public int compare(Object o1, Object o2) {
         
                    if(o1 instanceof User && o2 instanceof User){
         
                        User u1 = (User)o1;
                        User u2 = (User)o2;
                        return Integer.compare(u1.getAge(),u2.getAge());
                    }
                    throw new RuntimeException("输入的类型不匹配！");
                }
            });
            User u1 = new User("Tom",23);
            User u2 = new User("Jerry",32);
            User u3 = new User("Jack",20);
            User u4 = new User("Rose",18);
    
            map.put(u1,98);
            map.put(u2,89);
            map.put(u3,76);
            map.put(u4,100);
    
            Set entrySet = map.entrySet();
            Iterator iterator1 = entrySet.iterator();
            while (iterator1.hasNext()){
         
                Object obj = iterator1.next();
                Map.Entry entry = (Map.Entry) obj;
                System.out.println(entry.getKey() + "---->" + entry.getValue());
    
            }
        }
    
    
    }

#### 6. Map实现类之四：Hashtable ####

##### 6.1 概述 #####

> ⭕ `Hashtable`是个古老的 `Map` 实现类，`JDK1.0`就提供了。不同于`HashMap`，`Hashtable`是线程安全的，但效率低；不能存储`null`的`key`和`value`。

> ⭕ `Hashtable`实现原理和`HashMap`相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。

> ⭕与`HashMap`的比较  
> ?与`HashMap`不同，`Hashtable` 不允许使用 `null` 作为 `key` 和 `value` 。  
> ?与`HashMap`一样，`Hashtable`也不能保证其中 `Key-Value` 对的顺序。

> ⭕ `Hashtable`判断两个`key`相等、两个`value`相等的标准，与`HashMap`一致。

#### 7. Map实现类之四：Properties ####

##### 7.1 概述 #####

> ⭕ `Properties` 类是 `Hashtable` 的子类，该对象用于处理属性文件 。

> ⭕ 由于属性文件里的 `key`、`value`都是字符串`String`类型，所以 `Properties` 里的 key 和 `value` 都是字符串`String`类型。

> ⭕ `Properties`:常用来处理配置文件。

> ⭕ 存取数据时，建议使用`setProperty(String key,String value)`方法和 `getProperty(String key)`方法 。

Properties pros = new Properties();
    pros.load(new FileInputStream("jdbc.properties")); 
    String user =pros.getProperty("user"); 
    System.out.println(user);

##### 7.2 代码演示 #####

public class PropertiesTest {
         
    
        
    
    //Properties:常用来处理配置文件。key和value都是String类型
        public static void main(String[] args)  {
         
            FileInputStream fis = null;
            try {
         
                Properties pros = new Properties();
    
                fis = new FileInputStream("jdbc.properties");
                pros.load(fis);//加载流对应的文件
    
                String name = pros.getProperty("name");
                String password = pros.getProperty("password");
    
                System.out.println("name = " + name + ", password = " + password);
            } catch (IOException e) {
         
                e.printStackTrace();
            } finally {
         
                if(fis != null){
         
                    try {
         
                        fis.close();
                    } catch (IOException e) {
         
                        e.printStackTrace();
                    }
    
                }
            }
    
        }
    }

### 五、 Collections工具类 ###

#### 1. 概述 ####

> ⭕ Collections工具类是一个操作数组的工具类：Arrays
> 
> ⭕ Collections 是一个操作 Set、List 和 Map 等集合的工具类
> 
> ⭕ Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。

#### 2. Collections工具类方法 ####

> ⭕ 排序操作：（均为`static`方法）

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th align="center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>reverse(List)</code></td> 
   <td align="center">反转 <code>List</code> 中元素的顺序</td> 
  </tr> 
  <tr> 
   <td align="center"><code>shuffle(List)</code></td> 
   <td align="center">对 <code>List</code> 集合元素进行随机排序</td> 
  </tr> 
  <tr> 
   <td align="center"><code>sort(List)</code></td> 
   <td align="center">根据元素的自然顺序对指定 List 集合元素按升序排序</td> 
  </tr> 
  <tr> 
   <td align="center"><code>sort(List，Comparator)</code></td> 
   <td align="center">根据指定的 <code>Comparator</code> 产生的顺序对 List 集合元素进行排序</td> 
  </tr> 
  <tr> 
   <td align="center"><code>swap(List，int， int)</code></td> 
   <td align="center">将指定 list 集合中的 i 处元素和 j 处元素进行交换</td> 
  </tr> 
 </tbody> 
</table>

> ⭕查找、替换操作：

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th align="center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code>Object max(Collection)</code></td> 
   <td align="center">根据元素的自然顺序，返回给定集合中的最大元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object max(Collection，Comparator)</code></td> 
   <td align="center">根据 <code>Comparator</code> 指定的顺序，返回给定集合中的最大元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object min(Collection)</code></td> 
   <td align="center">根据元素的自然顺序，返回给定集合中的最小元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>Object min(Collection，Comparator)</code></td> 
   <td align="center">根据 <code>Comparator</code> 指定的顺序，返回给定集合中的最小元素</td> 
  </tr> 
  <tr> 
   <td align="center"><code>int frequency(Collection，Object)</code></td> 
   <td align="center">返回指定集合中指定元素的出现次数</td> 
  </tr> 
  <tr> 
   <td align="center"><code>void copy(List dest,List src)</code></td> 
   <td align="center">将<code>src</code>中的内容复制到<code>dest</code>中</td> 
  </tr> 
  <tr> 
   <td align="center"><code>boolean replaceAll(List list，Object oldVal，Object newVal)</code></td> 
   <td align="center">使用新值替换<code>List</code> 对象的所有旧值</td> 
  </tr> 
 </tbody> 
</table>

> ⭕同步控制操作：
> 
> `Collections` 类中提供了多个 `synchronizedXxx()` 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 3. 代码演示 ####

@Test
        public void test1(){
         
            List list = new ArrayList();
            list.add(123);
            list.add(43);
            list.add(765);
            list.add(-97);
            list.add(0);
    
            //报异常：IndexOutOfBoundsException("Source does not fit in dest")
    //        List dest = new ArrayList();
    //        Collections.copy(dest,list);
            //正确的：
            List dest = Arrays.asList(new Object[list.size()]);
            System.out.println(dest.size());//list.size(); 5
            Collections.copy(dest,list);
    
            System.out.println(dest);//[123, 43, 765, -97, 0]
    
    
            /*
            Collections 类中提供了多个 synchronizedXxx() 方法，
            该方法可使将指定集合包装成线程同步的集合，从而可以解决
            多线程并发访问集合时的线程安全问题
    
             */
            //返回的list1即为线程安全的List
            List list1 = Collections.synchronizedList(list);
        }

@Test
        public void test2(){
         
            List list = new ArrayList();
            list.add(123);
            list.add(43);
            list.add(765);
            list.add(765);
            list.add(765);
            list.add(-97);
            list.add(0);
    
            System.out.println(list);//[123, 43, 765, 765, 765, -97, 0]
    
    //        Collections.reverse(list);
    //        Collections.shuffle(list);
    //        Collections.sort(list);
    //        Collections.swap(list,1,2);
            int frequency = Collections.frequency(list, 123);
    
            System.out.println(list);//[123, 43, 765, 765, 765, -97, 0]
            System.out.println(frequency);//1
    
        }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/8e9a50666e5e4b478867576864952444.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/e893bd00a27d412b9915d203c651c58e.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_16_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/43a1a501b1ca46cd8c7dbc6e2e55e115.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_17_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/88072b39673d49efa47dc7496eaee23b.png
[77939c8d975a4f03aa4411931bf62374.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/19e4a963e9474e82a46dafc128cc2653.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASXJfSGV5_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/6ee13c3bc9894f74b1d089d8d64ab385.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP6ICB5biIaXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/8bc834f5e36140039ed231895a9c3f23.png