1. 云图网首页
  2. 技术专区
  3. Java

Java 集合

• Java


1. Java 集合类简介

1.1 集合概览

Java 集合类主要都是从 Collection 和 Map 两个接口派生而成，其中 Collection 又包含 List、Set 和 Queue，如下图。Java 集合就像容器，能够将多个同类型的对象装进该容器中，所以又叫容器。其中各集合含义如下：

  • Map：代表具有映射关系的集合，通过 key-value 存储，其中 key 是不可重复的，用于标识集合中的每项数据；
  • List：代表有序、可重复的集合；
  • Set：代表无序、不可重复的集合；
  • Queue：队列集合实现；

 

// jdk 1.8 中 Collection 的源码

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(java.util.Collection<?> c);

    boolean addAll(java.util.Collection<? extends E> c);

    boolean removeAll(java.util.Collection<?> c);

    ... //省略了其他方法
}

 

// jdk 1.8 中 Map 源码，其中内部接口 Entry<K, V> 对应 Map 的键值对

public interface Map<K,V> {
    int size();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    V put(K key, V value);

    V remove(Object key);

    void putAll(java.util.Map<? extends K, ? extends V> m);

    void clear();

    Set<K> keySet();

    Collection<V> values();

    Set<java.util.Map.Entry<K, V>> entrySet();

    interface Entry<K,V> {
        K getKey();

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();

        ...
    }

    boolean equals(Object o);

    int hashCode();

}

1.2 集合选用技巧

主要根据集合的特点来进行选择：

  1. 如果需要存放元素值：
    • 要保证元素唯一，选用实现 Set 接口的集合 HashSet 或 TreeSet；
    • 不用保证元素唯一，选择实现 List 接口的集合 ArrayList 或 LinkedList；
  2. 如果需要存放键值对：
    • 需要排序：选用 Map 接口下的 TreeMap；
    • 无需排序：选用 Map 接口下的 HashMap；
    • 保证线程安全：选用 Map 接口下的 ConcurrentHashMap；

2. 集合 vs 数组

集合和数组都是 Java 中重要的数据结构，两者之间的区别主要有如下两点：

不同点

数组

集合

容量

初始化时指定，只能存储定长数据

保存不定长的数据

存储的数据类型

基本数据类型，对象均可

只能是对象（基本数据类型要转换为封装类），而且可以保存 key-value 数据

3. Collection

Collection 是 Set、List、Queue 的父接口，主要提供了如下方法供子类实现，从而实现数据操作。

 

其中 iterator() 方法的返回值 Iterator 接口类叫做 迭代器，主要用于遍历集合元素，定义了如下两个方法：

方法

说明

boolean hasNext()

若仍有元素可以迭代，则返回 true

E next()

返回迭代的下一元素

void remove()

删除指定元素

 
public class Main(){
    public static void main(String[] args){
        Collection<Integer> list = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            list.add(i);
        }

        // 获取迭代器
        Iterator<Integer> iterator = list.iterator();
        // 遍历集合
        while(iterator.hasNext()){
            Integer value = iterator.next();
            System.out.print("t" + value);
        }
    }
}

4. Collection 之 Set

Set 集合继承于 Collection，用于 Collection 有的所有方法，未提供额外方法。Set 不允许包含重复元素，如果试图将两个相同元素加入同一 Set 中，将导致失败。

4.1 HashSet 类

  1. HashSet 的特点
  • 无法保证元素的排列顺序；
  • HashSet 不是同步的，若多个线程同时访问一个 HashSet，则必须通过代码来保证其同步；
  • 集合元素值可以是 null；
  1. LinkedHashSet

LinkedHashSet 是 HashSet 的子类，同样是根据元素的 hashCode 来决定元素的存储位置，同时用链表维护元素顺序，从而保证元素以插入的顺序来保存。

  1. HashSet 中判断集合元素相等

