JAVA集合总结,将知识点一网打尽!

一、Java集合框架体系总览

总的来说,Java集合框架以Collection接口为中心,下属是三个子接口,分别是:List(线性表)、Set、Queue(队列),以及还有一个非常重要的Map接口。下面我们分别总结一下每种类型集合下的知识点。

Collection接口

首先我们来看一下Collection接口中的方法:

1. 添加元素的功能:
/**添加元素*/
boolean add(E e);
/**将整个集合添加到某个集合*/
boolean addAll(Collection<? extends E> c);

2.从集合中删除(指定)元素
/**清空集合中的所有元素*/
void clear();
//从集合中移除指定元素
boolean remove(Object o);
//从此集合中移除指定集合中包含的元素
boolean removeAll(Collection<?> c);
//移除在c集合中不包含的元素
boolean retainAll(Collection<?> c);

3.判断功能
/**集合中是否有元素o,如果有返回true,否则返回false*/
boolean contains(Object o);
/**如果在此集合中有给定集合中的全部元素那么将返回true*/
boolean containsAll(Collection<?> c);
//判断集合是否为空,如果为空返回true,否者返回false
boolean isEmpty();

4.获取集合的各种信息
//获得遍历集合元素的迭代器,这个方法是Collection继承Iterable接口得到的
Iterator<E> iterator();
//返回集合中元素的个数
int size();
/**判断两个对象是否相等*/
boolean equals(Object o);
//返回集合对象的hashCode
int hashCode();

5. 转换
//将此集合转化为数组
Object[] toArray();
/**=============jdk1.8新增的几个方法=============*/
//在jdk1.8中新增了一下几个方法,都是default方法,在Collection接口中直接给出了实现

//parallelStream()返回并行的Stream
default Stream<E> parallelStream() {
   return StreamSupport.stream(spliterator(), true);
}

//仅仅是返回集合的Stream
default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false); 
}    

//删除容器中所有满足filter指定条件的元素
default boolean removeIf(Predicate<? super E> filter) { 
    Objects.requireNonNull(filter);                     
    boolean removed = false;                            
    final Iterator<E> each = iterator();                
    while (each.hasNext()) {                            
        if (filter.test(each.next())) {                 
            each.remove();                              
            removed = true;                             
        }                                               
    }                                                   
    return removed;                                     
}    

//可分割的迭代器,不同以往的iterator需要顺序迭代,Spliterator可以分割为若干个小的迭代器进行并行操
//作,既可以实现多线程操作提高效率,又可以避免普通迭代器的fail-fast机制所带来的异常
default Spliterator<E> spliterator() {       
    return Spliterators.spliterator(this, 0);
}                                                 
Iterable接口

Collection接口继承了Iterable接口,说明所有的集合元素都是可以通过Iterator迭代器来遍历,事实也确实是这样,下面是Iterable接口中的三个方法:

//获取遍历集合的迭代器,Collection中的iterator方法就是从这里继承得到的
Iterator<T> iterator();

//JDK1.8新增的一个遍历集合的方法,采用函数式接口的方式,可以很方便的遍历所有集合类型
default void forEach(Consumer<? super T> action) {
    //方法内部已经判空了,所有在使用这个方法的时候没有必要的时候不用判空
    Objects.requireNonNull(action);               
    //底层实际还是增强for
    for (T t : this) {                            
        action.accept(t);                         
    }                                             
} 

//作用和Collection中的同名方法一样
default Spliterator<T> spliterator() {                        
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
}                                                             
Iterator—迭代器

使用迭代器可以任何类型的集合,Iterator也是一个接口,它有三个迭代器必备的基本方法外加jdk1.8新增了一个方便的遍历集合的方法forEachRemaining

//判断集合是否还有下一个元素
boolean hasNext();
//获取集合的下一个元素
E next();
//移除元素
default void remove() {
   throw new UnsupportedOperationException("remove");
}

//JDK1.8新增的一个方法,用法和作用都和Iterable接口中的forEach()方法类似
default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action); 
    //这里使用的是Iterator接口中的hasNext方法配合while循环实现遍历的
    while (hasNext())                                      
        action.accept(next());                             
}                                                          

二、List接口

Java 的 List 是非常常用的数据类型。List 是有序的 Collection。Java List 一共三个实现类:
分别是 ArrayList、Vector 和 LinkedList。

1、ArrayList

ArrayList 是最常用的 List 实现类,内部是通过Object数组实现的,它可以实现对元素进行快速随机访问。ArrayList中的Object数组的的默认初始化大小是10,并且默认构造方法中对于数组的创建是在第一次添加元素时执行的,我们可以看看源码的实现:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    //ArrayList默认容量
    private static final int DEFAULT_CAPACITY = 10;
    //用Object[0]来代替null 很多时候我们需要传递参数的类型,而不是传null,所以用Object[0]
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //一个空对象,如果使用默认构造函数创建,则默认对象内容默认是该值  
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //存储元素的数组
    transient Object[] elementData; // non-private to simplify nested class access
    //数组中元素个数
    private int size;
    //数组最大容量
    private static final int MAX_ARRAY_SIZE = 2147483639;
    
    //默认构造方法,在构造方法中并没有立即初始化一个大小为10的Object数组,而是采用了懒加载,延迟到第一次添加元素的时候才初始化
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    //指定容量的ArrayList则是在构造方法中立即初始化了一个指定容量大小的Object数组
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
}
添加元素的方法add

