Java11-集合

NiuMT 2020-06-03 20:58:30
Java

数组在内存存储方面的特点：

数组在存储数据方面的弊端：

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

Collection 接口方法

Collection 接口：单列数据， 定义了存取一组对象的方法的集合

image-20201021230438466

接口方法：

  1. 添加：add(Object obj)；addAll(Collection coll)
  2. 获取有效元素的个数：int size()
  3. 清空集合：void clear()
  4. 是否是空集合：boolean isEmpty()
  5. 是否包含某个元素：boolean contains(Object obj); boolean containsAll(Collection c); 调用的obj.equals()方法，==需要重写equals()方法==
  6. 删除：boolean remove(Object obj) 只会删除找到的第一个元素；boolean removeAll(Collection coll) 取当前集合的差集；调用的obj.equals()方法，==需要重写equals()方法==
  7. 取两个结合的交集：boolean retainAll(Collection c), 把交集的结果存在当前集合中，不影响 c
  8. 集合是否相等：boolean equals(Object obj)
  9. 转成对象数组：Object[] toArray()
  10. 获取集合对象的哈希值：hashCode()
  11. 遍历：iterator() 返回迭代器对象，用于集合遍历

Iterator 迭代器接口

Iterator 对象称为迭代器 (设计模式的一种)，主要用于遍历 Collection 集合中的元素。

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

Collection 接口继承了 java.lang.Iterable 接口，该接口有一个 iterator() 方法，那么所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个实现了Iterator 接口的对象 。

Iterator 仅用于遍历集合 Iterator 本身并不提供承装对象的能力。如果需要 创建Iterator 对象，则必须有一个被迭代的集合。

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

在调用
it.next() 方法之前必须要调用 it.hasNext() 进行检测。若不调用，且下一条记录无效，直接调用 it.next() 会抛出 NoSuchElementException 异常。

image-20201022104231525

注意：

使用 foreach 循环遍历集合元素

Java 5.0 提供了 foreach 循环迭代 访问 Collection 和数组。遍历操作不需获取 Collection 或数组的长度，无需使用索引访问元素。==遍历集合的底层调用 Iterator 完成操作==。foreach 还可以用来遍历数组。

image-20201022105215546

Collection 子接口一： List

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

ArrayList 、 LinkedList 和 Vector的异同：

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

ArrayList

ArrayList 的 JDK1.8 之前与之后的实现区别？

本质上， ArrayList 是对象引用的 一个“变长”数组。

Arrays.asList (…) 方法返回的 List 集合 既不是 ArrayList 实例，也不是
Vector 实例。Arrays.asList (…) 返回值是一个固定长度的 List 集合。

LinkedList

新增方法：

LinkedList 双向链表内部没有声明数组，而是定义了 Node 类型的 first 和 last
用于记录首末元素。同时，定义内部类 Node ，作为 LinkedList 中保存数据的基本结构。 Node 除了保存数据，还定义了两个变量：

image-20201022112301081

LinkedList内部声明了Node类型的 first 和 last 属性，默认null。

Vector

新增方法：

面试题：请问
ArrayList/LinkedList/Vector 的 异同 谈谈你的理解？ ArrayList 底层是什么？扩容机制？ Vector 和 ArrayList 的最大区别？

ArrayList 和 LinkedList 的异同：二者都线程不安全，相对线程安全的Vector ，执行效率高。此外，ArrayList 是实现了基于动态数组的数据结构， LinkedList 基于链表的数据结构。对于随机访问 get 和 set ArrayList 绝对优于 LinkedList ，因为 LinkedList 要移动指针。对于新增和删除 操作 add (特指插入) 和 remove，LinkedList 比较占优势，因为 ArrayList 要移动数据。

ArrayList 和 Vector 的区别：Vector和 ArrayList 几乎是完全相同的，唯一的区别在于 Vector 是同步类 ( synchronized)，属于强同步类。因此开销就比 ArrayList 要大，访问要慢。正常情况下 大多数的 Java 程序员使用ArrayList 而不是 Vector, 因为同步完全可以由程序员自己来控制。 Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。 Vector 还有一个子类 Stack 。

@Test
public void testListRemove() {
    List list = new ArrayList();
    list.add(1);
    list.add(2);
    list.add(3);
    updateList(list);
    System.out.println(list);// 1 2
}
private static void updateList(List list)
    list.remove(2);
}

Collection 子接口二： Set

Set 接口是 Collection 的子接口， set 接口没有提供额外的方法；Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。

无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定

不可重复性：Set 判断两个对象是否相同是根据 equals() 方法，相同的元素只能添加一个。

添加元素的过程：

我们向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

总结：七上八下

HashSet底层：数组+链表的结构。

HashSet

底层也是数组，初始容量为 16，当如果使用率超过 0.75（16*0.75=12），就会扩大容量为原来的 2 倍。

要求：想set中添加的数据，其所在类 一定要重写hashcode()和equals()；

