数组与集合


1.集合与数组存储数据的概述：

集合、数组都是对多个数据进行存储操作的结构，简称Java容器
说明：此时的存储，主要指的是内存层面的存储。不涉及到持久化的存储（.txt，.jpg，.avi，数据库中）


2.数组存储的特点：

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


3.数组存储的弊端：

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


4.集合存储的优点：

解决数组存储数据方面的弊端

Collection接口


1.单列集合框架结构

**|—-Collection接口：单列集合，用来存储一个一个的对象
|—-list接口：存储有序的、可重复的数据。—-> ”动态”数组
|—-ArrayList、LinkedList、Vector

  1.    |---set接口：存储无序的，不可重复的数据 ---> 高中讲的“集合”<br />           |---HashSet、LinkedHashSet、TreeSet**

对应图示：
image.png

2.Collection接口常用方法：

add(Object obj),addAll(Collection coll),size(),isEmpty(),clear();
contains(Object obj),containsAll(Collection coll),
remove(Object obj),removeAll(Collection coll),
retainsAll(Collection coll),equals(Object obj);
hasCode(),toArray(),iterator();


3.Collection集合与数组间的转换

  1. //集合 ---> 数组：toArray()
  2. Object[] arr = coll.toArray();
  3. for (int i = 0; i < arr.length; i++) {
  4.     System.out.println(arr[i]);
  5. }
  7. //拓展：数组 ---> 集合：调用Arrays类的静态方法asList()
  8. List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
  9. System.out.println(list);
  11. List<int[]> arr1 = Arrays.asList(new int[]{123, 456});
  12. System.out.println(arr1.size());//1
  14. List arr2 = Arrays.asList(new Integer[]{123, 456});
  15. System.out.println(arr2.size());//2

4.使用Collection集合存储对象，要求对象所属的类满足：

  1. 向Collection接口的实现类的对象添加数据onj时，要求obj所在类要重写equals()


5.本章节对大家的要求：

层次一：选择合适的集合类去实现数据的保存，调用其内部的相关方法
层次二：不同的集合类底层的数据结构为何？如何实现数据的操作的：增删改查等

Iterator接口与foreach循环


1.遍历Collection的两种方式：

① 使用迭代器Iterator ② foreach循环（增强for循环）


2.java.utils包下定义的迭代器接口：Iterator
2.1说明：

  1. Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。
  2. GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。


2.2作用：遍历集合Collection元素

2.3如何获取实例：coll.iterator()返回一个迭代器实例

2.4遍历代码实现：

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


2.5图示说明：
image.png

2.6 remove()的使用：

  1. //如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用//remove都会报IllegalStateException
  2. //内部定义了remove()，可以在遍历的时候，删除集合中的元素，此方法不同于集合调用//remove()
  3. @Test
  4. public void test3(){
  5.     Collection coll = new ArrayList();
  6.     coll.add(123);
  7.     coll.add(456);
  8.     coll.add(new Person("Jerry",20));
  9.     coll.add(new String("Tom"));
  10.     coll.add(false);
  12.     //删除集合中“Tom”
  13.     Iterator iterator = coll.iterator();
  14.     while (iterator.hasNext()){
  15.         Object obj = iterator.next();
  16.         if ("Tom".equals(obj)){
  17.             iterator.remove();
  18.         }
  19.     }
  21.     //遍历集合
  22.     iterator = coll.iterator();
  23.     while (iterator.hasNext()){
  24.         System.out.println(iterator.next());
  25.     }
  27. }


3.JDK 5.0新特性—增强for循环：（foreach循环）
3.1.遍历集合举例：

  1. @Test
  2. public void test1(){
  3.     Collection coll = new ArrayList();
  4.     coll.add(123);
  5.     coll.add(456);
  6.     coll.add(new Person("Jerry",20));
  7.     coll.add(new String("Tom"));
  8.     coll.add(false);
  10.     //for(集合元素的类型 局部变量 : 集合对象)
  11.     for (Object obj : coll){
  12.         System.out.println(obj);
  13.     }
  15. }


说明：

内部仍然调用了迭代器


3.2.遍历数组举例：

  1. @Test
  2. public void test2(){
  3.     int[] arr = new int[]{1,2,3,4,445,87};
  5.     //for(数组元素的类型 局部变量 : 数组对象)
  6.     for (int i : arr){
  7.         System.out.println(i);
  8.     }
  9. }

Collection子接口：List接口


1.存储的数据特点：