不同的对象进行比较，可以有如下四种情况：

  • 若两元素通过 equal() 方法比较返回 false，但两者的 hashCode() 返回不相等，则将其存储在不同位置；
  • 若两元素通过 equal() 方法比较返回 true，但两者的 hashCode() 返回不相等，则将其存储在不同位置；
  • 若两元素通过 equal() 方法比较返回 false，但两者的 hashCode() 返回相等，则将其存储在相同位置，在这个位置以链表式结构来保存多个对象。因为向 HashSet 集合中存入一个元素时，HashSet 将调用对象的 hashCode() 获取其 hash 值，然后根据 hash 值来决定对象在 HashSet 中的存储位置；
  • 若两元素通过 equal() 方法比较返回 true，且两者的 hashCode() 返回相等，则不添加到 HashSet；

4.2 TreeSet 类

一组有序的集合，若未指定排序规则 Comparator，则按照自然排序。

注意：TreeSet 中的元素都必须实现 Comparable 接口；

4.3 HashSet vs LinkedHashSet vs TreeSet

Set 类型

使用场景

底层数据结构

HashSet

无序无重合，快速查找，元素必须定义 hashCode()，线程不安全，能够存储 null 值

链表

LinkedHashSet

维护次序的 HashSet，元素必须定义 hashCode()，能按照添加的顺序遍历

链表

TreeSet

保持元素大小次序，元素必须实现 Comparable 接口，有自然排序和定制排序

红黑树

5. Collection 之 List

5.1 List 常用方法

List 是一个元素有序、可重复的集合，其中的每个元素均有对应的顺序索引，允许使用重复元素，通过索引来访问指定位置的集合元素，继承自 Collection，拥有其所有方法，此外还有其他一些根据索引来操作元素的方法，如下：

方法

说明

void add(int index, Object element)

在列表的指定位置插入指定元素

boolean addAll(int index, Collection<? extends E> c)

将集合 c 中的所有元素都插入到列表中的指定位置 index处

Object get(index)

返回列表中指定位置的元素

int indexOf(Object o)

返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1

int lastIndexOf(Object o)

返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1

Object remove(int index)

移除列表中指定位置的元素

Object set(int index, Object element)

用指定元素替换列表中指定位置的元素

List subList(int fromIndex, int toIndex)

返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的所有集合元素组成的子集

Object[] toArray()

返回按适当顺序包含列表中的所有元素的数组（从第一个元素到最后一个元素）

void replaceAll(UnaryOperator operator)

根据 operator指定的计算规则重新设置 List集合的所有元素

void sort(Comparator c)

根据 Comparator参数对 List集合的元素排序

5.2 ArrayList

  1. ArrayList 特点
    • 实现了 List 接口的可变数组；
    • 可以插入 null；
    • 非 synchronized；
    • 其 size(),isEmpty(),get(),set(),iterator(),add() 等方法的时间复杂度均为

    O(1)

    ；

5.3 LinkedList

LinkedList 是一个链表维护的序列容器，和 ArrayList 最大的区别在于其底层实现，前者使用链表，后者使用数组，所以选用时可以根据数组和链表的特性来进行选择，主要不同有如下几点：

  • 数组查找效率高，能够通过索引直接查找出对应元素，但链表却需要每次都从头开始；
  • 链表插入和删除元素比较高效，只需要在插入或删除位置断链后重组链即可，但数组需要重新复制一份将所有数据后移或前移；
  • 动态申请内存时，链表只需要动态创建，但数组达到初始申请长度后，需要重新申请一个更大的数组，并将原来数组的数据迁移过去；

5.4 ArrayList vs LinkedList

类型

优点

缺点

底层数据结构

ArrayList是·

随机访问元素较快

中间元素的插入和删除较慢

数组

LinkedList

中间元素的插入和删除，顺序访问的优化

随机访问较慢

双向链表

6. Collection 之 Queue

6.1 Queue 常用方法