以Eclipse/IDEA 为 例 ，在自定义类中可以调用工具自动 重写 equals 和 hashCode 。问题：为什么 用 E clipse/IDEA 复写 hashCode 方法，有 31 这个数字？

  • 选择系数的时候要选择尽量大的系数。因为如果计算出来的 hash 地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）
  • 并且 31 只占用 5bits, 相乘造成数据溢出的概率较小。
  • 31 可以 由 i*31== (i<<5) 1 来表示 现在很多虚拟机里面都有做相关 优化 。 （提高算法效率）
  • 31 是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有 1 来整除 减少冲突

LinkedHashSet

LinkedHashSet 是 HashSet 的子类。

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

==LinkedHashSet 插入性能略低于 HashSet==，但在迭代访问 Set 里的全部元素时有很好的性能。

LinkedHashSet 不允许集合元素重复。

TreeSet

  1. 向TreeSet中添加的数据，要求是==相同的类型==；
  2. 两种排序方式：自然排序(compareTo)和定制排序(Comparator)
    • 自然排序：比较两个对象是否相同的标准为：compareTo()返回0。不再是equal()
    • 定制排序：将比较方法放到TreeSet的带参构造器中。比较两个对象是否相同的标准为：Compara()返回0。不再是equal()
  3. 如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable接口。
  4. TreeSet 是 SortedSet 接口的实现类， TreeSet 可以确保集合元素处于排序状态。、
  5. TreeSet 底层使用 红黑树 结构存储数据

新增的方法如下： 了解

TreeSet 两种排序方法： 自然排序 和 定制排序 。默认情况下， TreeSet 采用自然排序。

练习：在List 内去除重复数字值，要求尽量简单

//练习：在List内去除重复数字值，要求尽量简单
public static List duplicateList(List list) {
    HashSet set = new HashSet();
    set.addAll(list);
    return new ArrayList(set);
}
@Test
public void test2(){
    List list = new ArrayList();
    list.add(new Integer(1));
    list.add(new Integer(2));
    list.add(new Integer(2));
    list.add(new Integer(4));
    list.add(new Integer(4));
    List list2 = duplicateList(list);
    for (Object integer : list2) {
        System.out.println(integer);
    }
}

面试题

public void test3(){
    HashSet set = new HashSet();
    // 其中Person 类中重写了 hashCode() 和 equal() 方法
    Person p1 = new Person(1001,"AA");
    Person p2 = new Person(1002,"BB");

    set.add(p1);
    set.add(p2);
    System.out.println(set);//2个数据

    p1.name = "CC";
    set.remove(p1);// 删除失败，hashcode不一致
    System.out.println(set);
    set.add(new Person(1001,"CC"));// 3个数据
    System.out.println(set);
    set.add(new Person(1001,"AA"));// 4个数据
    System.out.println(set);
}

Map 接口

Map 接口： 双列数据，保存具有映射关系“ key-value对”的集合

image-20201021230536054

|----Map：双列数据
    |----HashMap：作为Map的主要实现类；线程不安全，效率高；存储null的key或value
        |----LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。对于频繁的遍历操作，此类执行效率高于HashMap
    |----TreeMap：保证按照添加的key-value对进行排序，实现遍历。此时考虑key的自然排序或者定制排序。底层使用红黑树。
    |----Hashtable：作为古老的实现类；线程安全，效率低；不能存储null的key或value
        |----Properties：常用来处理配置文件。key-value都是String类型。

Map 中的 key 和 value 都可以是任何引用类型的数据；Map 中的 key 用 Set 来存放， 不允许重复 ，即同一个 Map 对象所对应的类，须重写 hashCode 和 equals 方法；常用 String 类作为 Map 的“键”。

1.添加 、 删除、修改操作

2.元素 查询的操作：

3.元视图操作的方法：

HashMap

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

底层实现原理：

JDK 7及以前版本： HashMap 是数组 + 链表结构，即为链地址法

JDK 8版本发布以后： HashMap 是数组 + 链表 + 红黑树实现。

JDK 7:

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

JDK 8 相较于jdk7在底层实现方面的不同：

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

HashMap的put()

HashMap的put().png)

HashMap源码中的重要常量：

关于映射关系的key 是否可以修改? answer ：不要修改

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

面试题：负载因子值的大小，对 HashMap 有什么影响

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

LinkedHashMap

LinkedHashMap 是 HashMap 的子类；

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

与 LinkedHashSet 类似 LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致。

image-20201022223239758

TreeMap

TreeMap 存储 Key-Value 对时， 需要根据 key-value 对进行排序，所以key必须是同一个类创建的对象。
TreeMap 可以保证所有的 Key-Value 对处于有序状态 。

TreeSet 底层使用红黑树结构存储数据

TreeMap 的 Key 的排序：

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

Hashtable

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

与 HashMap 不同， Hashtable 不允许使用 null 作为 key 和 value

与 HashMap 一样， Hashtable 也不能保证其中 Key-Value 对的顺序

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

Properties

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

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

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

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

Collections 工具类

Collections 是一个操作 Set 、 List 和 Map 等集合的工具类；操作数组的工具类：Arrays

Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

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

查找、替换

Java10-枚举类与注解
Java12-泛型