文档章节

Java核心(四)你不知道的数据集合

王磊的博客
 王磊的博客
发布于 2018/11/28 09:51
字数 2744
阅读 72
收藏 7

数据容器关系图

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

Java中的集合通常指的是Collection下的三个集合框架List、Set、Queue和Map集合,Map并不属于Collection的子集,而是和它平行的顶级接口。Collection下的子集的关系如文章开头图片所示。

本文的重点将会围绕: 集合的使用、性能、线程安全、差异性、源码解读等几个方面进行介绍。

本文涉及的知识点,分为两部分:

第一部分,Collection所有子集:

  • List => Vector、ArrayList、LinkedList
  • Set => HashSet、TreeSet
  • Queue

第二部分,Map => Hashtable、HashMap、TreeMap、ConcurrentHashMap。

一、List

我们先来看List、Vector、ArrayList、LinkedList,它们之间的继承关系图,如下图:

关系图

可以看出Vector、ArrayList、LinkedList,这三者都是实现集合框架中的List,也就是所谓的有序集合,因此具体功能也比较近似,比如都提供按照位置进行定位、添加或者删除的操作,都提供迭代器以遍历其内容等。但因为具体的设计区别,在行为、性能、线程安全等方面,表现又有很大不同。

来看它们的主要方法,如下图:

List方法

常用方法:

  • size 集合个数
  • add()/add(int, E) 添加末尾/添加指定位置
  • get(int) 获取
  • remove 删除
  • clear 清空
  • ...

1.1 Vector

Vector是Java早期提供的 线程安全的动态数组, 如果不需要线程安全,并不建议选择,毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据,可以根据需要自动的增加容量,当数组已满时,会创建新的数组,并拷贝原有数组数据。

看源代码可以知道,我们Vector是通过 synchronized 实现线程安全的:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

Vector动态增加容量,源码查看:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

capacityIncrement变量是what?答案如下:

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

Vector动态增加容量总结: 由上面的源码可知,如果初始化Vector的时候指定了动态容量扩展大小,就增加指定的动态大小,如果未指定,则扩展一倍的容量。

1.2 ArrayList

ArrayList 是应用更加广泛的<strong>动态数组</strong>,它本身不是线程安全的,所以性能要好很多。

ArrayList的使用与Vector类似,但有着不同的动态扩容机制,如下源码:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

其中“>> 1”是位运算相当于除2,所有ArrayList扩容是动态扩展50%.

1.3 LinkedList

LinkedList 顾名思义是 Java 提供的<strong>双向链表</strong>,所以它不需要像上面两种那样调整容量,它也不是线程安全的,它包含一个非常重要的内部类:Entry。Entry是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。

1.4 Vector、ArrayList、LinkedList区别

Vector、ArrayList、LinkedList的区别,可以从以下几个维度进行对比:

1.4.1 底层实现的区别

Vector、ArrayList 内部使用数组进行实现,LinkedList 内部使用双向链表实现。

1.4.2 读写性能方面的区别

ArrayList 对元素 非末位 的增加和删除都会引起内存分配空间的动态变化,因此非末位的操作速度较慢,但检索速度很快。

LinkedList 基于链表方式存放数据,增加和删除元素的速度较快,但是检索速度较慢。

1.4.3 线程安全方面的区别

Vector 使用了synchronized 修饰了操作方法是线程安全的,而 ArrayList、LinkedList 是非线程安全的。

如果需要使用线程安全的List可以使用CopyOnWriteArrayList类。

二、Map

Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现,是以<strong>键值对</strong>的形式存储和操作数据的容器类型。

它们之间的关系,如下图:

map

  • Hashtable 是早期 Java 类库提供的一个<a href="https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8">哈希表</a>实现,本身是同步的,不支持 null 键和值,由于同步导致的性能开销,所以已经很少被推荐使用。
  • HashMap 是应用更加广泛的哈希表实现,行为上大致上与 HashTable 一致,主要区别在于 HashMap 不是同步的,支持 null 键和值等。通常情况下,HashMap 进行 put 或者 get 操作,可以达到常数时间的性能,所以<strong>它是绝大部分利用键值对存取场景的首选</strong>,比如,实现一个用户 ID 和用户信息对应的运行时存储结构。
  • TreeMap 则是基于红黑树的一种提供顺序访问的 Map,和 HashMap 不同,它的 get、put、remove 之类操作都是 O(log(n))的时间复杂度,具体顺序可以由指定的 Comparator 来决定,或者根据键的自然顺序来判断。

