Java集合框架概述

集合的定义

集合、数组都是对多个数据（对象）进行存储操作的结构，简称为Java容器

此时的”存储”主要指的是内存层面的存储，不涉及到持久化的存储

集合与数组的对比利弊

数组存储的特点

  1.   - 一旦初始化以后，其长度就确定了
  2.   - 数组一旦定义好，其元素的类型也就确定了，我们也就只能操作指定类型的数据了。比如：String[] arr1;Object[] arr2

数组存储的弊端

  1.   - 一旦初始化后，其长度就不可修改
  2.   - 数组中提供的方法非常有限，对于添加、删除、插入数据等操作，非常不便，同时效率不高
  3.   - 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
  4.   - 数组存储数据的特点：有序、可重复。对于无序、不可重复的需求，不能满足

集合存储的优点
解决数组存储数据方面的弊端

Collection接口方法

单列集合框架结构

层级
|——Collection接口：单列集合，用来存储一个一个的对象
|——List接口：存储有序的，可重复的数据 —> “动态”数组
|——ArrayList、LinkedList、Vector
|——Set接口：存储无序的，不可重复的数据 —> 类似于高中的”集合”
|—-HashSet、LinkedHashSet、TreeSet
对应图示
image.png

Collection接口常用方法

  1. /**
  2.  * Collection相关方法测试
  3.  * <p>
  4.  * add(E e)
  5.  * size()
  6.  * addAll(Collection coll1)
  7.  * clear()
  8.  * isEmpty()
  9.  * contains(Object obj)
  10.  * containsAll(Collection coll1)
  11.  * remove(Object obj)
  12.  * removeAll(Collection coll1)
  13.  * retainAll(Collection coll1)
  14.  * equals(Object obj)
  15.  * hashCode()
  16.  * toArray()
  17.  * 拓展: 数组转换为集合
  18.  * </p>
  19.  *
  20.  * @author : YukiJudai 2022/3/24 14:38
  21.  */
  22. public class CollectionTest {
  23.     @Test
  24.     public void test1() {
  25.         Collection coll = new ArrayList();
  26.         //add(E e):将元素e添加到集合coll中
  27.         coll.add("AA");
  28.         coll.add("BB");
  29.         coll.add(123);
  30.         coll.add(new Date());
  32.         //size()：获取添加的元素的个数
  33.         System.out.println(coll.size());
  35.         //addAll(Collection coll1):将coll1集合中的元素添加到当前的集合中
  36.         Collection coll1 = new ArrayList();
  37.         coll1.add(456);
  38.         coll1.add("CC");
  40.         coll.addAll(coll1);
  42.         //clear():清空集合元素
  43.         coll.clear();
  45.         //isEmpty():判断当前集合是否为空
  46.         System.out.println(coll.isEmpty());
  47.     }
  49.     @Test
  50.     public void test2() {
  51.         Collection coll = new ArrayList();
  52.         coll.add(456);
  53.         coll.add(new String("BB"));
  54.         coll.add(123);
  55.         coll.add(new Date());
  57.         //contains(Object obj):判断当前集合是否包含obj
  58.         System.out.println(coll.contains(123));
  59.         System.out.println(coll.contains(new String("BB")));
  61.         //containsAll(Collection coll1):判断形参coll1中的所有元素是否都存在于当前集合中
  62.         Collection coll1 = Arrays.asList(123, 456);
  63.         System.out.println(coll.containsAll(coll1));
  64.     }
  66.     @Test
  67.     public void test3() {
  68.         //remove(Object obj):从当前集合中移除obj元素
  69.         Collection coll = new ArrayList();
  70.         coll.add(123);
  71.         coll.add(456);
  72.         coll.add(new String("Tom"));
  73.         coll.add(false);
  75.         //removeAll(Collection coll1):（差集）从当前集合中移除coll1中所有的元素
  76.         Collection coll1 = Arrays.asList(123, 456);
  77.         System.out.println(coll.removeAll(coll1));
  78.     }
  80.     @Test
  81.     public void test4() {
  82.         Collection coll = new ArrayList();
  83.         coll.add(123);
  84.         coll.add(456);
  85.         coll.add(new String("Tom"));
  86.         coll.add(false);
  88.         //retainAll(Collection coll1):（交集）获取当前集合和coll1集合的交集，并返回给当前集合
  89. //        Collection coll1 = Arrays.asList(123,456);
  90. //        System.out.println(coll.retainAll(coll1));
  92.         //equals(Object obj):要想返回true,需要当前集合和形参集合的元素都相同
  93.         Collection coll2 = new ArrayList();
  94.         coll2.add(456);
  95.         coll2.add(123);
  96.         coll2.add(new String("Tom"));
  97.         coll2.add(false);
  99.         System.out.println(coll.equals(coll2));
  101.         //hashCode():返回当前对象的哈希值
  102.         System.out.println(coll.hashCode());
  104.         //toArray():集合转换为数组
  105.         Object[] arr = coll.toArray();
  106.         for (int i = 0; i < arr.length; i++) {
  107.             System.out.println(arr[i]);
  108.         }
  110.         //拓展: 数组转换为集合(调用数组工具类——Arrays类的静态方法asList())
  111.         System.out.println(Arrays.asList(new String[]{"AA", "BB"}));
  113.         List list = Arrays.asList(new int[]{14, 23});
  114.         System.out.println(list.size());
  116.         //iterator():返回iterator接口的实例。用于遍历集合元素
  117.     }
  118. }

