Fork me on GitHub

Java的艺术-Java容器(1)之容器基础

此处输入图片的描述
详解JAVA容器。

Java容器是什么?

容器,顾名思义,就是盛东西的地方。我们的程序中经常要管理大量的对象,比如在学校的信息管理系统里,每一个学生的相关信息,都可以抽象成一个对象;再比如在web server的场景下,一个客户端可以抽象成一个对象。这些情况下,都会产生很多同类型的对象,这时候,我们就会把同一个类型的对象放到同一个容器中进行集中管理。

Java的容器是前人为我们设计好的一套存储对象和数据的一套轮子,
通过使用Java中写好的容器API我们可以很方便的存储、操作我们的数据。

容器的作用:
Java容器类库是用来保存对象的,他有两种不同的概念:(1)Collection,独立元素的序列,这些元素都服从一条或多条规则。List、Set以及Queue都是Collection的一种,List必须按照顺序保存元素,而Set不能有重复元素,Queue需要按照排队规则来确定对象的顺序。(2)Map,Map是键值对类型,允许用户通过键来查找对象。Hash表允许我们使用另一个对象来查找某个对象。

为什么需要容器呢?
《thinking in java》书中说:“如果一个程序只包含固定数量的且生命周期都已知的对象,那么这是一个非常简单的数据。”但是事实上,我们平时接触的程序都不是如此简单的,很多程序都是在运行时才知道需要创建什么对象、创建多少对象,因此很可能我们需要在任意时刻任意位置创建任意数量的对象。因此,不能依靠创建命名的引用持有每一个对象,因为不确定性,我们必须要动态的创建对象,保存对象(其实是对象的引用)。

Java常见容器

Java完整容器类结构

此处输入图片的描述

详细结构及概述

结构

Collection接口
 ├List接口
  │├LinkedList 双向链表,顺序访问,快速增删,栈、队列、双向队列
  │├ArrayList 顺序结构动态数组实现,随机访问
  │└Vector 向量
   │└Stack 栈
 ├Set接口
  │├TreeSet 红黑树实现,有序,查找O(logN)
  │├HashSet 哈希表实现,无序,查找O(1)
   │└LinkedHashSet
 ├Queue接口
  │├PriorityQueue 堆实现,可实现优先队列
  │└LinkedList 双向链表,顺序访问,快速增删,栈、队列、双向队列
Map接口
 ├HashMap 哈希表实现,线程不安全
  ├Hashtable 线程安全,现为ConcurrentHashMap替换,分段锁
 ├TreeMap 红黑树实现
  ├LinkedHashMap 双向链表实现
  ├WeakHashMap
  └IdentityHashMap

一句话概括常用不同容器类

参考Github

1.Set
1.1 TreeSet:基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。
1.2 HashSet:基于哈希表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
1.3 LinkedHashSet:具有 HashSet 的查找效率,且内部使用双向链表维护元素的插入顺序。

2.List
2.1 ArrayList:基于动态数组实现,支持随机访问。
2.2 Vector:和 ArrayList 类似,但它是线程安全的。
2.3 LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间
插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列。

3.Queue
3.1 LinkedList:可以用它来实现双向队列。
3.2 PriorityQueue:基于堆结构实现,可以用它来实现优先队列。

4.Map
4.1 TreeMap:基于红黑树实现。
4.2 HashMap:基于哈希表实现。
4.3 HashTable:和 HashMap类似,但它是线程安全的,这意味着同一时刻多个线程可以同时写入 HashTable并且不会导致数据不一致。它是遗留类,不应该去使用它。现在可以使用ConcurrentHashMap 来支持线程安全,并且ConcurrentHashMap 的效率会更高,因为ConcurrentHashMap引入了分段锁。
4.4 LinkedHashMap:使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用( LRU) 顺序。


接下来,详细比较不同容器的区别和联系!

顶层接口-Collections接口

Collection是序列容器的顶级接口,这个interface定义了序列容器必须实现的所有成员方法。

常用方法

包括:容器容量,判断是否为空,检查容器元素,迭代器,增删等操作。

1
2
3
4
5
6
7
8
9
10
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
}

List接口及常用实现类

总结

实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。

