Java基础之Collection

发布于：2023-01-22 ⋅ 阅读:(409) ⋅ 点赞:(0)

Collection

文章目录

  • 集合层次结构中的根接口

    • JDK不提供此接口的任何直接实现
      • 提供更具体的子接口（如Set和List ）的实现
      • 通常用于传递集合并在需要最大通用性的地方操作
    • 两个标准构造函数：
      • 无参构造：创建空集合
      • 单个参数类型的构造函数：创建具有与其参数相同的元素的新集合
        • 允许用户复制任何集合，生成所需实现类型的等效集合
      • 无法强制执行此约定，接口不能包含构造函数
        • 但Java平台库中的所有通用Collection实现都遵守
    • 接口中包含修改其操作的集合的方法
      • 集合不支持操作时抛出UnsupportedOperationException
        • 如果调用对集合没有影响，方法可能会（不是必须）抛出UnsupportedOperationException
        • 例如要添加的集合为空，在不可修改的集合上调用addAll(Collection)方法可能会（不是必须）抛出异常

  • 保存数据都是单个对象，动态保存数据对象

    • 在 JDK1.5 之前 Collection 只是一个独立接口

      • JDK 1.5 之后 提供了 Iterator 父接口
      • JDK 1.8之后对 Iterator 接口也有扩充

    • 在 JDK 1.2 ~ JDK 1.4 时代进行集合使用往往直接操作Collection 接口

    • 从 JDL1.5 之后 更多使用其两个子接口

      • List：允许重复
      • Set：不允许重复

  • 在这里插入图片描述

  • 方法 作用
    public boolean add(E e) 向集合保存数据
    public boolean addAll( Collection <? extends E> c) 追加一组数据
    public void clear() 清空集合
    public boolean contains(object o) 查询数据是否存在（需要equals() 方法支持）
    public boolean remove(Object o) 数据删除（需要 equals() 方法支持）
    public int size() 获取数据长度
    public Object[] toArray() 将集合变为对象数组返回
    public Iterator <E> itrator() 将集合变为 Iterator 接口返回，遍历集合元素

AbstractCollection

  • 实现 Collection 接口的抽象类
  • 实现不可修改的集合，只需要扩展此类并iterator和size方法的实现
    • 迭代器方法返回的迭代器必须实现hasNext和next
  • 实现可修改的集合，必须还要重写add方法
    • 否则会抛出UnsupportedOperationException
    • 迭代器方法返回的迭代器必须另外实现remove方法

AbstractList

  • 继承AbstractCollection ，实现 List 接口的抽象类
  • 随机访问数据存储（例如数组）支持
    • 对于顺序访问数据（如链表），优先使用AbstractSequentialList而非此类
  • 实现不可修改的列表，只需要扩展此类并提供get(int)和size()方法的实现
  • 实现可修改的列表，必须还要重写set(int, E)方法
    • 否则抛出UnsupportedOperationException
    • 如果列表是可变大小，则必须另外覆盖add(int, E)和remove(int)方法
  • 不必提供迭代器实现
    • 迭代器和列表迭代器由此类在 随机访问 方法上实现
      • get(int)、set(int, E)、add(int, E)和remove(int)方法
AbstractSequentialList

  • 继承 AbstractList 的抽象类

  • 提供对数据元素的链式访问而非随机访问

    • 对于随机访问数据（如数组），优先使用AbstractList而非此类。

  • 此类与AbstractList类相反

    • 实现随机访问方法 get(int index)、set(int index, E element)、add(int index, E element)和remove(int index))
      • 是在列表的列表迭代器之上
      • AbstractList类是基于随即访问方法实现迭代器

  • 实现列表，只需要扩展此类并提供listIterator和size方法的实现

    • 不可修改的列表，只需实现列表迭代器的hasNext、next、hasPrevious、previous和index方法
    • 可修改的列表，应该另外实现列表迭代器的set方法
    • 可变大小的列表，应该另外实现列表迭代器的删除和添加方法
LinkedList

  • 继承AbstractSequentialList，实现List、Deque接口的实现类

  • 基于链表实现

    • 底层实现了 双向链表 和 双端队列 特点

    • 可以添加任意元素，可重复（包括 null）

  • 没有同步方法，多个线程同时访问一个List须手动实现访问同步

  • 查找时需要从头遍历，效率低

  • 详细介绍如下 List 中

