网站导航
> 文档中心 > Java集合框架--Collention和Map（一）

Java集合框架--Collention和Map（一）

网友: 文档中心 2022-03-25 23:49:22

Java集合框架概述

面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储，但是使用Array进行存储时又有一些弊端，而Java集合就像是一种容器，可以动态地将多个对象的引用放到容器中。

数组在内存中存储的特点

初始化后长度时固定的 ------>不便于扩展
数组声明的类型决定了元素初始化时的类型
数组存储的数据是有序的、可重复的----->存储数据的特点单一
数组提供的属性和方法少，不便于增删改查，且效率不高，并且无法直接获取存储元素的个数

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

 

Java可分为Collection（聚集）和Map（映射）两种体系

Collection接口：单列数据，定义了 存取一组对象 的方法的集合
  List：元素有序，可重复的集合
  Set：元素无序（TreeSet实现类有序），不可重复的集合
Map接口：双列数据，保存具有映射关系的key-value对的集合，定义了相关存取方法
 
 

Collection（聚集）集合和Map（映射）集合的接口继承树

在这里插入图片描述

注：实线代表继承，虚线代表实现
Map集合和Collection集合的容器工具类都是Collentions，不要因为名字像而混淆

在这里插入图片描述

Collection（聚集）接口

在这里插入图片描述

除了图上的List列表、Set集合子接口，还有
SortedSet有序集合、
Queue队列、
Deque双向队列、
BlockingQueue阻塞队列、
BlockingDeque阻塞双向队列、
BeanContext：Bean上下文 等子接口。

除了图上的一些Collection的接口实现类，还有
ArrayDeque数组双向队列、
EnumSet 枚举集合、
Stack栈、
DelayQueue延迟队列、
SynchronousQueue 同步队列、
LinkedBlockingDeque链式阻塞双向队列、
LinkedBlockingQueue链式阻塞队列等

  • Collection（聚集）接口是List、Set和Queue接口的父接口，因此Collection接口定义的方法对List集合、Set集合、Queue集合都可以操作
  • JDK对Collection接口无实现，而是对更具体的子接口进行实现
  • Java5之前没有泛型，Java集合会丢失容器中所有对象的类型并当做Object处理，Java5后有了泛型之后Java集合才可以记住容器中对象的数据类型

Collection接口方法

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

Iterator迭代器接口

  • Iterator对象被称为迭代器（设计模式的一种），主要用于遍历集合的元素
  • 迭代器模式：提供方法访问一个容器对象中的各个元素但是又不暴露该容器对象的内部细节，迭代器模式就是为了容器而生。
  • Collection接口继承了Java.lang.Iterable接口，那么所有实现了Collention接口的集合类都可以使用iterator()方法用来返回一个实现了Iterator接口的对象
  • Iterator仅用于遍历集合，而自身并无承载对象的能力，如果要创建Iterator对象，首先必须要有一个被迭代的集合
  • 集合对象每调用一次iterator()方法都得到一个新的迭代器对象，默认游标都是在第一个元素前
 迭代器方法 hasNext()：是否还有下一个元素 next()：①将指针下移 ②返回集合中当前所指向的元素 remove()：移除当前所指向的元素 （通过此迭代器对象的remove()方法而不是集合remove()方法）

在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。
Iterator可以删除集合的元素，但是是遍历过程中>>>通过迭代器对象的remove方 法<<<，不是集合对象的remove方法。
如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，
再调用remove都会报IllegalStateException。

foreach循环：

  • Java5提供了foreach循环访问Collection和数组
  • 遍历操作不需要获取Collection或数组的长度，无需使用索引访问元素
  • 底层调用Iterator----->使用数组方法map遍历一个数组可以返回一个新的数组，而foreach返回的数组为undefined（未定义）的原因就是Iterator没有承载对象的能力
     for(Person person:persons)   //persons是数据类型为person的列表   即for(元素类型 自定义元素名称：被遍历的数据结构的名称)

一、Collection接口继承----List接口

  • List接口继承Collection接口
  • 由于Java数组的局限性，常用List替代数组使用
  • List集合类中的元素：①有序 ②可重复
  • 每个元素都有对应的整数型的索引，记载其在容器中的位置，可以直接根据索引存取容器中的元素
  • List接口常用实现类有：ArrayList、LinkedList、Vector

 List接口方法
 除了从Collection集合继承的方法外，List集合增加了一些根据索引操作集合元素的方法