HashMap 的性能表现非常依赖于哈希码的有效性,请务必掌握 hashCode 和 equals 的一些基本约定,比如:

  • equals 相等,hashCode 一定要相等;
  • 重写了 equals 也要重写 hashCode;
  • hashCode 需要保持一致性,状态改变返回的哈希值仍然要一致;
  • equals 的对称、反射、传递等特性;

线程安全: Hashtable是线程安全的,HashMap和TreeMap是非线程安全的。HashMap可以使用ConcurrentHashMap来保证线程安全。

三、Set

Set有两个比较常用的子集:HashSet、TreeSet.

HashSet内部使用的是HashMap实现的,看源代码可知:

public HashSet() {
    map = new HashMap<>();
}

HashSet也并不是线程安全的,HashSet用于存储无序(存入和取出的顺序不一定相同)元素,值也不能重复。

HashSet可以去除重复的值,如下代码:

public static void main(String[] args) {
        Set set = new HashSet();
        set.add("orange");
        set.add("apple");
        set.add("banana");
        set.add("grape");
        set.add("banana");
        System.out.println(set);
}

编译器不会报错,执行的结果为:[orange, banana, apple, grape],去掉了重复的“banana”选项。但排序是无序的,如果要实现有序的存储就要使用TreeSet了。

public static void main(String[] args) {
    Set set = new TreeSet();
    set.add("orange");
    set.add("apple");
    set.add("banana");
    set.add("grape");
    set.add("banana");
    System.out.println(set);
}

输出的结果是:[apple, banana, grape, orange]

同样,我们查看源码发现,TreeSet的底层实现是TreeMap,源码如下:

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet也是非线程安全的。

四、Queue

Queue(队列)与栈是相对的一种数据结构。只允许在一端进行插入操作,而在另一端进行删除操作的线性表。栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,但大多都是在其他的数据结构中,比如,树的按层遍历,图的广度优先搜索等都需要使用队列做为辅助数据结构。

Queue的直接子集,如下图:

queue

其中最常用的就是线程安全类:BlockingQueue.

4.1 Queue方法

  • 添加:add(e) / offer(e)
  • 移除:remove() / poll()
  • 查找:element() / peek()

注意:

  1. 避免add()和remove()方法,而是要使用offer()和poll()添加和移除元素。后者操作失败不会报错,前者会抛出异常;
  2. element() / peek() 都为查询第一个元素,不会删除集合,但element()查询失败会抛出异常,peek()不会。

4.2 Queue使用

Queue<String> queue =  new LinkedList<String>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
System.out.println(queue);
queue.poll();
System.out.println(queue);
queue.poll();
queue.poll();
queue.poll();
System.out.println(queue.peek());
// System.out.println(queue.element()); // element 查询失败会抛出异常
System.out.println(queue);

4.3 其他队列

ArrayBlockingQueue 底层是数组,有界队列,如果我们要使用生产者-消费者模式,这是非常好的选择。

LinkedBlockingQueue 底层是链表,可以当做无界和有界队列来使用,所以大家不要以为它就是无界队列。

SynchronousQueue 本身不带有空间来存储任何元素,使用上可以选择公平模式和非公平模式。

PriorityBlockingQueue 是无界队列,基于数组,数据结构为二叉堆,数组第一个也是树的根节点总是最小值。

ArrayBlockingQueue :一个由数组结构组成的有界阻塞队列。

LinkedBlockingQueue :一个由链表结构组成的有界阻塞队列。

PriorityBlockingQueue :一个支持优先级排序的无界阻塞队列。

DelayQueue:一个使用优先级队列实现的无界阻塞队列。

SynchronousQueue:一个不存储元素的阻塞队列。

LinkedTransferQueue:一个由链表结构组成的无界阻塞队列。

LinkedBlockingDeque:一个由链表结构组成的双向阻塞队列

