Java集合:整体结构

一、Java中集合

  Java中集合类是Java编程中使用最频繁、最方便的类。集合类作为容器类可以存储任何类型的数据,当然也可以结合泛型存储指定的类型(不过泛型仅仅在编译期有效,运行时是会被擦除的)。集合类中存储的仅仅是对象的引用,并不存储对象本身。集合类的容量可以在运行期间进行动态扩展,并且还提供很多很方便的方法,如求集合的并集、交集等。

二、集合类结构

  Java中的集合包含多种数据结构,如链表、队列、哈希表等。从类的继承结构来说,可以分为两大类,一类是继承自Collection接口,这类集合包含List、Set和Queue等集合类。另一类是继承自Map接口,这主要包含了哈希表相关的集合类。下面我们看一下这两大类的继承结构图:

1、List、Set和Queue

 图中的绿色的虚线代表实现,绿色实线代表接口之间的继承,蓝色实线代表类之间的继承。

   (1)List:我们用的比较多List包括ArrayList和LinkedList,这两者的区别也很明显,从其名称上就可以看出。ArrayList的底层的通过数组实现,所以其随机访问的速度比较快,但是对于需要频繁的增删的情况,效率就比较低了。而对于LinkedList,底层通过链表来实现,所以增删操作比较容易完成,但是对于随机访问的效率比较低。

我们先看下两者的插入效率:

 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 }

下面是本地执行的结果:

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 }

2、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来代替。

三、总结

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

2416
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

2757
来自专栏小勇DW3

ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

1173
来自专栏云霄雨霁

字符串查找----R向单词查找树

910
来自专栏desperate633

LintCode 子数组之和题目分析代码

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

552
来自专栏Java 源码分析

HashSet 源码分析

HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

3024
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

803
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

4066
来自专栏码云1024

List Set Map比较

3324
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

621

扫码关注云+社区