ArrayList
  • 继承 AbstractList，实现 List 接口的实现类
    • 实现可变大小的数组，ArrayList 增长当前长度的50%
  • 随机访问和遍历元素效率高
    • 插入删除会改变后续所有元素位置，效率低
  • 非同步，多个线程同时访问一个List须手动实现访问同步
  • 详细介绍如下 List 中

AbstractSet

  • 继承AbstractCollection，实现Set接口的抽象类
  • 扩展此类实现集合的过程与通过扩展 AbstractCollection 实现集合的过程相同
    • 该类的子类中的所有方法和构造函数都必须遵守Set接口施加的附加约束
    • 例如：add方法不得允许将对象的多个实例添加到集合中
  • 此类不会覆盖AbstractCollection类的任何实现
    • 只添加了equals和hashCode的实现
HashSet
  • 继承AbstractSet，实现Set接口的实现类
  • 不允许出现重复元素
    • 允许包含值为null的元素，但最多只能一个
  • 不保证集合中元素的顺序
  • 详细介绍如下 Set 中
LinkedHashSet
  • 继承HashSet，实现Set接口
  • 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现
  • 详细效果如下 Set 中
TreeSet
  • 继承AbstractSet，实现 NavigableSet 接口
    • 可以实现排序等功能
  • 详细介绍如下 Set 中

AbstractQueue

  • 继承AbstractCollection，实现 Queue 接口
  • 提供一些 Queue 操作的实现
  • 基本实现不允许空元素时，此类是合适的
    • 方法add、remove和element分别基于offer、poll和peek
    • 但抛出异常而不是通过false或null返回来指示失败
PriorityQueue
  • 基于优先级堆的无界优先级队列，使用方式跟 Queue 相同
    • 元素排序：根据自然顺序或在队列构建时提供的Comparator
      • 取决于使用的构造函数
    • 不允许null元素
    • 不允许插入不可比较的对象
      • 即对象需要实现Comparable接口
      • 否则可能导致ClassCastException
  • 队列的头部是相对于指定排序的最小元素
    • 如果多个元素以最低值绑定，则头部是这些元素之一
  • 队列检索操作：poll、remove、peek和element访问队列头部的元素
  • 优先级队列无界，但具有控制用于存储队列元素的数组大小的内部容量
    • 总是至少与队列大小一样大
    • 随着元素被添加容量会自动增长
  • 此类及其迭代器实现了Collection和Iterator接口的所有可选方法
    • iterator()中提供的 Iterator不能保证以任何特定顺序遍历优先级队列的元素
    • 需要有序遍历，使用Arrays.sort(pq.toArray())
  • 此实现不同步
    • 任何线程修改队列，则多个线程不应同时访问PriorityQueue实例
    • 使用线程安全的java.util.concurrent.PriorityBlockingQueue类
  • 此实现为入队和出队方法offer、poll、remove()和add提供 O(log(n)) 时间
    • remove(Object)和contains(Object)方法：线性时间
    • 检索方法:peek、element和size固定时间
      在这里插入图片描述

Queue

  • 继承Collection接口

    • 队列结构，先进先出（FIFO）
    • 例外：如优先级队列
      • 根据比较器或元素自然顺序进行排序
      • 对元素进行排序的 LIFO队列、堆栈(LIFO，后进先出)
      • 不必完全遵守先进先出规则

  • 操作两个端点：队尾 和 队首（队头）

  • 操作本质：所有数据通过队首依次进入

    • 队列的头部元素都可以通过remove()或poll()删除

  • 队列 和 栈

    • 队列：先进先出

    • 栈：先进后出

  • 队列的实现可以使用 LinkedList

    • Queue 实现了List 队列

    • 数据顺序为保存顺序

  • 通常不允许插入null元素

    • 部分实现不禁止插入null ，但不应将null插入到Queue
    • null也被poll方法用作特殊返回值，以指示队列不包含任何元素

  • 队列主要依靠Queue 接口中提供的方法处理

    • 方法都以两种形式存在

      1. 操作失败时抛出异常

      2. 返回特殊值(null或false，具体取决于操作)

        • 插入操作专为与容量受限的Queue实现一起使用设计

        • 大多数实现中，插入操作不会失败

  • 队列方法总结

    • equals和hashCode从Object继承，基于标识
      • 对于具有相同元素但具有不同排序属性的队列，基于元素的相等性并不好定义
    异常 特殊值
    插入 add(e) offer(e)
    消除 remove() poll()
    检查 element() peek()
    • offer(E e)、add() ：插入元素
      • offer()失败返回false，用于故障是正常而不是异常发生时使用
      • add()失败抛出异常
    • remove()、poll()：删除并返回队列的头部
      • 队列为空时remove()抛出异常，poll()返回null
    • element()、peek()：返回但不删除队列的头部

