Java集合源码学习(五)几种常用集合类的比较

这篇笔记对几个常用的集合实现,从效率,线程安全和应用场景进行综合比较。

1.ArrayList、LinkedList与Vector的对比

(1)相同和不同
都实现了List接口,使用类似。
Vector和ArrayList的底层实现都是数组,这一点与LinkedList的双向链表不同。
Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间,而ArrayList每次对size增长50%。
(2)线程安全
ArrayList、LinkedList都没有进行同步,可以使用 Collections的同步方法进行包装。

(3)性能比较
在ArrayList和Vector中,从一个指定的位置(通过索引)查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的,这个时间我们用O(1)表示。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置,即时间复杂度O(N)。为什么会这样呢?因为数组在内存上是连续的,进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。
如果你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是其他操作,你最好选择其他的集合操作类。比如,LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的O(1),但它在索引一个元素的是有比较慢,O(i),其中i是索引的位置。

2.HashMap与HashTable比较

(1)是否允许空值
HashMap允许 null 值(key和value都可以),Hashtable不允许 null 值(key 和 value 都不可以),
这一点在之前学习源码时也注意到了,看一下HashTable的源码:


1

2

3

4

5

6

7

public synchronized V put(K key, V value) {

       // Make sure the value is not null

       if (value == null) {

           throw new NullPointerException();

       }

       ......

   }

(2)哈希值的使用不同
Hashtable直接使用对象的hashCode,代码是这样的:


1

2

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

而HashMap重新计算hash值,这一点在之前的分析中也看到了:


1

2

int hash = hash(k);

int i = indexFor(hash, table.length);

另外还有一些如内部链表数组使用方式不同等差异。

(3)线程安全
HashMap和HashTable在线程安全性上就如同ArrayList和Vector类似,
HashTable的操作都使用synchronized做了同步。需要注意这是一种性能较低的线程安全。

>>HashSet和HashMap的区别

HashSet 实现了 Set 接口,它不允许集合中有重复的值,在将对象存储在 HashSet 之前,要先确保对象重写 equals()和 hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象。
HashMap 实现了 Map 接口,Map 接口对键值对进行映射。Map 中不允许重复的键。Map 接口有两个基本的实现,HashMap 和 TreeMap。TreeMap 保存了对象的排列次序,而 HashMap 则不能。HashMap 允许键和值为 null。

(1)不同之处
HashMap实现了Map接口 HashSet实现了Set接口
HashMap储存键值对 HashSet仅仅存储对象
使用put()方法将元素放入map中 使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值 HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
HashMap比较快,因为是使用唯一的键来获取对象 HashSet较HashMap来说比较慢

(2)线程安全
HashMap 是非 synchronized 的。

时间: 2024-09-21 21:30:51

Java集合源码学习(五)几种常用集合类的比较的相关文章

Java集合源码学习(二)ArrayList分析

Java集合源码学习笔记(二)ArrayList分析 1.关于ArrayList ArrayList直接继承AbstractList,实现了List. RandomAccess.Cloneable.Serializable接口, 为什么叫"ArrayList",因为ArrayList内部是用一个数组存储元素值,相当于一个可变大小的数组,也就是动态数组. (1)继承和实现 继承了AbstractList,实现了List:ArrayList是一个数组队列,提供了相关的添加.删除.修改.遍历

Java集合源码学习(三)LinkedList分析

前面学习了ArrayList的源码, 数组是顺序存储结构,存储区间是连续的,占用内存严重,故空间复杂的很大. 但数组的二分查找时间复杂度小,为O(1),数组的特点是寻址容易,插入和删除困难. 今天学习另外的一种常用数据结构LinkedList的实现, LinkedList使用链表作为存储结构,链表是线性存储结构,在内存上不是连续的一段空间, 占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N),链表的特点是寻址困难,插入和删除容易. 所有的代码都基于JDK 1.6. >>关于Lin

Java集合源码学习(四)HashMap分析

ArrayList.LinkedList和HashMap的源码是一起看的,横向对比吧,感觉对这三种数据结构的理解加深了很多. 1.数组.链表和哈希表结构 数据结构中有数组和链表来实现对数据的存储,这两者有不同的应用场景, 数组的特点是:寻址容易,插入和删除困难:链表的特点是:寻址困难,插入和删除容易: 哈希表的实现结合了这两点,哈希表的实现方式有多种,在HashMap中使用的是链地址法,也就是拉链法. 看下面这张流传很广的图, 拉链法实际上是一种链表数组的结构,由数组加链表组成,在这个长度为16

Java集合源码学习(一)集合框架概览

>>集合框架 Java集合框架包含了大部分Java开发中用到的数据结构,主要包括 List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections)几个部分. >>Collection系列 画类图好麻烦,强烈推荐processon.com. 注意,在Eclipse中使用Ctrl+T查看Collection接口的继承与实现关系, 会发现好多用于并发的相关容器,以及第三方的包实现了这个接口,这里只考察原生Java集合

Java集合源码剖析:Vector源码剖析

Vector简介 Vector也是基于数组实现的,是一个动态数组,其容量能自动增长. LinkedList是JDK1.0引入了,它的很多实现方法都加入了同步语句,因此是线程安全的(其实也只是相对安全,有些时候还是要加入同步语句来保证线程的安全),可以用于多线程环境. LinkedList没有丝线Serializable接口,因此它不支持序列化,实现了Cloneable接口,能被克隆,实现了RandomAccess接口,支持快速随机访问. Vector源码剖析 Vector的源码如下(加入了比较详

Java集合源码剖析:Java集合框架

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

Java集合源码剖析:TreeMap源码剖析

前言 本文不打算延续前几篇的风格(对所有的源码加入注释),因为要理解透TreeMap的所有源码,对博主来说,确实需要耗费大量的时间和经历,目前看来不大可能有这么多时间的投入,故这里意在通过于阅读源码对TreeMap有个宏观上的把握,并就其中一些方法的实现做比较深入的分析. 红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,关于二叉排序树,参见:http://blog.csdn.net/ns_code/article/details/1982

Java集合源码剖析:Hashtable源码剖析

Hashtable简介 Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长. Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中. Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆. HashTable源码剖析 Hashtable的源码的很多实现都与HashMap差不多,源码如下(加入了比较详细的注释):

Java集合源码剖析:HashMap源码剖析

HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长. HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap. HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆. HashMap源码剖析 HashMap的源码如下(加入了比较详细的注释): pac