五、扩展:String的线程安全

关于String、StringBuffer、StringBuilder的线程安全

String是典型的Immutable(不可变)类,被声明为final所有属性也都是final,所有它是不可变的,所有拼加、截取等动作等会产生新的String对象。

StringBuffer是为了解决上面的问题,而诞生的,提供了append方法实现了对字符串的拼加,append方法使用了synchronized实现了线程安全。

StringBuilder是JDK 1.5 新出的特性,作为StringBuffer的性能补充,StringBuffer的append方法使用了synchronized实现了线程的安全,但同时也带来了性能开销,在没有线程安全的情况下可以优先使用StringBuilder。

六、总结

List 也就是我们前面介绍最多的有序集合,它提供了方便的访问、插入、删除等操作。

Set 是不允许重复元素的,这是和 List 最明显的区别,也就是不存在两个对象 equals 返回 true。我们在日常开发中有很多需要保证元素唯一性的场合。

Queue/Deque 则是 Java 提供的标准队列结构的实现,除了集合的基本功能,它还支持类似先入先出(FIFO, First-in-First-Out)或者后入先出(LIFO,Last-In-First-Out)等特定行为。这里不包括 BlockingQueue,因为通常是并发编程场合,所以被放置在并发包里。

Map 是广义 Java 集合框架中的另外一部分,Map 接口存储一组键值对象,提供key(键)到value(值)的映射。

七、参考资料

《码出高效:Java开发手册》

Java核心技术36讲:http://t.cn/EwUJvWA

Oracle docs:https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html

© 著作权归作者所有

王磊的博客
粉丝 37
博文 30
码字总数 65460
作品 0
西安
私信 提问
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
day14_DBUtils学习笔记

一、DBUtils介绍 Apache公司开发的框架。   DBUtils是java编程中的数据库操作实用工具,小巧简单实用。   DBUtils封装了对JDBC的操作,简化了JDBC操作。可以少写代码。 commons-dbutils 是...

黑泽明军
2018/05/20
0
0
【java8】java新特性(二)——lambda表达式

一,前言 在上一篇博客中,小编向大家抛转引玉,简单说明了[ Java8 ](http://blog.csdn.net/kisscatforever/article/details/79572194 ),其实Java 8在2014年3月18日,就发布了。可以说程序...

kisscatforever
2018/03/20
0
0
从java程序员到CTO的成长路线图

很多新人不知道从事java开发,具体的发展路径是怎么样的,甚至很多人都不能区分程序猿和攻城师的区别。包括不少小白,从事java开发都半年,甚至1年了,对职业发展还没有清晰的认证。这非常不...

6pker
2013/10/24
0
2
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
2018/10/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

两数的最大公约数

hello,复习一下数学知识! 最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。 因为之前做一个小功能,需要先计算一下数组的最大公约数,所以我就想记录一下...

woshixin
今天
3
0
学习Node.js的电子书大全

在这里,与大家分享一批很有用的 Node.js 的电子书资源。Node 是一个服务器端的 JavaScript 解释器,它将改变服务器应该如何工作的概念。它的目标是帮助程序员构建高度可伸缩的应用程序,编写...

jay603
今天
58
0
《伟大的博弈》读后感作文4100字

《伟大的博弈》读后感作文4100字: 五一小长假,作为工厂员工,没能跟上大家放假的步伐,窝家里两天没出门,逼着自己看完《伟大的博弈》,感触颇多。似乎不能消化,先记录第一遍作为幼稚的见...

原创小博客
昨天
5
0
单点登录-基于Redis+MySQL实现单点登录(SSO)

1. 为什么要用单独登录? 主要便于公司内部多系统统一认证授权管理,一次登录可访问多个跨域系统,也同时更加方便统一管理用户登录(员工离职需要拿掉登录权限、统计所有用户对系统的登录请求...

秋日芒草
昨天
2
0
827. Making A Large Island

思想: 将所有连通的 1 分成一个组,分配编号,然后使用BFS统计1的个数,得到这个组的面积。 遍历格子里所有为 0 的元素,检查四个方向的1所在的组并加上这个组面积。于是得到当前元素为 0 ...

reter
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部