Deque

  • 实现Queue接口

  • ：双端队：支持两端元素插入和移除的线性集合

    • deque：是双端队列的缩写，发音：deck
    • 用作队列：产生 FIFO（先进先出）行为；元素在双端队列的末尾添加并从开头删除
    • 用作堆栈：产生 LIFO（后进先出）行为，从双端队列的开头推送和弹出元素
      • 优先使用此接口而不是旧的Stack类

  • 多数Deque实现对元素数量没有固定限制

    • 支持容量受限的双端队列以及没有固定大小限制的双端队列

  • 定义了访问双端队列两端元素的方法，不支持对元素的索引访问

    • 提供插入、删除和检查元素的方法
    • 不建议插入 null 元素
      • null被各种方法用作特殊返回值来指示双端队列为空

  • 方法都以两种形式存

    1. 操作失败时抛出异常
    2. 返回特殊值(null或false，取决于操作)
      • 插入操作专为容量受限的Deque实现设计
      • 在大多数实现中，插入操作不会失败

  • Deque 方法总结

    • 双端队列用作队列或堆栈时 peek 方法同样有效
      • 任何一种情况下，元素都是从双端队列的开头绘制的
    • 移除内部元素：removeFirstOccurrence和removeLastOccurrence
    • equals和hashCode从Object继承，基于标识
    头部 尾部
    异常 特殊值 异常 特殊值
    插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
    消除 removeFirst() pollFirst() removeLast() pollLast()
    检查 getFirst() peekFirst() getLast() peekLast()

    • Queue 和 Deque 方法比较

      • 从Queue接口继承的方法与Deque方法完全等价
      Queue Deque
      add(e) addLast(e)
      offer(e) offerLast(e)
      remove() removeFirst()
      poll() pollFirst()
      element() getFirst()
      peek() peekFirst()

      • Stack 和 Deque 方法比较

        • Stack 方法完全等同于Deque方法
        Stack Deque
        push(e) addFirst(e)
        pop() removeFirst()
        peek() peekFirst()
LinkedList
  • 继承AbstractSequentialList，实现List、Deque接口的实现类

List

  • Collection 的子接口

  • List 接口相比Collection 接口进行了方法扩充

    • 获取指定索引的数据：public E get(int index)
    • 修改指定索引数据：public E set(int index, E element)
    • 返回 ListIterator 接口：public ListIterator <E> listiterator()
      • 还有一些其他方法…
    • JDK 1.9 开始追加静态方法
      • List.of() 方法用于追加数据

  • 存储特征：保存顺序就是存储顺序

    • 支持索引操作

  • 最大特点：允许保存重复元素数据

  • List 本身是一个接口，需要使用子类完成定义才能使用，常用子类：

    • ArrayList：最常用，查找快，增删效率低

      • Vector：线程安全，但效率较低

    • LinkedList：链表结构，增删快，查找效率较低

ArrayList

介绍

  • List 子接口使用最多的子类

    • 继承了 AbstraceList 抽象类

  • 基于数组实现，允许保存 null（多个）

    • 基本等同于 Vector，可以动态修改的数组，没有固定大小限制
    • ArrayList 是线程不安全，Vector 是线程安全

  • 可以进行自定义对象的保存

    • 通过泛型约束
      • 保存元素实际上是对象，泛型 <E> 只能为引用数据类型
      • 对于基本数据类型需要使用包装类
    • 使用contain()、remove()等方法必须要重写自定义类的equals()方法

  • size 、isEmpty 、get、set、iterator和listIterator操作在恒定时间内运行

    • 添加操作以摊销常数时间运行，即添加 n 个元素需要 O(n) 时间

    • iterator和listIterator返回的迭代器是快速失败的
      在这里插入图片描述

构造

  • 分为无参和有参两种

    • 无参构造：使用默认定义的空数组
    • 有参构造：参数大于 0 时使用传入参数开辟数组空间
      • 否则使用默认空数组
  • private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};	// 默认容量实体元素数组，空数组
