Java集合：总体结构

时间 2019-12-09 标签 java 集合总体结构

1、Java中集合java

　　Java中集合类是Java编程中使用最频繁、最方便的类。集合类做为容器类能够存储任何类型的数据，固然也能够结合泛型存储指定的类型（不过泛型仅仅在编译期有效，运行时是会被擦除的）。集合类中存储的仅仅是对象的引用，并不存储对象自己。集合类的容量能够在运行期间进行动态扩展，而且还提供不少很方便的方法，如求集合的并集、交集等。编程

2、集合类结构数组

　　Java中的集合包含多种数据结构，如链表、队列、哈希表等。从类的继承结构来讲，能够分为两大类，一类是继承自Collection接口，这类集合包含List、Set和Queue等集合类。另外一类是继承自Map接口，这主要包含了哈希表相关的集合类。下面咱们看一下这两大类的继承结构图：安全

一、List、Set和Queue数据结构

图中的绿色的虚线表明实现，绿色实线表明接口之间的继承，蓝色实线表明类之间的继承。多线程

　　 (1)List：咱们用的比较多List包括ArrayList和LinkedList，这二者的区别也很明显，从其名称上就能够看出。ArrayList的底层的经过数组实现，因此其随机访问的速度比较快，可是对于须要频繁的增删的状况，效率就比较低了。而对于LinkedList，底层经过链表来实现，因此增删操做比较容易完成，可是对于随机访问的效率比较低。框架

咱们先看下二者的插入效率：dom

 1 package com.paddx.test.collection;
 2 
 3 import java.util.ArrayList;
 4 import java.util.LinkedList;
 5 
 6 public class ListTest {
 7     public static void main(String[] args) {
 8         for(int i=0;i<10000;i++){
 9 
10         }
11         long start = System.currentTimeMillis();
12 
13         LinkedList<Integer> linkedList = new LinkedList<Integer>();
14         for(int i=0;i<100000;i++){
15             linkedList.add(0,i);
16         }
17 
18         long end = System.currentTimeMillis();
19         System.out.println(end - start);
20 
21         ArrayList<Integer> arrayList = new ArrayList<Integer>();
22         for(int i=0;i<100000;i++){
23             arrayList.add(0,i);
24         }
25 
26         System.out.println(System.currentTimeMillis() - end);
27     }
28 }

下面是本地执行的结果：ide

23
1227

　　能够看出，在这种状况下，LinkedList的插入效率远远高于ArrayList，固然这是一种比较极端的状况。咱们再来比较一下二者随机访问的效率：工具

 1 package com.paddx.test.collection;
 2 
 3 import java.util.ArrayList;
 4 import java.util.LinkedList;
 5 import java.util.Random;
 6 
 7 public class ListTest {
 8     public static void main(String[] args) {
 9 
10         Random random = new Random();
11 
12         for(int i=0;i<10000;i++){
13 
14         }
15         LinkedList<Integer> linkedList = new LinkedList<Integer>();
16         for(int i=0;i<100000;i++){
17             linkedList.add(i);
18         }
19 
20         ArrayList<Integer> arrayList = new ArrayList<Integer>();
21         for(int i=0;i<100000;i++){
22             arrayList.add(i);
23         }
24 
25         long start = System.currentTimeMillis();
26 
27 
28         for(int i=0;i<100000;i++){
29             int j = random.nextInt(i+1);
30             int k = linkedList.get(j);
31         }
32 
33         long end = System.currentTimeMillis();
34         System.out.println(end - start);
35 
36         for(int i=0;i<100000;i++){
37             int j = random.nextInt(i+1);
38             int k = arrayList.get(j);
39         }
40 
41         System.out.println(System.currentTimeMillis() - end);
42     }
43 }

下面是我本机执行的结果：

5277
6

　　很明显能够看出，ArrayList的随机访问效率比LinkedList高出好几个数量级。经过这两段代码，咱们应该可以比较清楚的知道LinkedList和ArrayList的区别和适应的场景。至于Vector，它是ArrayList的线程安全版本，而Stack则对应栈数据结构，这二者用的比较少，这里就不举例了。

　　(2)Queue：通常能够直接使用LinkedList完成，从上述类图也能够看出，LinkedList继承自Deque，因此LinkedList具备双端队列的功能。PriorityQueue的特色是为每一个元素提供一个优先级，优先级高的元素会优先出队列。

　　(3)Set：Set与List的主要区别是Set是不容许元素重复的，而List则能够容许元素重复的。判断元素的重复须要根据对象的hash方法和equals方法来决定。这也是咱们一般要为集合中的元素类重写hashCode方法和equals方法的缘由。咱们仍是经过一个例子来看一下Set和List的区别，以及hashcode方法和equals方法的做用：

