Java集合总结

发表于 | 分类于
字数统计: 2.1k | 阅读时长 ≈ 8

集合的作用

简单来说，集合就是存储对象的容器，方便我们操作多个Java对象。

集合分类

集合接口以及常用实现类

使用场景：

  • 如果是集合类型，可选择List或Set。List是插入有序，可重复的，值可以为null；Set 是不可重复的，值不能为null。
  • 如果是key-value类型，则选择Map。保持插入顺序选择LinkedHashMap;排序选择TreeMap。

Collection

1、Collection介绍

集合与数组的区别：

  • 数组长度固定，集合长度可变
  • 数组可以存储基本数据类型和引用数据类型；集合只能存储引用数据类型，存储基本数据类型时会自动装箱，转换为对应的包装类。

基本方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1、添加功能：
    boolean add(Object obj)：添加一个元素
    boolean addAll(Collection c)：添加一个集合的所有元素
2、删除功能：
    void clear()：移除所有元素
    boolean remove(Object obj)：移除一个元素
    boolean removeAll(Collecion c)：移除当前集合的所有元素，只要一个元素被移除就返回true
3、判断功能：
    boolean contains(Object obj)：判断当前集合是否包含当前元素
    boolean containsAll(Collection c)：判断当前集合包含指定集合
    boolean isEmpty()：判断集合是否为空
4、获取功能：
    Iterator<E> iterator()：获取迭代器
5、长度功能：
    int size()：获取元素个数
6、交集功能：
    boolean retainAll(Collection c)：移除当前集合中集合c没有的元素，最终结果保存至当前集合中

2、迭代器（Iterator）

java.utils.Collection继承了java.lang.Iterable接口，Collection继承了Iterable的Iterator()方法，返回Iterator对象。

java.utils.Iterator也是一个接口，只有三个方法

  • hasNext()
  • next()
  • remove()