private static final Object[] EMPTY_ELEMENTDATA = {};					// 实体元素数组，空数组
transient Object[] elementData;											// 当前元素数组

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;				// 无参构造，指向默认容量实体元素数组，空数组
}

public ArrayList(int initialCapacity) {									// 有参构造，传入要构造的数组容量
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];					// 传入参数大于0，直接创建该容量大小数组
    } 
    else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;							// 参数为 0 ，指向空元素数组
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);	// 非法参数异常
    }
}
操作机制

  • ArrayList 中维护了 Object 类型空数组

    • 保存的数据实际上是在对象数组

  • 数据追加时若数组容量不够开辟新数组

    • 将原数组数据拷贝到新数组

  • 无参构造使用默认空数组（容量为0）

    • JDK 1.8 之前构造对象会默认直接开辟数组空间，容量为 10

    • 之后无参构造使用空数组，使用时初次开辟数组空间，容量为 10

    • 有参构造可指定初次开辟数组空间容量

  • 数组容量不足自动进行扩容（当前容量的 1.5 倍）

    • 无参构造初次添加数据开辟 10 容量空间

  • 使用 ArrayList 时建议初始化合适的数组容量，避免垃圾数组产生

扩容机制
  1. 无参构造：创建 elementData 空数组（未实例化）
    • 有参构造可指定集合初次开辟空间大小
  2. 追加数据：判断是否需要扩容
    • 以当前容量的 1.5 倍为界限自动扩容（开辟新数组）
    • 将原数组数据 copy 到新数组
      • 使用 Array.copy() 方法扩容
常用方法

  • ensureCapacity()：调整 arraylist 的大小

    • arraylist 会马上调整为指定的容量大小
    • 否则每次添加元素时都会调整 arraylist 的大小

  • trimToSize()

    • ArrayList 内部使用数组存储元素
      • 数组满时创建容量是当前数组的 1.5 倍的新数组，并将所有元素都将移至新数组
      • 设数组已满又添加新个元素，数组容量仍以相同的比例扩展（即前一个数组的1.5倍）
      • 此时数组将有一些未分配的冗余空间
    • trimToSize() 方法可以删除未分配的空间
      • 更改 ArrayList 的容量，使其等于 ArrayList 中的元素个数

  • forEach()

    • 与 for-each 循环不同：for-each 用于遍历数组中的每个元素

      • forEach(Consumer<E> action)遍历元素并执行特定操作，

        • action：对每个元素执行的操作

        • ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
// 所有元素 * 10
numbers.forEach((e) -> {				// lambda 表达式调用 forEach 遍历并执行操作
    e = e * 10;
    System.out.print(e + " ");
});
方法 描述
add(int index，Element e) 将元素插入到列表指定位置；index 没有传入实际参数，元素将追加至数组的最末尾
addAll(int index, Collection c) 添加集合中的所有元素到列表指定位置
clear() 删除所有元素（优先使用）
clone() 浅拷贝，复制一份 arraylist
contains(Object obj) 判断元素是否在列表中，内部使用 equals() 方法查找元素
get(int index) 通过索引值获取列表中的元素
indexOf(Object obj) 返回列表中元素的索引值
removeAll(Collection c) 删除存在参数集合中的 arraylist 里的所有元素（重复出现返回第一个）
remove(Object obj) remove(int index) 删除列表中匹配的单个元素（删除第一个）
size() 返回列表中元素数量
isEmpty() 判断列表是否为空；不存在元素则返回 true
subList(int fromIndex, int toIndex) 截取列表中指定位置的的元素
set(int index, Element e) 替换列表中指定索引的元素
sort(Comparator c) 对元素进行排序
toArray(T[] arr) 将列表转换为数组
toString() 将列表转换为字符串
ensureCapacity(int minCapacity) 设置指定容量大小的列表
lastIndexOf(Object obj) 返回指定元素最后一次出现的位置（不存在返回 -1）
retainAll(Collection c) 保留 arraylist 中在指定集合中存在的元素
containsAll(Collection c) 查看 arraylist 是否包含指定集合中的所有元素
trimToSize() 将 arraylist 的容量调整为数组中的元素个数
removeRange(int fromIndex, int toIndex) 删除 arraylist 中指定索引之间存在的元素
replaceAll(UnaryOperator<E> operator) 将给定的操作内容替换掉数组中每一个元素
removeIf(Predicate<E> filter) 删除所有满足特定条件的 arraylist 元素；如果元素被删除则返回 true
forEach(Consumer<E> action) 遍历 arraylist 中每一个元素并执行特定操作

