Java - 集合类库详解

发表于 更新于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 10 分钟

集合的概述

集合的由来

  • 当需要在 Java 程序中记录单个数据内容时，则声明一个变量。
  • 当需要在 Java 程序中记录多个类型相同的数据内容时，声明一个一维数组。
  • 当需要在 Java 程序中记录多个类型不同的数据内容时，则创建一个对象。
  • 当需要在 Java 程序中记录多个类型相同的对象数据时，创建一个对象数组。
  • 当需要在 Java 程序中记录多个类型不同的对象数据时，则准备一个集合。

    集合的框架结构

  • Java 中集合框架顶层框架是：java.util.Collection 集合和 java.util.Map 集合。
  • 其中 Collection 集合中存取元素的基本单位是：单个元素
  • 其中 Map 集合中存取元素的基本单位是：单对元素

Collection 集合

基本概念

java.util.Collection 接口是 List 接口、 Queue 接口以及 Set 接口的父接口，因此该接口里定义的方法既可用于操作 List 集合，也可用于操作 Queue 集合和 Set 集合。

image

常用方法

方法声明功能介绍

|boolean add (E e)| 向集合中添加对象 |
|boolean addAll (Collection< ? extends E> c)| 用于将参数指定集合 C 中的所有元素添加到当前集合中 |

|boolean contains (Object o)| 判断是否包含指定对象 |
|boolean containsAll (Collection< ?> c)| 判断是否包含参数指定的所有对象 |
|boolean retainAll (Collection< ?> c)| 保留当前集合中存在且参数集合中存在的所有对象（交集）|
|boolean remove (Object o)| 从集合中删除对象 |
|boolean removeAll (Collection< ?> c)| 从集合中删除参数指定的所有对象 |
|void clear ()| 清空集合 |
|int size ()| 返回包含对象的个数 |
|boolean isEmpty ()| 判断是否为空 |
|boolean equals (Object o)| 判断是否相等 |
|int hashCode ()| 获取当前集合的哈希码值 |
|Objecto toArray ()| 将集合转换为数组 |
|Iterator<E> iterator | 获取当前集合的迭代器 |

Iterator 接口

java util.Iterator 接口主要用于描述迭代器对象，可以遍历 Collection 集合中的所有元素。
java.util.Collection 接口继 Iterator 接口，因此所有实现 Collection 接口的实现类都可以使用该迭代器对象。

方法声明功能介绍
boolean hasNext()判断集合中是否有可以迭代 / 访问的元素
E next()用于取出一个元素并指向下一个元素
void remove()用于删除访问到的最后一个元素

List 集合

基本概念

  • java.util.List 集合是 Collection 集合的子集合，该集合中允许有重复的元素并且有先后放入次序。
  • 该集合的主要实现类有: ArrayList 类、 LinkedList 类、 Stack 类、 Vector 类。
  • 其中 ArrayList 类的底层数据管理的，支持下标访问，增删元素不方便。
  • 其中 Linkedlist 类的底层是采用双向链表进行数据管理的，访问不方便，增删元素方便。
  • 可以认为 ArrayList 和 lInkedlIst 的方法在逻辑上完全样，只是在性能上有一定的差别，ArrayList 更适合于机访问而 Linkedlist 更适合于插入和删除；在性能要求不是特别苛刻的情形下可以忽略这个差别。
  • 其中 Stack 类的底层是采用动态数组进行数据管理的，该类主要用于描述一种具有后进先出特征的数据结构叫做栈 (last in first out LIFO)。
  • 其中 Vector 类的底层是采用动态数组进行数据管理的，该类与 ArrayList 类相比属于线程安全的类，效率比较低。

常用方法