LinkedList、ArrayList都实现了List接口,都是不同步的,线程不安全,元素是有序的、可重复。

一般情况下使用LinkedList、ArrayList这两个就可以了,因为非同步,所以效率比较高

ArrayList的随机访问效率较好,但是插入、删除元素较慢;LinkedList提供了优化的顺序访问,随机访问逊色于ArrayList,但插入、删除的代价较低。

总之,如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。

LinkedList

基于双向链表的数据结构,允许null元素,增加、删除、修改元素方面效率比ArrayList高。

LinkedList提供额外的get,remove,insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

注意:LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:List list = Collections.synchronizedList(new LinkedList(…));

ArrayList

概述

基于顺序结构的动态数组的数据结构,不同步,线程不安全,查询(get,set)效率高。

size(),isEmpty(),get(),set()方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

Array和ArrayList的区别及各自适用的场景:

Array是数组,ArrayList是Array的加强版。

(1)array可以保存基本类型和对象类型,arrayList只能保存对象类型

(2)array数组的大小是固定的不能更改,而ArrayList的大小可以改变

(3)Array数组在存放的时候一定是同种类型的元素。ArrayList就不一定了,因为ArrayList可以存储Object。

(4)ArrayList有更加丰富的方法如addAll()、removeAll()、iterator()

适用场景:
如果想要保存一些在整个程序运行期间都会存在而且不变的数据,我们可以将它们放进一个全局数组里,但是如果我们单纯只是想要以数组的形式保存数据,而不对数据进行增加等操作,只是方便我们进行查找的话,那么,我们就选择ArrayList。

如果我们需要对元素进行频繁的移动或删除,或者是处理的是超大量的数据,那么,使用ArrayList就真的不是一个好的选择,因为它的效率很低,使用数组进行这样的动作就很麻烦,那么,我们可以考虑选择LinkedList。

Vector

概述

Vector类似ArrayList,但是Vector是线程同步的。由Vector创建的Iterator,虽然和ArrayList创建的 Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。

Stack

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有 peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。


Set接口及常用实现类

概述

Set容器类主要有HashSetTreeSet等。
元素不重复。

HashSet

概述

允许包含值为null的元素,但最多只能有一个null元素。

基于哈希表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

TreeSet

TreeSet基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。

LinkedHashSet

LinkedHashSet的实现借助LinkedHashMap使用适配器模式实现的。具有 HashSet 的查找效率,且内部使用双向链表维护元素的插入顺序。


Map接口及常用实现类

总结

Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。

主要方法:

1
2
3
boolean equals(Object o)//比较对象
boolean remove(Object o)//删除一个对象
put(Object key,Object value)//添加key和value

TreeMap

TreeMap 和 TreeSet

TreeSet是借助TreeMap实现的的适配器模式的体现。TreeMap懂了TreeSet也了解了,TreeMap实现了SortedMap接口,会根据key的大小对Map中的元素进行排序。key的大小判断在没有传入比较器Comparator的情况下通过自身的自然顺序比较。TreeMap底层通过红黑树实现

红黑树是一颗近似平衡的二叉查找树,任何一个节点的左右子树高度差不会超过二者中较低的那个的一倍,TreeMap的每个节点即为一个键值对,红黑树的特性如下:

1
2
3
4
5
6
7
(1)每个节点要么是黑色,要么是红色
(2)根节点必须为黑色
(3)红色节点不能连续,即红色节点的孩子和父亲只能是黑色
(4)任何节点到树的末端的任何路径包含的黑色节点个数相同
(5)每次对红黑树操作后都要使其满足上述条件,调整红黑树的策略主要是:
- 改变节点颜色;
- 改变树的结构(左旋操作、右旋操作)

HashMap

HashTable和HashMap

第一、继承不同。

1
2
  public class Hashtable extends Dictionary implements Map
  public class HashMap  extends AbstractMap implements Map

第二、Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下,可以直接使用Hashtable,但是要使用HashMap的话就要自己增加同步处理了。

第三、Hashtable中,key和value都不允许出现null值。在HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。

第四、两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式 。

第五、哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

LinkedHashMap

LinkedHashMap实现了Map接口,即允许放入key为null的元素,也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体,也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用LinkedList增强的HashMap。

