Java集合之整体结构

一、Java中集合

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

二、集合类结构

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

1、List、Set和Queue

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

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

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

package com.paddx.test.collection;
import java.util.ArrayList;
import java.util.LinkedList;
public class ListTest {
public static void main(String[] args) {
for(int i=;i<;i++){
}
long start = System.currentTimeMillis();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=;i<;i++){
linkedList.add(,i);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
ArrayList<Integer> arrayList = new ArrayList<Integer>();
for(int i=;i<;i++){
arrayList.add(,i);
}
System.out.println(System.currentTimeMillis() - end);
}
} 

下面是本地执行的结果:

23

1227

  可以看出,在这种情况下,LinkedList的插入效率远远高于ArrayList,当然这是一种比较极端的情况。我们再来比较一下两者随机访问的效率:

package com.paddx.test.collection;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;
public class ListTest {
public static void main(String[] args) {
Random random = new Random();
for(int i=;i<;i++){
}
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=;i<;i++){
linkedList.add(i);
}
ArrayList<Integer> arrayList = new ArrayList<Integer>();
for(int i=;i<;i++){
arrayList.add(i);
}
long start = System.currentTimeMillis();
for(int i=;i<;i++){
int j = random.nextInt(i+);
int k = linkedList.get(j);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
for(int i=;i<;i++){
int j = random.nextInt(i+);
int k = arrayList.get(j);
}
System.out.println(System.currentTimeMillis() - end);
}
} 

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

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的迭代器,其源码如下,大家如果熟悉迭代器模式的话,应该很容易理解。

public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}

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)