方法声明功能介绍
void add(int index, E element)向集合中指定位置添加元素
boolean addAll(int index, Collection< ? extends E > c)向集合中添加所有元素
E get(int index)从集合中获取指定位置元素
int indexof(Object o)查找参数指定的对象
int lastIndexOf(Object o)查找参数指定的对象
E set(int index, E element)修改指定位置的元素
E remove(int index)删除指定位置的元素
List< E > subList(int fromIndex, int tolndex）用于获取子 List

Queue 集合

基本概念

  • java.util.Queue 集合是 Collection 集合的子集合，与 List 集合属于平级关系。
  • 该集合的主要用于描述具有先进先出特征的数据结构，叫做队列 (first in first out FIFO)。
  • 该集合的主要实现类是 Linkedlist 类，因为该类在增删方面比较有优势。

常用方法

方法声明功能介绍
boolean offer(E e)将一个对象添加至队尾，若添加成功则返回 true
E poll()从队首删除并返回一个元素
E peek()返回队首的元素 (但并不删除)

Set 集合

基本概念

  • java util.Set 集合是 Collection 集合的子集合，与 List 集合平级。
  • 该集合中元素没有先后放入次序。且不允许重复。
  • 该集合的主要实现类是: HashSet 类和 TreeSet 类以及 LinkedhashSet 类
  • 其中 HashSet 类的底层是来用哈希表进行数据管理的。
  • 其中 Treeset 类的底层是采用红黑树进行数据管理的。
  • 其中 LinkedHashSet 类与 HashSet 类的不同之处在于内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺序，因此便于迭代。

image

TreeSet 集合

  • 二叉树主要指每个节点最多只有两个子节点的树形结构。
  • 满足以下 3 个特征的二叉树叫做有序二叉树:
    a 左子树中的任意节点元素都小于根节点元素值；
    b 右子树中的任意节点元素都大于根节点元素值；
    c 左子树和右子树的内部也遵守上述规则；
  • 由于 TreeSet 集合的底层采用红黑树进行数据的管理，当有新元素插入到 TreeSet 集合时，需要使用新元素与集合中已有的元素依次比较来确定新元素的合理位置。
  • 比较元素大小的规则有两种方式。
    使用元素的自然排序规则进行比较并排序，让元素类型实现 java.lang.Comparable 接口；
    使用比较器规则进行比较并排序，构造 TreeSet 集合时传入 java.util.Comparator 接口；
  • 自然排序的规则比较单一，而比较器的规则比较多元化，而且比较器优先于自然排序。

常用的方法

  • 参考 Collection 集合中的方法即可

元素放入 HashSet 集合的原理

  • 使用元素调用 hashCode 方法获取对应的哈希码值，再由某种哈希算法计算出该元素在数组中的索引位置。
  • 若该位置没有元素，则将该元素直接放入即可。
  • 若该位置有元素，则使用新元素与已有元素依次比较哈希码值，若哈希码值不相同，则将该元素直接放入。
  • 若新元素与已有元素的哈希码值相同，则使用新元素调用 equals 方法与已有元素依次比较。
  • 若相等则添加元素失败，否则将元素直接放入即可。
  • 思考：为什么要求重写 equa 方法后要重写 hashCode 方法呢？
  • 解析：
    当两个元素调用 equals方法相等时证明这两个元素相同，重写 hashCode 方法后保证这两个元素得到的哈希码值相同，由同一个哈希算法生成的索引位置相同，此时只需要与该索引位置已有元素比较即可，从而提高效率并避免重复元素的出现。

Map 集合

基本概念

  • java.util.Map<K,V> 集合中存取元素的基本单位是：单对元素，其中类型参数如下：
    K - 此映射所维护的键 (Key) 的类型，相当于目录
    V - 映射值 (value) 的类型，相当于内容。
  • 该集合中 key 是不允许重复的，而且一个 key 只能对应一个 value
  • 该集合的主要实现类有 HashMap 类、 TreeMap 类、 LinkedHashMa p 类、 HashTable 类、Properties 类
    其中 HashMap 类的底层是采用哈希表进行数据管理的。
    其中 TreeMap 类的底层是采用红黑树进行数据管理的。
    其中 LinkedHashMap 类与 HashMap 类的不同之处在于内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺，因此便于迭代。
    其中 HashTable 类是古老的 Map 实现类，与 HashMap 类相比属于线程安全的类，且不允许 null 作为 key 或者 value 的数值。
    其中 Properties 类是 HashTable 类的子类，该对象用于处理属性文件，key 和 value 都是 String 类型的
  • Map 集合是面向查询优化的数据结构，在大数据量情况下有着优良的查询性能。
  • 经常用于根据 key 检索 value 的业务场景

image

常用方法

方法声明功能介绍
V put(K key, V value)将 Key-Value 对存入 Map，若集合中已经包含该 Key，则替换该 Key 所对应的 Value，值为该 Key 原来所对应的 Value, 若没有则返回 Null
V get(Object key)返回与参数 Key 所对应的 Value 对象，如果不存在则返回 null
boolean containsKey(Object key)判断集合中是否包含指定的 Key
boolean containsValue(Object value)判断集合中是否包含指定的 Value
V remove(Object key)根据参数指定的 key 进行删除
Set< k > keySet返回此映射中包含的键的 Set 视图
Collection< v > values()回此映射总包含的值的 Se 视图
Set< Map.Entry< K,V > entrySet() >返回此映射中包含的映射的 Set 视图

元素放入 HashMap 集合的原理

  • 使用元素的 key 调用 hashCode 方法获取对应的哈希码值，再由某种哈希算法计算在数组中的索引位置。
  • 若该位置没有元素，则将该键值对直接放入即可。
  • 若该位置有元素，则使用 key 与已有元素依次比较哈希值，若哈希值不相同，则将该元素直接放。
  • 若 key 与已有元素的哈希值相同，则使用 key 调用 equals 方法与已有元素依次比较。
  • 若相等则将对应的 value 修改，否则将键值对直接放入即可。

相关的常量

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