package com.paddx.test.collection;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class SetTest {

    public static void main(String[] args) {
        Person p1 = new Person("lxp",10);
        Person p2 = new Person("lxp",10);
        Person p3 = new Person("lxp",20);

        ArrayList<Person> list = new ArrayList<Person>();
        list.add(p1);
        System.out.println("---------");
        list.add(p2);
        System.out.println("---------");
        list.add(p3);
        System.out.println("List size=" + list.size());

        System.out.println("----分割线-----");

        Set<Person> set = new HashSet<Person>();
        set.add(p1);
        System.out.println("---------");
        set.add(p2);
        System.out.println("---------");
        set.add(p3);
        System.out.println("Set size="+set.size());
    }


    static class Person{
        private String name;
        private int age;

        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        @Override
        public boolean equals(Object o) {
            System.out.println("Call equals();name="+name);
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Person person = (Person) o;

            return name.equals(person.name);

        }

        @Override
        public int hashCode() {
            System.out.println("Call hashCode(),age="+age);
            return age;
        }
    }
}

　　上述代码的执行结果以下：

---------
---------
List size=3
----分割线-----
Call hashCode(),age=10
---------
Call hashCode(),age=10
Call equals();name=lxp
---------
Call hashCode(),age=20
Set size=2

　　从结果看出，元素加入List的时候，不执行额外的操做，而且能够重复。而加入Set以前须要先执行hashCode方法，若是返回的值在集合中已存在，则要继续执行equals方法，若是equals方法返回的结果也为真，则证实该元素已经存在，会将新的元素覆盖老的元素，若是返回hashCode值不一样，则直接加入集合。这里记住一点，对于集合中元素，hashCode值不一样的元素必定不相等，可是不相等的元素，hashCode值可能相同。

　　HashSet和LinkedHashSet的区别在于后者能够保证元素插入集合的元素顺序与输出顺序保持一致。而TresSet的区别在于其排序是按照Comparator来进行排序的，默认状况下按照字符的天然顺序进行升序排列。

　　(4)Iterable：从这个图里面能够看到Collection类继承自Iterable，该接口的做用是提供元素遍历的功能，也就是说全部的集合类（除Map相关的类）都提供元素遍历的功能。Iterable里面包含了Iterator的迭代器，其源码以下，你们若是熟悉迭代器模式的话，应该很容易理解。

1 public interface Iterator<E> {
2 
3     boolean hasNext();
4 
5     E next();
6 
7     void remove();
8 }

二、Map：

Map类型的集合最大的优势在于其查找效率比较高，理想状况下能够实现O(1)的时间复杂度。Map中最经常使用的是HashMap，LinkedHashMap与HashMap的区别在于前者可以保证插入集合的元素顺序与输出顺序一致。这二者与TreeMap的区别在于TreeMap是根据键值进行排序的，固然其底层的实现也有本质的区别，如HashMap底层是一个哈希表，而TreeMap的底层数据结构是一棵树。咱们如今看下TreeMap与LinkedHashMap的区别：

package com.paddx.test.collection;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class MapTest {
    public static void main(String[] args) {
        Map<String,String> treeMap = new TreeMap<String,String>();
        Map<String,String> linkedMap = new LinkedHashMap<String, String>();

        treeMap.put("b",null);
        treeMap.put("c",null);
        treeMap.put("a",null);

        for (Iterator<String> iter = treeMap.keySet().iterator();iter.hasNext();){
            System.out.println("TreeMap="+iter.next());
        }

        System.out.println("----------分割线---------");

        linkedMap.put("b",null);
        linkedMap.put("c",null);
        linkedMap.put("a",null);

        for (Iterator<String> iter = linkedMap.keySet().iterator();iter.hasNext();){
            System.out.println("LinkedHashMap="+iter.next());
        }
    }
}

运行上述代码，执行结果以下：

TreeMap=a
TreeMap=b
TreeMap=c
----------分割线---------
LinkedHashMap=b
LinkedHashMap=c
LinkedHashMap=a

　　从运行结果能够很明显的看出这TreeMap和LinkedHashMap的区别，前者是按字符串排序进行输出的，然后者是根据插入顺序进行输出的。细心的读者能够发现，HashMap与TreeMap的区别，与以前提到的HashSet与TreeSet的区别是一致的，在后续进行源码分析的时候，咱们能够看到HashSet和TreeSet本质上分别是经过HashMap和TreeMap来实现的，因此它们的区别天然也是相同的。HashTable如今已经不多使用了，与HashMap的主要区别是HashTable是线程安全的，不过因为其效率比较低，因此一般使用HashMap，在多线程环境下，一般用CurrentHashMap来代替。

3、总结

　　本文只是从总体上介绍了Java集合框架及其继承关系。除了上述类，集合还提供Collections和Arrays两个工具类，此外，集合中排序跟Comparable和Comparator紧密相关。在以后的文章中将对上述提的类在JDK中实现源码进行详细分析。