Java集合框架

作者: 竖起大拇指 | 来源:发表于2020-05-29 15:27 被阅读0次

集合可以看作是一种容器，用来存储对象信息。所有集合类都位于java.util包下，支持多线程的集合类位于java.util.concurrent包下。
Java集合类主要由两个根接口Collection和Map派生出来的,Collection派生出了三个子接口:List，Set,Queue,因此java集合大致也可分为List,Set,Queue,Map四种接口体系.Map不是Collection的子接口.

image.png

大致说明:

看上面的框架图，先抓住它的主干,即Collection和Map

Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。
List是一个有序的队列，每一个元素都有它的索引。第一个元素的索引值是0。List的实现类由LinkedList，ArrayList，Vector，Stack。
Set是一个不允许有重复元素的集合。Set的实现类有HashSet和TreeSet。HashSet依赖HashMap，它实际上是通过HashMap实现的。TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。
Map是一个映射接口，即Key-value键值对。Map中的每一个元素包含一个Key和Key对应的value。AbstractMap是个抽象类，它实现了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是继承于AbstractMap。Hashtable虽然继承于Dictionary,但是它实现了Map接口。
Iterator，它是遍历集合的工具，即我们通常通过Iterator迭代器来遍历集合。我们说Collection依赖于Iterator，是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象。ListIterator是专门为遍历List而存在的.
Arrays和Collecitons，它们是操作数组和集合的两个工具类。

Collection接口

Collection接口是处理对象集合的根接口，其中定义了很多对元素进行操作的方法，方法定义如下:

image.png

List接口

1.ArrayList

ArrayList时一个动态数组，也是我们常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量(10),该容量代表了数组的大小。随着容器中元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间，效率。

ArrayList擅长于随机访问。同时ArrayList是非同步的。

2.LinkedList

ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get,remove,First/Last 方法在LinkedList的首部或尾部。
由于实现的方式不同，linkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
与ArrayList一样，linkedList也是非同步的

Set接口

Set是一种不包含重复元素的Collection。它维持了它自己的内部排序，所以随机访问没有任何意义，与List一样，它同样允许null的存在但是仅有一个。Set接口有三个实现类，分别是散列集HashSet，链式撒列集LinkedHashSet和树形集TreeSet

1.HashSet

HashSet是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用null元素。Hashset是非同步的。HashSet的实现方式大致如下：通过一个HashMap存储元素，元素是存放在HashMap的key中，而value统一值用一个Object对象。

2. LinkedHashSet

LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来是以插入顺序保存的，也就是说，当遍历该集合时候，linkedHashSet将会以元素的添加顺序访问集合的元素。

3.TreeSet

TreeSet是一个有序集合，其顶层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式:自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

自然排序

TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素的大小关系，然后将元素按照升序排列，这就是自然排序。如果试图将一个对象添加到TreeSet集合中，则该对象必须实现Comparable接口，否则会抛出异常。当一个对象调用方法与另一个对象比较时，例如,obj1.compareTo(obj2),如果该方法返回0，则两个对象相等；如果返回一个正数，则obj1大于obj2；如果返回有个负数，则obj1小于obj2。
Java常用类中已经实现了Comparable接口的类由以下几个:
BigDecimal,以及所有数值类型对应的包装类
Character:按照字符的unicode值进行比较
Boolean:true对应包装类实例大于false对应的包装类实例
String:按照字符串中的字符unicode值进行比较
Date,Time:后面的时间，日期比前面的时间，日期大
对于TreeSet集合而言，它判断两个对象时否相等的标准是：两个对象通过compareTo(Object obj)方法比较是否返回0，如果返回0则相等。

定制排序

想要实现定制排序，需要创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由Comparator对象负责集合元素的排序逻辑。

Map接口

1.HashMap

以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组(Entry[] table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构.

2.LinkedHashMap

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时相同，那么就选用LinkedHashMap。
LinkedHashMap实现与HashMap的不同之处在于，后者维护者一个运行于所有条目的双重链接列表。根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。
由于LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能。因为它以链表来维护内部顺序。

3.TreeMap

TreeMap时一个有序的key-value集合，非同步，基于红黑树实现。每一个key-value节点作为红黑树的一个节点

Iterator与ListIterator详解

Iterator

定义如下:

public interface Iterator<E> {
boolean hasNext();  //判断集合里是否存在下一个元素。如果有，hasNext()方法返回true
 E next(); //返回集合里下一个元素
 void remove()；删除集合里上一次next方法返回的元素

default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

使用示例:

public class IteratorExample {
    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<String>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        Iterator<String> it = a.iterator();
        while (it.hasNext()) {
            String t = it.next();
            if ("bbb".equals(t)) {
                it.remove();
            }
        }
        System.out.println("After iterate : " + a);
    }
}

输出结果如下:

Before iterate : [aaa, bbb, ccc]
After iterate : [aaa, ccc]

注意:
1.Iterator只能单向移动.
2.Iterator.remove()是唯一安全的方式来在迭代过程中修改集合；如果在迭代中以任何其他的方式修改了基本集合将会产生未知的行为。而且每次调用一次Next方法，remove方法只能被调用一次。否则会抛出异常.

2.ListIterator

ListIterator是一个功能更加强大的迭代器，它是继承与Iterator接口，只能用于各种List类型的访问。可以通过调用ListIterator()方法产生一个指向List开始处的ListIterator,还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator.

public interface ListIterator<E> extends Iterator<E> {
  boolean hasNext();
  E next();
  boolean hasPrevious();
  E previous();
  int nextIndex();
  int previousIndex();
  void remove();
  void set(E e);
  void add(E e);
}

由以上定义我们可以推出ListIterator可以:
(1)双向移动（向前/向后遍历）.
(2)产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引.
(3)可以使用set()方法替换它访问过的最后一个元素.
(4)可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素。

使用示列:

            var list=ArrayList<String>()
            list.add("aaa")
            list.add("bbb")
            list.add("ccc")
            println("Before iterator :$list")
            var it=list.listIterator()
            println("before list iterator index:"+it.previousIndex())
            while(it.hasNext()){
                println(it.next()+","+it.previousIndex()+","+it.nextIndex())
            }

            println("-----------------------")
            while (it.hasPrevious()) {
                println(it.previous() + " ")
            }
            println("-----------------------")
            it = list.listIterator()
            while (it.hasNext()) {
                var t = it.next()
                if ("ccc" == t) {
                    it.set("nnn")
                } else {
                    it.add("kkk")
                }
            }
            println("After iterate : $list")

打印如下:

Before iterator :[aaa, bbb, ccc]
before list iterator index:-1
aaa,0,1
bbb,1,2
ccc,2,3
-----------------------
ccc 
bbb 
aaa 
-----------------------
After iterate : [aaa, kkk, bbb, kkk, nnn]