LinkedList

介绍

  • 继承AbstractSequentialList，实现List、Deque接口

  • 基于链表实现：线性表；但并不按线性的顺序存储数据，而是节点中存到下一个节点的地址

    • 底层实现了 双向链表 和 双端队列 特点

    • 可以添加任意元素，可重复（包括null）

  • 没有同步方法，多个线程同时访问一个List须手动实现访问同步

    • 使用Collections.synchronizedList方法包装该列表

    • 最好在创建时完成，防止对列表的意外不同步访问

      • List list = Collections.synchronizedList(new LinkedList(...));

  • 使用方法和 ArrayList 相同，但实现机制完全不同

    • ArrayList 基于数组扩容实现
    • LinkedList：基于双向链表实现

  • 此类的iterator和listIterator方法返回的迭代器是快速失败的

在这里插入图片描述

构造
public LinkedList();			// 只有无参构造

public boolean add(E e) {		// 增加数据
	linkLast(e);				// 追加数据方法
    return true;
}

					
void linkLast(E e) {									// 追加数据到最后，链表实现；利用节点实现数据保存
    final Node<E> l = last;								// 尾节点
    final Node<E> newNode = new Node<>(l, e, null);		// 以尾节点为上一个节点，传参元素为数据 创建新节点
    last = newNode;  									// 为提高程序性能，每次保存上一次追加的节点，避免递归
    if (l == null)  			 						 
    	first = newNode;								// 尾节点为空，新节点为第一个节点
    else
	    l.next = newNode;  								// 否则追加到尾节点的下一个节点
    size++;												// 长度增加
    modCount++;											// 操作值增加，iterator中修改元素时异常原因
}
操作机制
实现
  • 底层维护了双向链表
    • 维护两个属性
      • first：首节点
      • last：尾节点
    • 节点（Node对象）中有三个属性
      • prev：指向前一个节点
      • next：指向后一个节点
      • item：保存当前节点数据
  • Linkedlist 的增删元素不通过数组完成：相对效率较高
    • 添加、删除元素通过链接、断开节点完成
    • 索引到列表中的操作将从开头或结尾遍历列表，效率较低
单向链表
  • 节点中包含两个属性

    1. 当前节点的数据

    2. 指向下一个节点的链接

在这里插入图片描述

双向链表
  • 节点包含三个属性
    1. 向前的节点链接
    2. 当前节点数据
    3. 向后的节点链接

在这里插入图片描述

方法列表
  • 以下情况 LinkedList 访问列表中的随机元素比 ArrayList 更高效
    • addFirst()、addLast()
    • removeFirst()、removeLast()
    • getFirst()、getLast()
    • 对链表首、尾元素进行操作无需遍历，可直接获取元素
方法 描述
public boolean add(E e) 添加元素到链表尾部，返回是否成功
public void add(int index, E element) 向指定位置插入元素
public boolean addAll(Collection c) 将一个集合的所有元素添加到链表后面，返回是否成功
public boolean addAll(int index, Collection c) 将一个集合的所有元素添加到链表的指定位置之后，返回是否成功
public void addFirst(E e) 添加元素到头部
public void addLast(E e) 添加元素到尾部
public boolean offer(E e) 向链表末尾添加元素，返回是否成功
public boolean offerFirst(E e) 头部插入元素，返回是否成功
public boolean offerLast(E e) 尾部插入元素，返回是否成功
public void clear() 清空链表
public E removeFirst() 删除并返回第一个元素
public E removeLast() 删除并返回最后一个元素
public boolean remove(Object o) 删除某一元素，返回是否成功
public E remove(int index) 删除指定位置的元素
public E poll() 删除并返回第一个元素
public E remove() 删除并返回第一个元素
public boolean contains(Object o) 判断是否含有某一元素
public E get(int index) 返回指定位置的元素
public E getFirst() 返回第一个元素
public E getLast() 返回最后一个元素
public int indexOf(Object o) 查找指定元素从前往后第一次出现的索引
public int lastIndexOf(Object o) 查找指定元素最后一次出现的索引
public E peek() 返回第一个元素
public E element() 返回第一个元素
public E peekFirst() 返回头部元素
public E peekLast() 返回尾部元素
public E set(int index, E element) 设置指定位置的元素
public Object clone() 克隆链表
public Iterator descendingIterator() 返回倒序迭代器
public int size() 返回链表元素个数
public ListIterator listIterator(int index) 返回从指定位置开始到末尾的迭代器
public Object[] toArray() 返回一个由链表元素组成的数组
public T[] toArray(T[] a) 返回一个由链表元素转换类型而成的数组