|—-Collection接口：单列集合，用来存储一个一个的对象
|—-List接口：存储有序的、可重复的数据。—-> ”动态”数组，替换原有数组
|—-ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
|—-LinkedList：对于频繁的插入、删除操作，使用频率比ArrayList高；底层使用双向链表存储
|—-Vector：作为List接口的古老实现类；；线程安全的，效率低；底层使用Object[] elementData存储


2.常用方法：（记住）

增：add(Object obj)
删：remove(int index) / remove(Object obj)
改：set(int index,Object ele)
查：get(int index)
插： add(int index, Object ele)
长度：size()
遍历：① Iterator迭代器方式
② 增强for循环
③ 普通的循环


3.常用实现类：

|—-Collection接口：单列集合，用来存储一个一个的对象
|—-List接口：存储有序的、可重复的数据。—-> ”动态”数组，替换原有数组
|—-ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
|—-LinkedList：对于频繁的插入、删除操作，使用频率比ArrayList高；底层使用双向链表存储
|—-Vector：作为List接口的古老实现类；；线程安全的，效率低；底层使用Object[] elementData存储

4.源码分析（难点）

4.1 ArrayList源码分析：

* 2.1 JDK 7情况下：
ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementDate
 list.add(123);//elementDate[0] = new Integer(123);
…
 list.add(11);//如果此次的添加导致底层elementDate数组容量不够，则扩容
* 默认情况下，扩容为原来容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中

  • 结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

* 2.2 JDK 8中ArrayList的变化：
ArrayList list = new ArrayList();//底层Object[] elementDate初始化为{}，并没有创建长度为10的数组
 list.add(123);//第一次调用add()时，底层创建了长度10的数组，并将数据123添加到elementDate[0]
…
 后续的添加和扩容操作与JDK 7无异

* 2.3小结：

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

4.2 LinkedList源码分析：

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

4.3 Vector的源码分析：

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


5.存储的元素的要求：

添加的对象，所在的类要重写equals()方法


[面试题]

ArrayList、LinkedList、Vector三者的异同？
同：三个类都实现了List接口，存储数据的特点相同：存储有序的，可重复的数据
不同：见上

Collection子接口：Set接口


1.存储的数据特点：无序的、不可重复的元素
具体的：

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


2.元素添加过程：（以HashSet为例）

我们向HashSet中添加元素a，首先调用元素a所在类的HashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：
如果此位置上没有元素，则元素a添加成功。 —-> 情况一
如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较元素a与元素b的哈希值；
如果哈希值不相同，则元素a添加成功。 —-> 情况二
如果哈希值相同，进而需要调用元素a所在类的equals()方法；
equals()返回true，元素a添加失败
equals()返回false，则元素a添加成功 —-> 情况三

对于添加成功的情况二和情况三而言：元素a与已经存在指定索引位置上数据以链表的方式存储
JDK 7：元素a放到数组中，指向原来元素
JDK 8：原来的元素在数组中，指向元素a
总结：七上八下

HashSet底层：数组 + 链表的结构（前提：JDK 7）


3.常用方法

Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法


4.常用实现类：

  • |—-Collection接口：单列集合，用来存储一个一个的对象
    |—-set接口：存储无序的，不可重复的数据 —-> 高中讲的“集合”
     |—-HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
    |—-LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历。对于使用频繁的遍历操作，LinkedHashSet效率高于HashSet 在添加数据大的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据
     |—-TreeSet：可以按照添加的对象的指定属性，进行排序

5.存储对象所在类的要求：

HashSet / LinkedHashSet：

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


TreeSet：

1.自然排序中，比较两个对象是否相同的标准：compareTo()返回0，不再是equals()方法
2.定制排序中，比较两个对象是否相同的标准：compare()返回0，不再是equals()方法


6.TreeSet的使用
6.1使用说明：

1.向TreeSet中添加的数据，要求是相同类的对象
2.两种排序方式：自然排序（实现comparable接口）、定制排序（Comparator）