相关推荐

  • Java函数式编程(二):集合的使用

    第二章:集合的使用 我们经常会用到各种集合,数字的,字符串的还有对象的.它们无处不在,哪怕操作集合的代码要能稍微优化一点,都能让代码清晰很多.在这章中,我们探索下如何使用lambda表达式来操作集合.我们用它来遍历集合,把集合转化成新的集合,从集合中删除元素,把集合进行合并. 遍历列表 遍历列表是最基本的一个集合操作,这么多年来,它的操作也发生了一些变化.我们使用一个遍历名字的小例子,从最古老的版本介绍到现在最优雅的版本. 用下面的代码我们很容易创建一个不可变的名字的列表: 复制代码 代码如下:

  • Java中集合和数组的排序方式小结

    根据约定,在使用java编程的时候应尽可能的使用现有的类库,当然你也可以自己编写一个排序的方法,或者框架,但是有几个人能写得比JDK里的还要好呢?使用现有的类的另一个好处是代码易于阅读和维护,这篇文章主要讲的是如何使用现有的类库对数组和各种Collection容器进行排序,(文章中的一 部分例子来自<Java Developers Almanac 1.4>) 首先要知道两个类:java.util.Arrays和java.util.Collections(注意和Collection的区 别)Co

  • java集合框架的体系结构详细说明

    最近在一本J2EE的书中看到了很不错的对集合框架的说明文章,筛选后发上来和大家共享,集合框架提供管理对象集合的接口和类.它包含接口,类,算法,以下是它的各个组件的说明. Collection接口 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements).一些Collection允许相同的元素而另一些不行.一些能排序而另一些不行.Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自

  • java集合map取key使用示例 java遍历map

    复制代码 代码如下: for (Iterator i = keys.iterator(); i.hasNext()        {           String key = (String) i.next();           String value = (String) map.get(key);           text+=key + " = " + value;       } 复制代码 代码如下: <span style="border-coll

  • java实现列表、集合与数组之间转化的方法

    本文实例讲述了java实现列表.集合与数组之间转化的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package test;  import java.util.ArrayList;  import java.util.Arrays;  import java.util.HashSet;  import java.util.List;  import java.util.Set;  public class Test2 {      public static void

  • Java实现Map集合二级联动示例

    Map集合可以保存键值映射关系,这非常适合本实例所需要的数据结构,所有省份信息可以保存为Map集合的键,而每个键可以保存对应的城市信息,本实例就是利用Map集合实现了省市级联选择框,当选择省份信息时,将改变城市下拉选择框对应的内容. 思路分析: 1. 创建全国(省,直辖市,自治区)映射集合,即LinkedHashMap对象,使用Map接口的put()方法向集合中添加指定的省与城市的映射关系,其中值为String型一维数组. 代码如下: CityMap.java 复制代码 代码如下: import

  • Java集合Set、List、Map的遍历方法

    本文实例讲述了Java集合Set.List.Map的遍历方法,分享给大家供大家参考. 具体方法如下: package com.shellway.javase; import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.uti

  • Java函数式编程(四):在集合中查找元素

    查找元素 现在我们对这个设计优雅的转化集合的方法已经不陌生了,但它对查找元素却也是无能为力.不过filter方法却是为这个而生的. 我们现在要从一个名字列表中,取出那些以N开头的名字.当然可能一个也没有,结果可能是个空集合.我们先用老方法实现一把. 复制代码 代码如下: final List<String> startsWithN = new ArrayList<String>(); for(String name : friends) { if(name.startsWith(&

  • Java中的2种集合排序方法介绍

    直接上代码: import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * * <p> * ClassName CollectionsSort * </p> * <p> * Description 主要介绍两种集合的排序算法<br/> * 第一:java.util.Collections.s

  • Java集合之整体结构

    一.Java中集合 Java中集合类是Java编程中使用最频繁.最方便的类.集合类作为容器类可以存储任何类型的数据,当然也可以结合泛型存储指定的类型(不过泛型仅仅在编译期有效,运行时是会被擦除的).集合类中存储的仅仅是对象的引用,并不存储对象本身.集合类的容量可以在运行期间进行动态扩展,并且还提供很多很方便的方法,如求集合的并集.交集等. 二.集合类结构 Java中的集合包含多种数据结构,如链表.队列.哈希表等.从类的继承结构来说,可以分为两大类,一类是继承自Collection接口,这类集合包

  • Java集合框架超详细小结

    目录 一:Collection集合 1.1集合概述: 1.2集合架构 1.3Collection集合常用方法 二:迭代器Iterator 2.1Iterator接口 2.2Iterator的实现原理: 2.3增强for() 2.4迭代器注意事项 三:泛型 3.1泛型概述 3.2泛型的优缺点 3.3泛型的定义与使用 泛型方法 泛型接口 3.4泛型的通配符 通配符高级使用-----受限泛型 四:Java常见数据结构 4.1栈 4.2队列 4.3数组 4.4链表 4.5红黑树 五:List集合体系 5

  • 关于Java集合框架面试题(含答案)上

    1.Java集合框架是什么?说出一些集合框架的优点? 每种编程语言中都有集合,最初的Java版本包含几种集合类:Vector.Stack.HashTable和Array.随着集合的广泛使用,Java1.2提出了囊括所有集合接口.实现和算法的集合框架.在保证线程安全的情况下使用泛型和并发集合类,Java已经经历了很久.它还包括在Java并发包中,阻塞接口以及它们的实现.集合框架的部分优点如下: (1)使用核心集合类降低开发成本,而非实现我们自己的集合类. (2)随着使用经过严格测试的集合框架类,代

  • 关于Java集合框架的总结

    本篇文章先从整体介绍了Java集合框架包含的接口和类,然后总结了集合框架中的一些基本知识和关键点,并结合实例进行简单分析.当我们把一个对象放入集合中后,系统会把所有集合元素都当成Object类的实例进行处理.从JDK1.5以后,这种状态得到了改进:可以使用泛型来限制集合里元素的类型,并让集合记住所有集合元素的类型. 一.综述 所有集合类都位于java.util包下.集合中只能保存对象(保存对象的引用变量).(数组既可以保存基本类型的数据也可以保存对象). 当我们把一个对象放入集合中后,系统会把所

  • Java集合Map常见问题_动力节点Java学院整理

    Java集合Map常见问题,供大家参考,具体内容如下 1."你知道HashMap的工作原理吗?" "你知道HashMap的get()方法的工作原理吗?" 答:"HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象.当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象.

  • Java集合框架中迭代器Iterator解析

    Java里面的数组数据可以通过索引来获取,那么对象呢?也是通过索引吗?今天我们就来分析一下Java集合中获取集合对象的方法迭代-Iterator. 本篇文章主要分析一下Java集合框架中的迭代器部分,Iterator,该源码分析基于JDK1.8,分析工具,AndroidStudio,文章分析不足之处,还请指正! 一.简介 我们常常使用 JDK 提供的迭代接口进行 Java 集合的迭代. Iterator iterator = list.iterator(); while(iterator.has

  • Java集合ArrayDeque类实例分析

    Java集合ArrayDeque类实例分析 前言 ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等. public class ArrayDeque<E> extends AbstractCollection<E> implements Deque&

  • Java集合框架LinkedList详解及实例

    Java集合框架LinkedList详解 LinkedList定义 package java.util; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first;

  • Java集合源码全面分析

    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Se

  • Java 集合中的类关于线程安全

    Java集合中那些类是线程安全的 线程安全类 在集合框架中,有些类是线程安全的,这些都是jdk1.1中的出现的.在jdk1.2之后,就出现许许多多非线程安全的类. 下面是这些线程安全的同步的类: vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用.在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的. statck:堆栈类,先进后出 hashtable:就比hashmap多了个线程安全 enumeration:枚举,相当于迭代器

随机推荐