区别

都是 List 接口的一种实现

  1. ArrayList 底层是数组实现的集合，LinkedList 底层是链表实现的集合
  2. 使用 List 中 get() 方法获取数据时
    • ArrayList 的时间复杂度为 1
      • 根据索引获取，直接定位
    • LinkedList 的时间复杂度为 n（元素位置）
      • 遍历元素链表，从第一个开始
  3. ArrayList 使用时默认初始化容量为 0
    • 首次添加数据开辟 10 个空间，容量不足时进行 1.5 倍扩容
    • 保存大容量数据时可能会造成垃圾的产生和性能下降
    • 可以使用 LinkedList 保存

选择

  • 频繁访问、修改列表中元素：ArrayList
    • 频繁进行增删操作：LinkedList
  • 正常操作中查询较多所以主要使用 ArrayList
    • 根据具体业务情况灵活选择

Vector

  • 原始古老的程序类（JDK 1.0）

    • JDK 1.2 时许多开发者习惯使用且已经有系统使用

    • 考虑其当时使用广泛性将其保留下来，并实现了 List 接口

    • 类定义结构和 ArrayList 相同

  • 与 ArrayList 基本完全相同

    • 无参构造一定默认开辟容量为 10 的数组、
      • 后续按照 2 倍扩容
    public Vector(int initialCapacity, int capacityIncrement) {			// 有参构造，指定初始容量和扩容幅度		
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {								// 有参构造，开辟指定容量
    this(initialCapacity, 0);
}

public Vector() {													// 无参构造，调用有参构造开辟 10 容量
    this(10);
}

  • Vertor 所有操作方法采用同步处理

    • ArrayList 没有进行同步处理
    • Vertor 所有方法在多线程操作安全，但性能较低

Set

  • Collection 的子接口
    • 特点
      • 不允许保存重复元素
        • 最多保存一个 null
      • 无法根据指定索引操作
  • Set 并未扩充许多新方法
    • 在 JDK 1.9 之后有类似 List 的 of() 静态方法
      • Set.of()方法用于填充数据
  • Set 是一个接口，需要使用子类完成定义才能使用
    • 常用子类
      • HashSet
      • TreeSet

SortedSet

  • 继承Set接口

    • 添加的元素对象必须实现Comparator比较器接口
      • 所有元素必须是相互可比较的
    • 实现自然升序排列，可自定义排序规则
    • 是SortedMap的集合类似物

  • 元素使用自然顺序排序，或在排序集创建时提供的Comparator排序

  • 集合的迭代器将按元素升序遍历集合

  • 有序集合实现Set接口：由有序集合维护的排序（无论是否提供显式比较器）必须与 equals 一致

    • Set 接口根据 equals 操作定义，但排序集使用 compareTo 或 compare 方法执行所有元素比较
      • 从排序集的角度来看，equles方法认为相等的两个元素排序也是相等的

  • 实现类应该提供四个标准构造函数

    1. 无参数构造：创建空排序集，根据元素的自然顺序排序
    2. Comparator 类型单个参数的构造函数：创建空排序集，根据指定的比较器排序
    3. Collection 类型单个参数的构造函数：创建新排序集，其元素与其参数相同，根据元素的自然顺序排序
    4. SortedSet 类型单个参数的构造函数：创建新排序集，具有与输入排序集相同的元素和相同的顺序
NavigableSet

  • 继承SortSet接口

  • 使用导航方法扩展的SortedSet ，报告给定搜索目标的最接近匹配

  • 可按升序或降序访问和遍历NavigableSet

    E lower(E e);							    // 小于指定元素的元素
E floor(E e);								// 小于或等于指定元素的元素
E ceiling(E e);								// 大于或等于指定元素的元素
E higher(E e);								// 大于指定元素的元素
// 以上方法获得元素不存在时返回 null

E pollFirst();								// 删除并返回第一个元素，不存在时返回null
E pollLast();								// 删除并返回最后一个元素，不存在时返回 null

Iterator<E> iterator();						// 按升序返回迭代器对象

NavigableSet<E> descendingSet();			// 返回集合元素的逆序视图，等价 Collections.reverseOrder (comparator()) 

Iterator<E> descendingIterator();			// 按降序返回迭代器对象，等效于 descendingSet().iterator() 

NavigableSet<E> subSet(E fromElement, boolean fromInclusive,	// 返回元素范围：fromElement ~ toElement 集合部分视图
                       E toElement,   boolean toInclusive);		
/* 参数相等，则返回的集合为空，除非 fromInclusive 和 toInclusive 都为真 */
SortedSet<E> subSet(E fromElement, E toElement);	// 返回中元素范围：[fromElement toElement) 的视图，，参数相等返回空集合

NavigableSet<E> headSet(E toElement, boolean inclusive);		// 返回集合中小于 toElement 的视图，参数为 true 时等于 
SortedSet<E> headSet(E toElement);								// 返回集合中元素严格小于 toElement 的视图

NavigableSet<E> tailSet(E fromElement, boolean inclusive);		// 返回集合中元素大于 fromElement 的视图，参数为 true 时等于
SortedSet<E> tailSet(E fromElement);							// 返回集合中元素严格大于 fromElement 的视图

HashSet

介绍

  • 继承 AbstractSet<E>，实现 Set<E>接口

    • 不是线程安全的
      • 多线程访问时必须显式同步对 HashSet 的并发访问
    • 存储元素实际是对象，基本类型需要使用包装类
    • 迭代器方法返回的迭代器是快速失败的

  • 存储特点

    • 最大特点：数据无序
    • 不允许保存重复元素
      • 可以存放 null，但只能有一个

  • 实际底层使用 HashMap 实现

    • 有固定的value值，由于Map中key不允许重复，Set无法保存重复元素

    • private static final Object PRESENT = new Object();   // 填充 Map 中 value 的固顶对象

public HashSet() {
    map = new HashMap<>();							 // 无参构造，实际创建 HashMap 对象
}

public HashSet(Collection<? extends E> c) {			// 有参构造，使用集合对象创建 Set
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));	// 创建指定初始化容量的 HashMap 对象
    addAll(c);										// 将集合元素添加到 HashMap 中		
}