void add(int index, Object ele):在index位置插入ele元素boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来Object get(int index):获取指定index位置的元素int indexOf(Object obj):返回obj在集合中首次出现的位置int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置Object remove(int index):移除指定index位置的元素，并返回此元素Object set(int index, Object ele):设置指定index位置的元素为eleList subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合

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

1、List实现类①----ArrayList数组列表、动态数组
ArrayList本质上是一个不定长的数组
ArrayList在JDK1.8版本前后区别：
 JDK1.8前：饿汉式直接创建一个容量为10的数组        
 JDK1.8后：懒汉式先创建一个长度为0的数组，当添加第一个元素时再创建一个容量为10的数组

2、List实现类②–LinkedList链表、链式列表
LinkedList对插入和删除操作效率较高
LinkedList是一个双向链表，内部没有声明数组，而是定义了Node类型的first和last作为头结点和尾结点。同时定义内部类Node，作为LinkedList中保存数据的基本结构

LinkedList比List集合新增的方法 void addFirst(Object obj)  void addLast(Object obj)  Object getFirst() Object getLast() Object removeFirst() Object removeLast()
Node:  prev变量：记录前一个元素的位置   data变量：保存数据    next变量：记录下一个元素的位置   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、List实现类③----Vector
大多数操作和ArrayList相同，只是Vector是线程安全的

在大多数操作中默认使用ArrayList，频繁插入删除时使用LinkedList，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。

二、Collection接口继承2----Set接口

  • Set集合不能笼统的说是一个无序集合，因为Set的一个实现类TreeSet是有序的
  • Set接口是Collection接口的子接口，没有提供额外方法
  • Set集合不允许包含相同元素，添加两个相同元素到一个Set集合时，会添加失败
  • Set集合判断两个对象是否相等不是用==而是用equals()方法（记得重写）

1、Set实现类①----HashSet哈希集合
HashSet是Set接口的典型实现，大部分情况下使用Set集合都是使用HashSet这个类
HashSet按照Hash算法来存储元素，因此具有很好的存取、删除、查找性能
HashSet的特点：①非线程安全
        ②无法保证元素的排列顺序
        ③集合的元素可以是null
HashSet判断元素相等的标准：两元素通过调用hashcode()和equals()方法返回值都相等

对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

向HashSet中添加元素的过程：
① 当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法
来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象
在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在
数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，
该散列函数设计的越好）
② 如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果
为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，
那么会通过链表的方式继续链接。
③如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。
在这里插入图片描述HashSet底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）
就会扩大容量为原来的2倍。（16扩容为32，依次为64,128…等）

重写 hashCode() 方法的基本原则

  1. 在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。
  2. 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等
  3. 对象中用作equals() 方法比较的 Field，都应该用来计算 hashCode 值。

重写 equals() 方法的基本原则 以自定义的Customer类为例，何时需要重写equals()？

  1. 当一个类有自己特有的>>>逻辑相等<<<概念,当改写equals()的时候，总是 要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法， 它们仅仅是两个对象。
  2. 因此，违反了“相等的对象必须具有相等的散列码”。
  3. 结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

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

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

2、Set实现类②----HashSet的子类----LinkedHashSet链式哈希集合
LinkedHashSet 是 HashSet 的子类
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。
LinkedHashSet 不允许集合元素重复
在这里插入图片描述

3、Set实现类③----SortSet（有序集合）的实现类----TreeSet树集合

  • TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。
  • TreeSet底层使用红黑树结构存储数据，有序、查询速度比List快
  • TreeSet也新增了一些方法，暂时先不了解
  • TreeSet的两种排序方法：自然排序和定制排序，默认情况下使用自然排序

排序

自然排序：TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元
素之间的大小关系，然后将集合元素按升序(默认情况)排列
如果试图把一个对象添加到 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。否则，让人难以理解
Comparable 的典型实现：
数值型对应的包装类，例BigDecimal、BigInteger 等：按它们对应的数值大小 进行比较
Character：按字符的 unicode值来进行比较
Boolean：true 对应的包装类实例大于 false 对应的包装类实例
String：按字符串中字符的 unicode 值进行比较
Date、Time：后边的时间、日期比前面的时间、日期大

定制排序：
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。

参考：尚硅谷-Java基础-宋红康-第11章Java集合.pdf

网络标签：

相关问题