ArrayList会在添加新元素之前先检查一下数组的大小是否够用,如果不够用就会扩容,默认的扩容大小是原数组的1.5倍,如果扩容1.5的大小还是没法满足添加元素所需的容量,就会使用传入的容量大小,这样就会导致下一次添加元素的时候又触发扩容,因此在使用任何集合元素的时候请尽量给定一个初始容量,避免频繁的扩容影响性能。

但是当从 ArrayList 的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除

public boolean add(E e) {
        //ArrayList的扩容机制在这一步实现
        ensureCapacityInternal(size + 1);  //确认内部容量
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        // 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //可以看到,如果是使用了默认构造方法时,只有在第一次添加元素的时候才会构造一个大小为10的数组  
            //
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //确定实际容量
        ensureExplicitCapacity(minCapacity);
   }


private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果超出了容量,进行扩展
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//ArrayList的扩容实现
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新数组的大小是旧数组大小的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果1.5倍的新数组大小还是没法满足,那就使用minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //当数组容量超过自大容量限制后MAX_ARRAY_SIZE,将数组的容量设置为Integer.MAX_VALUE
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
  }

2、Vector ( 数组实现、 线程同步)

Vector 与 ArrayList 一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一
个线程能够写 Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,
访问它比访问 ArrayList 慢

3、LinkedList(双链表、双端队列)

LinkedList即实现了List接口,同时它也实现了Deque接口。它**使用链表结构存储数据,很适合数据的动态插入和删除。**具体的我们看看源码就清楚了:

//Node结点,是一个双链表
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;                        
    }  
}

//链表的头结点
transient Node<E> first;        
//链表的尾结点                                                        
transient Node<E> last;
//链表的结点个数
transient int size = 0;

//默认的构造方法,啥都没干...
public LinkedList() {
}                    
添加元素的方法

LinkedList同时具有链表和双向队列的功能,因此添加元素的方法也有两个add方法和offer方法,前者用于向链表中尾插数据,后者用于向队列尾部添加数据。其实在源码中offer方法是把add方法有包装了一下而已。我们直接来看add方法的实现即可、

//添加新元素
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++;                                    
}                                                  

三、Set接口

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素,值不能重
复。对象的相等性本质是对象 hashCode 值(java 是依据对象的内存地址计算出的此序号)判断
的,如果想要让两个不同的对象视为相等的,就必须覆盖 Object 的 hashCode 方法和 equals 方
法。

1、HashSet

哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序(和 List 显然不
同) 而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的
hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值,如果哈希值一样,接着会比较
equals 方法 如果 equls 结果为 true ,HashSet 就视为同一个元素。如果 equals 为 false 就不是
同一个元素。

2、TreeSet

(1)TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序(升序、降序),每增
加一个对象都会进行排序,将对象插入的二叉树指定的位置。

(2)Integer 和 String 对象都可以进行默认的 TreeSet 排序,而自定义类的对象是不可以的,自
己定义的类必须实现 Comparable 接口,并且覆写相应的 compareTo()函数,才可以正常使
用。

(3)在覆写 compare()函数时,要返回相应的值才能使 TreeSet 按照一定的规则来排序

(4)比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整
数、零或正整数。

3、LinkedHashSet

对于 LinkedHashSet 而言,它继承与 HashSet、又基于 LinkedHashMap 来实现的。
LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素,它继承与 HashSet,其所有的方法
操作上又与 HashSet 相同,因此 LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并
通过传递一个标识参数,调用父类的构造器,底层构造一个 LinkedHashMap 来实现,在相关操
作上与父类 HashSet 的操作相同,直接调用父类 HashSet 的方法即可。

四、Map接口

1、Hashtable

Hashtable 是遗留类,很多映射的常用功能与 HashMap 类似,不同的是它承自 Dictionary 类,
并且是线程安全的,任一时间只有一个线程能写 Hashtable,并发性不如 ConcurrentHashMap,
因为 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用,不需要线程安全
的场合可以用 HashMap 替换,需要线程安全的场合可以用 ConcurrentHashMap 替换。

2、HashMap

HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快
的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null,允许多条记
录的值为 null。HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导
致数据的不一致。如果需要满足线程安全,可以用 Collections 的 synchronizedMap 方法使
HashMap 具有线程安全的能力,或者使用 ConcurrentHashMap。我们用下面这张图来介绍
HashMap 的结构。

在JDK7中HashMap使用数组+链表实现

大方向上,HashMap 里面是一个数组,然后数组中每个元素是一个单向链表。上图中,每个绿色
的实体是嵌套类 Entry 的实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的 next。
1. capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍。
2. loadFactor:负载因子,默认为 0.75。
3. threshold:扩容的阈值,等于 capacity * loadFactor

Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑
组成。
根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的
具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决
于链表的长度,为 O(n)
。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,
会将链表转换为红黑树
,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

具体的原理可以参考我的博客HashMap是如何工作的

3、LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类,保存了记录的插入顺序,在用 Iterator 遍历
LinkedHashMap 时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

4、TreeMap

TreeMap 实现 SortedMap 接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,
也可以指定排序的比较器,当用 Iterator 遍历 TreeMap 时,得到的记录是排过序的。
如果使用排序的映射,建议使用 TreeMap。
在使用 TreeMap 时,key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的
Comparator,否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

参考通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

留言区

还能输入500个字符