这三个方法通过Collection的实现类以内部类的方式实现，因为Collection的实现类存储结构不同，遍历方式也必然不同，必须通过各个实现类以内部类的方式实现，来完成对不同实现类的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@Test
public void test3() {
    // 1、创建集合对象
    Collection coll1 = new ArrayList();
    // 2、添加数据到集合中
    coll1.add(1);
    coll1.add(2);
    coll1.add(3);
    // 3、使用集合对象获取迭代器对象
    Iterator iterator = coll1.iterator();
    // 起始指针位于第一个元素之前
    // hasNext() 判断是否还有下一个元素
    // next() 指针下移，将下移以后的集合位置上的元素返回
    // 4、遍历集合
    while(iterator.hasNext()){// 5、判断是否存在元素
        Object obj = iterator.next();// 6、下移到下一个元素的位置
        if(obj.equals(new Integer(1))){
            iterator.remove();// 移除当前元素
        }
    }
    iterator = coll1.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

3、List集合

LIst集合特点：有序（存取顺序与取出顺序一致），可重复。

List集合常用实现类

  • ArrayList：底层数据结构是数组，线程不安全
  • LinkedList：底层结构是链表，线程不安全
  • Vector：底层数据结构是数组，线程安全

ArrayList

底层其实就是一个数组，但是可以进行扩容，实现动态增长。支持快速随机访问。插入和删除元素时，时间复杂度受元素位置影响。
直接添加元素或删除尾部元素时，时间复杂度为O(1)；指定位置添加或删除时间复杂度为O(n-i)，因为其他元素需要整体的后移或前移。

构造方法：
指定了容量则按照该容量初始化，未指定则返回一个空数组

add(E e)方法：
步骤：检查是否需要扩容—>插入元素

add(int index,E e)
步骤：检查角标—>检查是否需要扩容—>插入元素

get(int index)：检查角标—>返回元素

set(int index,E e)：检查角标—>替代元素—>返回旧值

remove(int index)：检查角标—>删除元素—>计算出需要移动的个数，并移动—>设置为null，让gc回收

在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList

LinkedList底层是双向链表 。删除时时间复杂度为O(1)，指定位置添加或删除时时间复杂度为O(n)，因为需要先移动到指定位置然后再删除或添加。

Vector

Vector底层也是数组，与ArrayList最大的区别就是：同步(线程安全)

所有方法都是同步的，有性能损失。

4、Set集合

Set集合特点：元素不可重复

Set集合常用实现类

  • HashSet：底层数据结构是哈希表。
  • TreeSet：底层数据结构是红黑数（平衡二叉树）；保证元素有序。
  • LinkedHashSet：底层数据结构由哈希表和链表组成。

HashSet

  • 实现Set接口
  • 不保证迭代顺序
  • 允许元素为null
  • 底层实际上是一个HashMap实例
  • 非同步
  • 初始容量非常影响迭代性能

TreeSet

  • 可以实现排序功能
  • 底层实际上是一个TreeMap实例
  • 非同步

LinkedHashSet

  • 迭代是有序的
  • 允许为null
  • 底层实际上是一个HashMap+双向链表实例(其实就是LinkedHashMap)
  • 非同步
  • 性能比HashSet差一丢丢，因为要维护一个双向链表
  • 初始容量与迭代无关，LinkedHashSet迭代的是双向链表

Map

1、Map介绍

特点：将键映射到值的对象，一个映射不能有重复的键，每个键最多映射一个值。

Map与Collection的区别

  • Map集合存储的元素是成对出现的，键唯一，值可以重复
  • Collection集合存储的元素是单独出现的，子类List存储的值可重复，Set不可重复

基本方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1、添加功能：
    put(K key,V value)  添加元素，key存在则替换
2、删除功能：
    void clear()  移除所有键值对
    remove(Object key)  根据键删除值，并把值返回
3、判断功能：
    boolean containsKey(Object key)  判断集合是否包含指定的键
    boolean containsValue(Object value)  判断集合是否包含指定的值
    boolean isEmpty()  判断集合是否为空
4、获取功能：
    Set<Map.Entry<K key,V value>> entrySet()  返回键值对对象的集合
    get(Object key)  根据键获取值
    Set<K> keySet()  获取集合中所有的键的集合
    Collection<V> values()  获取集合中所有值的集合
5、长度功能：
    int size()  返回集合中键值对的对数
6、遍历功能：
    void forEach(Object key, Object value)

HashMap

  • 无序，允许为null，非同步
  • 底层有散列表（数组+链表）实现

put(K key,V value)方法：map.put(key1,value1)

首先调用key1所在类的hashCode()计算key的哈希值，此哈希值与数组长度-1做&位运算，得到在Entry数组中的存放位置；
如果此位置为空，则直接添加，否则将key1的哈希值与此位置上元素的哈希值比较；
如果哈希值不同，则直接添加，否则调用key1所在类的equals()方法，如果返回true，直接覆盖，否则添加到链表尾部。

当元素个数达到容量的0.75倍时，就会扩容，容量扩大为原来的2倍，原有的数据全部被复制过来。

jdk1.7是以链表的形式添加元素，jdk1.8之后，链表长度大于8，数组长度大于64的时候，链表会转换为红黑树。

get(Object key)：计算key的哈希值，通过getNode(int hash,Object key)获取对应的value

remove(Object key)：计算key的哈希值，通过removeNode(int hash,Object key,Object value) 删除该键值对，并返回值

HashMap与HashTable的区别：

从存储结构和实现来讲基本上都是相同的。HashTable是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

在JDK8中HashMap的底层是：数组+链表+红黑树

ConcurrentHashMap

jdk1.7 采用分段锁的方式解决线程安全 segment数组+ReentrantLock

jdk1.8 采用synchronized+CAS实现线程安全

LinkedHashMap

  • 底层是数组和双向链表
  • 允许为null，不同步
  • 保存了插入的顺序

TreeMap

  • 实现了NavigableMap接口，而NavigableMap接口继承着SortedMap接口，可实现定制排序，默认key值升序
  • 底层是红黑树
  • key不能为null，为null为抛出NullPointerException
  • 不同步
  • 使用Comparator或者Comparable来比较key是否相等与排序的问题