6.2常用的排序方式：

  1. //方式一：自然排序
  2. @Test
  3.     public void test1(){
  4.         TreeSet set = new TreeSet();
  6.         //错误的：不能添加不同类的对象
  7. //        set.add(123);
  8. //        set.add(456);
  9. //        set.add("AA");
  10. //        set.add(new User("Tom",12));
  12.         //举例一：
  13. //        set.add(123);
  14. //        set.add(12);
  15. //        set.add(13);
  16. //        set.add(23);
  17. //        set.add(-123);
  18. //        set.add(89);
  20.         //举例二：
  21.         set.add(new User("Tom",12));
  22.         set.add(new User("Jerry",52));
  23.         set.add(new User("Jim",22));
  24.         set.add(new User("Mike",63));
  25.         set.add(new User("Jack",25));
  26.         set.add(new User("Jack",56));
  28.         Iterator iterator = set.iterator();
  29.         while (iterator.hasNext()){
  30.             System.out.println(iterator.next());
  31.         }
  33.     }
  35. //方式二：定制排序
  36. @Test
  37. public void test2(){
  38.     Comparator com = new Comparator() {
  39.         //按照年龄从小到大排列
  40.         @Override
  41.         public int compare(Object o1, Object o2) {
  42.             if (o1 instanceof User && o2 instanceof User){
  43.                 User u1 = (User) o1;
  44.                 User u2 = (User) o2;
  45.                 return Integer.compare(u1.getAge(),u2.getAge());
  46.             }else {
  47.                 throw new RuntimeException("输入数据类型不匹配");
  48.             }
  49.         }
  50.     };
  52.     TreeSet set = new TreeSet(com);
  53.     set.add(new User("Tom",12));
  54.     set.add(new User("Jerry",52));
  55.     set.add(new User("Jim",22));
  56.     set.add(new User("Mike",63));
  57.     set.add(new User("Jack",25));
  58.     set.add(new User("Mary",25));
  59.     set.add(new User("Jack",56));
  61.     Iterator iterator = set.iterator();
  62.     while (iterator.hasNext()){
  63.         System.out.println(iterator.next());
  64.     }
  65. }

Map接口

双列集合框架：Map

1.常用实现类结构

  • |—-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及之前）
    * 数组 + 链表 + 红黑树（JDK 8）

[面试题]

  • 1.HashMap的底层实现原理？
  • 2.HashMap和Hashtable的异同？
  • 3.CurrentHashMap于Hashtable的异同？（暂时不讲）


2.存储结构的理解：

  • Map中的key：无序的、不可重复的，使用Set存储所有的key —-> key所在类重写equals()和hasCode()（以HashMap为例）

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

  • 一个键值对：key-value构成了一个Entry对象

  • Map中的entry：无序的、不可重复的，使用Set存储所有的entry


图示：

  • image.png

3.常用方法

  • 添加：put(Object key,Object value)
  • 删除：remove(Object key)
  • 修改：put(Object key,Object value)
  • 查询：get(Object key)
  • 长度：size()
  • 遍历：keySet() / values() / entrySet()


4.内存结构说明：（难点）
4.1 HashMap在JDK7中实现原理：

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

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

  • 在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来

4.2 HashMap在JDK8中相较于JDK7底层实现方面的不同：

  • 1.new HashMap()：底层没有创建一个长度为16的数组
    2.JDK 8底层的数组是：Node[]，而非Entry[]
     3.首次调用put()方法时，底层创建长度为16的数组
    4.JDK 7底层结构：数组 + 链表。JDK 8中底层结构：数组 + 链表 + 红黑树
     4.1 形成链表时，七上八下（JDK7：新的元素指向旧的元素。JDK8：旧的元素指向新的元素）
    * 4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8且当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树存储

4.3 HashMap底层典型的属性的说明：

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75
threshold：扩容的临界值，=容量填充因子，16 0.75 => 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树，8
*MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量，64

4.4 LinkedHashMap的底层实现原理（了解）

LinkedHashMap底层使用的结构与HashMap相同，因为LinkedHashMap继承于HashMap，区别就在于：LinkedHashMap内部提供了Entry，替换了HashMap中的Node

image.png

5.TreeMap的使用

向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
因为我们要按照key进行排序：自然排序、定制排序


6.使用Properties读取配置文件

  1. //Properties：常用来处理配置文件。key和value都是String类型
  2. public static void main(String[] args) throws IOException {
  3.     Properties pros = new Properties();
  4.     FileInputStream fis = new
  5.              FileInputStream("D:\\java0\\java23\\src\\jdbc.properties");
  6.     pros.load(fis);//加载对应流文件
  7.     String name = pros.getProperty("name");
  8.     String password = pros.getProperty("password");
  9.     System.out.println("name = " + name + ", password = " + password);
  10.     fis.close();
  11. }

Collections工具类的使用


Collections工具类
1.作用：操作Collection和Map的工具类

2.常用方法：
image.png
image.png

说明：ArrayList和HashMap都是线程不安全的，如果程序要求线程安全，我们可以将ArrayList和HashMap转换为线程安全的。
使用synchronizedList(List list) 和 synchronizedMap(Map map)

3.面试题：
面试题：Collection和Collections的区别？

数据结构简述

image.png
image.png
image.png
image.png