Iterator迭代器接口

迭代器模式

定义
提供一种方法访问一个容器（container）对象中各个元素，而又不暴露该对象的内部细节。迭代器模式，就是为容器而生

Iterator接口内部方法

方法
hasNext()
判断迭代器中当前指针下一个地址是否有数据
next()
获取迭代器中当前指针下一个地址的数据
remove()
可以在遍历的时候，删除集合中的元素。此方法不同于集合直接调用remove()

如果还未调用next()或在上一次调用next方法之后已经调用了remove方法，再调用remove都会报IllegalStateException

  1. @Test
  2.     public void test1() {
  3.         Collection coll = new ArrayList();
  4.         coll.add(123);
  5.         coll.add(456);
  6.         coll.add(new String("Tom"));
  7.         coll.add(false);
  9.         Iterator iterator = coll.iterator();
  10.         //方式一：
  11. //        System.out.println(iterator.next());
  12. //        System.out.println(iterator.next());
  13. //        System.out.println(iterator.next());
  14. //        System.out.println(iterator.next());
  15. //
  16. //        //报异常：NoSuchElementException
  17. //        System.out.println(iterator.next());
  19.         //方式二（不推荐）
  20.         for (int i = 0; i < coll.size(); i++) {
  21.             System.out.println(iterator.next());
  22.         }
  24.         //方式三（推荐）
  25.         while (iterator.hasNext()) {
  26.             System.out.println(iterator.next());
  27.         }
  28.     }

迭代器的执行原理

  1. //hasNext()判断是否还有下一个元素
  2. while (iterator.hasNext()) {
  3.     //next() ①指标下移 ②将下移以后集合位置上的元素返回
  4.     System.out.println(iterator.next());
  5. }

集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前

foreach循环

说明
jdk 5.0 新增了foreach循环，用于遍历集合、数组
使用
集合使用
for(集合元素的类型 局部变量：集合对象) {}
数组使用
for(数组元素的类型 局部变量：数组对象) {}

本质上也是使用的迭代器

Collection子接口一：List

概述

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组
List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引
List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素
JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector

List接口框架

简介
|——Collection接口：单列集合，用来存储一个一个的对象
|——List接口：存储有序的，可重复的数据 —> “动态”数组
|——ArrayList：作为List接口的主要实现类；线程不安全，效率高；底层使用Object[] elementData存储
|——LinkedList：对于频繁的插入、删除操作，使用此类的效率比ArrayList高；底层使用双向链表存储
|——Vector：作为List接口的古老实现类；线程安全，效率低；底层使用Object[] elementData存储
三者的异同
同：三个类都实现了List接口，存储数据的特点相同（存储有序的，可重复的数据）
异：见以上三者的简介

ArrayList底层源码分析

jdk 7

  1. //底层创建了长度是10的Object[]数组elementData
  2. ArrayList list = new ArrayList();
  3. list.add(123); //elementData[0] = new Integer(123);
  4. ...
  5. list.add(11); //如果此次的添加导致底层elementData数组容量不够，则扩容


默认情况下，扩容为原来的容量的1.5倍，同时需要将原有的数组中的数据复制到新的数组中
结论：建议开发中使用带参的构造器 ArrayList list = new ArrayList(int capacity)
jdk 8

  1. ArrayList list = new ArrayList();//底层Object[] elementData初始化为{},并没有创建长度为10的数组
  2. list.add(123);//第一次调用add()时，底层菜创建了长度为10的数组，并将数据123添加到elementData数组中
  3. ...
  4. //后续的添加和扩容操作与 jdk 7 无异


小结
jdk 7中ArrayList的对象的创建类似于单例的饿汉式
jdk 8中ArrayLsit的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存

LinkedList底层源码分析

  1. LinkedList list = new LinkedList();//内部声明了Node类型的first和last对象，默认值为null
  2. list.add(123);//将123封装到Node中，创建了Node对象

其中Node定义为（体现了LinkedList的双向链表的说法）

  1. private static class Node<E> {
  2.         E item;
  3.         Node<E> next;
  4.         Node<E> prev;
  6.         Node(Node<E> prev, E element, Node<E> next) {
  7.             this.item = element;
  8.             this.next = next;
  9.             this.prev = prev;
  10.         }
  11. }

Vector源码分析

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

List接口中的常用方法

ListTest.java

区分List中remove(int index)和remove(Object obj)

Collection子接口二：Set

概述

①概念
无序性（以HashSet为例说明）
无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
不可重复性
保证添加的元素按照equals()判断时，不能返回true。即：相同的元素只能添加一个
②Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法

Set接口框架