public boolean add(E e) {
    return map.put(e, PRESENT) == null;				// 添加元素，使用固定 value 值
}
底层机制
机制

  • 实际使用 HashMap 存储数据

    • 底层数据结构为：数组 + 链表 + 红黑树

  • 数据保存为 Map 中的 key，用常量对象填充 value

    • 所以无法添加重复对象
    • 添加、扩容、树化机制都源于 HashMap 进行
添加元素

  1. 获取元素哈希值

    • 通过 hashCode 方法

  2. 对哈希值进行计算得出元素在哈希表中存放的位置

  3. 该位置没有元素，直接存放

    • 判断哈希表容量是否达到阈值
    • 满足条件后进行扩容

  4. 该位置已存在元素，进行相等判断（通过 equals 方法）

    • 相等时不再添加
    • 不相等时以链表方式追加到最后
      • 追加后进行链表树化判断
        • 满足条件后开启树化
    /**
* HashMap 中实际添加元素的方法
* @param hash 哈希值
* @param key  key
* @param value value
* @param onlyIfAbsent 为 true 不更改现有value值
* @param evict 为 false 则处于创造模式
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)             // 哈希表未初始化
        n = (tab = resize()).length;                                // 进行哈希表扩容并获取长度                                                
    if ((p = tab[i = (n - 1) & hash]) == null)                      // 获取该位置的哈希值并判断是否为空
        tab[i] = newNode(hash, key, value, null);                   // 为空时直接创建新节点放到该位置
    else {
        Node<K,V> e; K k;
        // 该位置哈希值和当前元素哈希值相等、且 key 和当前元素 key 相等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))       
            e = p;                                                                          // 直接使用该位置节点
        else if (p instanceof TreeNode)                                                     // 判断该位置节点是否是 树节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);                 // 转为树节点并进行树化元素添加
        else {                                                                              
            // 该节点不是树节点，且和当前元素哈希值、key都不相等
            for (int binCount = 0; ; ++binCount) {                                          // 遍历该位置所有节点元素
                if ((e = p.next) == null) {                                                 
                    // 判断是否是该位置链表中最后一个节点，执行到此时 e == null
                    p.next = newNode(hash, key, value, null);                               // 创建新节点作为下一个节点
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                    // 判断该位置链表是否达到树化标准
                        treeifyBin(tab, hash);                                              // 进行树化                             
                    break;                                                                  // 退出遍历
                }
                // 判断所有节点中有与该元素 哈希值、key 相等时退出遍历 
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;                                                                  
                p = e;                                                                      // 更新当前节点
            }
        }
        if (e != null) {								// 已存在对应的 key-value；否则此时 e 应该为 null
            V oldValue = e.value;						// 获取此时节点 value 值 
            if (!onlyIfAbsent || oldValue == null)		// 判断是否允许修改元素 或 value 是否为 bull    
                e.value = value;                        // onlyIfAbsent 为 true 或 此节点 value 值为 null 赋值当前元素 value 
            afterNodeAccess(e);
            return oldValue;    						// 返回原 value 值；未插入新元素，仅更新 key 对应的 value值，不更新修改次数
        }
    }
    ++modCount;                                         // 更新修改次数
    if (++size > threshold)                             // 判断长度是否达到扩容阈值                        
        resize();                                       // 进行扩容
    afterNodeInsertion(evict);
    return null;                                        // 新添加元素时返回原value 为 null
}
扩容逻辑
  • HashMap 初始化容量 16
    • 默认常量：DEFAULT_INITIAL_CAPACITY = 16
  • 超过当前容量的扩充阈值时进行扩容
    • 加载因子
      • DEFAULT_LOAD_FACTORY = 0.75
      • 即超过当前容量的 75% 时进行扩容
    • 阈值：例如初次扩容时阈值 = 当前容量 * 加载因子 = 12
      • 超过阈值进行自动扩容，二倍扩容
    • 数组中添加过12个元素即满足扩容条件
      • 同一条链表或多条链表总数达到临界值即触发
      • 而非数组总十二个空间占据元素
  • 添加元素后不满足树化所有条件时继续采用数组扩容机制
树化逻辑

  • JDK 1.8 后若一条链表元素个数到达默认值 8 且数据表 table 容量到默认值 64 会树化

    • TREEIFY_THRESHOLD = 8

    • MIN_TREEIFY_CAPACITY = 64

    • 仅满足单个条件不进行树化，仍先数组扩容

      // 表容量不到 64 时仍进行扩容
if(tab == null || tab.length < MIN_TREEIFY_CAPACITY((64)){
    resize();
}

TreeSet

介绍
  • 继承 AbstractSet<E>，实现 NavigableSet<E> 导航接口
    • 此实现不同步。多个线程同时访问且至少有一个线程修改了该树集，则必须在外部同步
    • 此类的iterator方法返回的迭代器是快速失败的
    • 为基本操作 add、remove和contains 提供有保证的 log(n) 时间成本
  • 元素使用自然顺序排序或在集合创建时提供的Comparator进行排序
    • 根据使用的构造函数
  • 实现Set接口，集合维护的顺序（无论是否提供显式比较器）必须与 equals 一致
    • Set 接口根据 equals 操作定义
    • TreeSet 实例使用其 compareTo 或 compare 方法执行所有元素比较

在这里插入图片描述

  • 与 HashSet 最大区别：保存数据有序
排序分析

  • TreeSet 保存的数据允许排序

    • 保存的数据类必须实现了Comparable接口

    • 实现此接口才可确认对象的大小关系

  • TreeSet 本质：底层利用 TreeMap 实现数据的存储

    • TreeMap 需要根据 Comparable 确定数据大小

    • 在进行自定义类对象比较时尽量将其所有属性依次进行大小匹配

      • 否则若仅有比对的属性相同会被认为是重复数据
      • 即 TreeSet 利用 Comparable 辨别重复数据

  • TreeSet 需要将类中所有属性进行比对

    • 实现难度较高
    • 实际开发首选 HashSet 子类进行存储

LinkedHashSet

  • 继承 HashSet， 实现 Set 接口

  • 底层使用 LinkedHashSet 实现

    • 维护 数组 + 双向链表 数据结构

    • 根据 hashCode 决定元素存储位置

    • 使用链表维护元素次序

      • 即 元素表现为以插入顺序保存
      • 将元素重新插入集合中，插入顺序不受影响

    • 不允许添加重复元素

  • 此实现不同步，多个线程同时访问哈希集，且至少一个线程修改了该集，则必须在外部同步

  • 此类的迭代器方法返回的迭代器是快速失败的
    | 在这里插入图片描述

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布