Queue 用于模拟队列这种数据结构，是一种 先进先出（FIFO，first-in-first-out） 的容器。队列头部是队列中存放时间最长的元素，尾部元素是队列中存放时间最短的元素。新的元素插入（offer()）到队列尾部，访问元素（poll）操作将返回队列头部元素，通常接口中提供了如下方法 ：

方法

说明

boolean add(E e)

将指定元素插入队尾，成功返回 true，空间不足时抛出 IllegalStateException

E element()

获取队首元素但不移除

boolean offer(E e)

将指定元素插入队尾，适用于有容量限制的队列（优于 add(E e)）

E peek()

获取队首元素但不移除，队列为空返回 null

E poll()

获取并移除队首元素，队列为空返回 null

E remove()

获取并移除队首元素

7. Map

7.1 Map 常用方法

Map 用于保存具有映射关系的数据，所以通常保存着两组数，一组保存 key，一组保存 value 。两者都可以是任意引用类型的数据，但是 key 不允许重复。接口中通常提供了如下方法：

方法

说明

void clear()

从映射中移除所有映射关系

boolean containsKey(Object key)

若映射中包含指定 key 的映射关系，返回 true

boolean containsValue(Object value)

若映射将一个或多个 key 映射到指定值，返回 true

Set<Map.Entry<K,V>> entrySet()

返回映射中包含的映射关系的 Set 视图

boolean equals(Object o)

比较指定的对象与此映射是否相等

V get(Objcet key)

返回指定建所映射的值；若该映射不含该键的映射关系，则返回 null

int hashCode()

返回映射的 hash 值

boolean isEmpty()

若映射为包含 key-value 映射关系，则返回 true

Set<K> keySet()

返回映射中包含的键的 Set 视图

V put(K key, V value)

将指定的值与此映射中的指定键关联

void putAll(Map<? extends K, ? extends V> m)

从指定映射中将所有映射关系复制到此映射中

V remove(Object key)

若存在一个键的映射关系，则将其从映射中移除

int size()

返回映射中的 key-value 关系数

Collection<V> values()

返回映射中包含的值的 Collection 视图

7.2 HashMap

最基础常用的一种 Map，无序且以散列表的方式进行存储。HashSet 其实就是基于 HashMap，将其 key 作为单个元素进行存储。关于 HashMap 的更多知识，可以参看 HashMap 知多少[1]。

7.3 LinkedHashMap

和 HashMap 最大的区别在于 LinkedHashMap 遍历时是有序的，可以保存插入时的顺序，同时还可以设置根据最近访问的元素放在最前面（即 LRU）；

7.4 TreeMap

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序，具体取决于使用的构造方法。TreeMap 的基本操作 containsKey、get、put和 remove 的时间复杂度是

log(n)

。另外，TreeMap是非同步的。它的 iterator方法返回的迭代器是 fail-fastl 的。

7.5 WeakHashMap

除了自身有对 key 的引用之外，若 key 没有其他引用指向它，此时就会自动丢弃该值。

7.6 各 Map 类型对比

Map 类型

使用场景

底层实现

HashMap

快速查询

散列表

LinkedHashMap

迭代遍历具有顺序(插入顺序 or最近最少使用)

链表

TreeMap

具有排序，唯一可以返回子树的 Map(subMap())

红-黑树

WeakHashMap

弱键映射，映射之外无引用的键，可以被垃圾回收

散列表

ConcurrentHashMap

线程安全的 Map

链表

IdentityHashMap

用 == 代替 equals() 对键进行排序，专位解决特殊问题

链表

参考资料

[1]

HashMap 知多少: 3.HashMap.md

更多教程请访问码农之家

点击查看往期精彩内容

二叉树的 4 种遍历方式，你会多少？

面试中最长常问到的 HashMap，你都知道多少？

原创文章，作者：254126420，如若转载，请注明出处：https://blog.ytso.com/276605.html

赞 (0)
0
上一篇 2022年7月24日
下一篇 2022年7月24日

相关推荐

发表回复

登录后才能评论