简介
|——Collection接口：单列集合，用来存储一个一个的对象
|——Set接口：存储无序的，不可重复的数据 —> 类似于高中的”集合”
|—-HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
|——LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历；对于比较频繁的遍历操作，LinkedHashSet效率高于HashSet
|——TreeSet：可以按照添加对象的指定属性，进行排序

HashSet

HashSet添加元素过程
①我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值
②此哈希值接着通过某种算法计算出HashSet底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：
如果此位置上没有其他元素，则元素a添加成功（情况1）
如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较元素a与元素b的hash值；
如果hash值不相同，则元素a添加成功（情况2）
如果hash值相同，进而需要调用元素a所在类的equals()方法：
如果equals()方法返回true，元素a添加失败
如果equals()方法返回false，元素a添加成功（情况3）
③对于添加成功的情况2、3而言：元素a与已经存在指定索引位置上数据以链表的方式存储

jdk 7：元素a放到数组中，指向原来的元素 jdk 8：原来的元素在数组中，指向元素a

要求：向Set中添加的数据，其所在的类一定要重写hashCode()和equals()
要求：重写的两个方法尽可能保持一致性。（相等的对象必须具有相等的散列码）

重写两个方法的小技巧：对象中用作equals()方法比较的Field，都应该用来计算hashCode值

LinkedHashSet

LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据

对于比较频繁的遍历操作，LinkedHashSet效率高于HashSet

TreeSet

概述
向TreeSet中添加的数据，要求是相同类的对象
两种排序方式：自然排序（实现Compareable接口） 和 定制排序（Comparator接口）
自然排序中：比较两个对象是否相同的标准为：compareTo()是否返回0，不再是equals方法
定制排序中：比较两个对象是否相同的标准为：compare()是否返回0，不再是equals方法

Map接口

Map结构的理解

Map中的key是无序的，不可重复的，使用Set存储所有的key —-> key所在的类要重写equals()和hashCode() （以HashMap为例）
Map中的value是无序的，可重复的，使用Collection存储所有的value —-> value所在的类要重写equals()
一个键值对：key-value构成了一个Entry对象
Map中的Entry：无序的、不可重复的，使用Set存储所有的Entry

Map框架结构

|——Map：双列数据，存储key-value对的数据 —类似于高中的函数：y = f(x)
|——HashMap：作为Map的主要实现类；线程不安全，效率高；存储null的key和value
|——LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。
原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素
对于频繁的遍历操作，此类执行效率高于HashMap
|——TreeMap：保证按照添加的key-value进行排序，实现排序遍历（此时考虑key的自然排序或定制排序）；底层使用红黑树
|——Hashtable：作为古老的实现类；线程安全，效率低；不能存储null的key和value
|——Properties：常用来处理配置文件。key-value都是String类型

HashMap的底层实现原理

jdk 7

  1. HashMap map = new HashMap();
  2. //在实例化以后并执行第一次put()，底层创建了长度是16的一维数组Entry[] table
  3. //...可能已经执行过多成put了...
  4. map.put(key1,value1);
  5. /*
  6.  *   首先，调用key1所在类的hashCode()计算key1的哈希值，此哈希值经过某种算法计算以后，得到Entry数组中的存放位置
  7.  *          如果此位置上的数据为空，此时key1-value1添加成功   ---情况1
  8.  *          如果此位置上的位置不为空（意味着此位置上存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据
  9.  *          的哈希值
  10.  *              如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功    ---情况2
  11.  *              如果key1的哈希值与某一个数据（key2-value2）的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较
  12.  *                  如果equals()返回false，此时key1-value1添加成功     ---情况3
  13.  *                  如果equals()返回true，使用value1替换value2          
  14.  */

补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储

扩容
在不断地添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，扩容
默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来
jdk 8
1. new HashMap()：底层没有创建一个长度为16的数组
2. jdk 8底层的数组是： node[] 而非 Entry[]
3. 首次调用put()时，底层创建长度为16的数组
4. jdk 7底层结果只有数组+链表，jdk 8底层结果为：数组+链表+红黑树

当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8且当前数组的长度 > 64，此时此索引位置上的所有数据改为使用红黑树存储

DEFAULT_INITIAL_CAPACITY: HashMap的默认容量: 16
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子: 0.75（提前扩容的目的在于尽量利用数组，减少链表的出现。0.75是通过统计学不断测试验证出来的）
threshold: 扩容的临界值（默认为160.75=12）=容量加载因子
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值，转化为红黑树
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量
关于负载因子

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

LinkedHashMap底层实现原理

LinkedHashMap作为HashMap的子类，在HashMap的基础上，继承了Node为Entry，并新增加了before，after用于记录数据添加的先后顺序

  1. static class Entry<K,V> extends HashMap.Node<K,V> {
  2.      Entry<K,V> before, after;//能够记录添加的元素的先后顺序
  3.      Entry(int hash, K key, V value, Node<K,V> next) {
  4.          super(hash, key, value, next);
  5.      }
  6.  }

Map接口的常用方法

MapTest.java

TreeMap两种排序方式

TreeMapTest.java

Properties

PropertiesTest.java

HashMap 和 Hashtable的异同？

CurrentHashMap 与 Hashtable的异同？

Collections工具类

CollectionsTest.java