LinkedHashMap 和 LinkedHashSet:

LinkedHashSet和LinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。

LinkedHashMap是HashMap的子类,二者唯一的区别是LinkedHashMap在HashMap的基础上,采用双向链表(doubly-linkedlist)的形式将所有entry连接起来,这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry的插入顺序。

LinkedHashMap在遍历的时候不同于HashMap需要先遍历整个table,LinkedHashMap只需要遍历header指向的双向链表即可,因此LinkedHashMap的迭代时间只和entry数量相关。其他的包括初始容量、负载因子以及hashCode、equals方法基本和HashMap一致。

WeakHashMap

WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

ConcurrentHashMap

HashMap不是线程安全的,HashTable是线程安全的,但是其安全性由全局锁保证,因此效率很低。而ConcurrentHashMap 是将锁的范围细化来实现高效并发的。 基本策略是将数据结构分为一个一个 Segment(每一个都是一个并发可读的 hash table, 即分段锁)作为一个并发单元。 为了减少开销, 除了一处 Segment 是在构造器初始化的, 其他都延迟初始化。 并使用 volatile 关键字来保证 Segment 延迟初始化的可见性问题。

jdk1.8对ConcurrentHashMap做了一些改进:

改进一:取消segments字段,直接采用transient volatile HashEntry< K,V>[] table保存数据,采用table数组元素作为锁,从而实现了对每一行数据进行加锁,进一步减少并发冲突的概率。

改进二:将原先table数组+单向链表的数据结构,变更为table数组+单向链表+红黑树的结构。在冲突链表长度过长的情况,如果还是采用单向链表方式,那么查询某个节点的时间复杂度为O(n);因此,对于个数超过8(默认值)的列表,jdk1.8中采用了红黑树的结构,那么查询的时间复杂度可以降低到O(logN),可以改进性能。

容器的遍历

迭代器模式

Collection 实现了 Iterable 接口,其中的 iterator() 方法能够产生一个 Iterator 对象,通过这个对象就可以迭代遍历 Collection 中的元素。

1
2
3
4
Iterator it = container.iterator();
while(it.hasNext()) {
  Object obj = it.next();
}

List遍历

主要有三种:
第一种:迭代器+for

1
2
3
4
for(Iterator iterator = list.iterator();iterator.hasNext();){                    
int i = (Integer) iterator.next();
System.out.println(i);
}

第二种:迭代器

1
2
3
4
5
Iterator iterator = list.iterator();
while(iterator.hasNext()){
int i = (Integer) iterator.next();//注意next()返回的是Object对象!!
System.out.println(i);
}

第三种:增强for

1
2
3
for (Object object : list) {
System.out.println(object);
}

第四种:普通for

1
2
3
4
for(int i = 0 ;i<list.size();i++) {  
int j= (Integer) list.get(i);
System.out.println(j);
}

Map遍历

有四种:

第一种:通过获取所有的key按照key来遍历

1
2
3
4
//Set<Integer> set = map.keySet(); //得到所有key的集合
for (Integer in : map.keySet()) {
String str = map.get(in);//得到每个key多对用value的值
}

第二种:通过Map.entrySet使用iterator遍历key和value

1
2
3
4
5
Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

注意,用迭代器遍历Map时,Map没有iterator()方法,所以需要用entrySet()得到Set对象,再调用iterator()得到迭代器对象。

第三种:通过Map.entrySet遍历key和value,推荐,尤其是容量大时

1
2
3
4
5
6
for (Map.Entry<Integer, String> entry : map.entrySet()) {
//Map.entry<Integer,String> 映射项(键-值对) 有几个方法:用上面的名字entry
//entry.getKey() ;entry.getValue(); entry.setValue();
//map.entrySet() 返回此映射中包含的映射关系的 Set视图。
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

第四种:通过Map.values()遍历所有的value,但不能遍历key

1
2
3
for (String v : map.values()) {
System.out.println("value= " + v);
}


参考:
Java常见的容器类及其区别
Java中的容器
一份涵盖大部分Java程序员所需要掌握的核心知识
深入整理java集合容器

-------------本文结束感谢阅读-------------