引言
本文根据《Java语言程序设计 进阶篇 》(Y.Daniel Liang)进行学习总结编写。
本文章为原创性文章,如有转载请注明出处,尊重原创,谢谢。
说起Java集合框架,也许你会很陌生,但是你多少肯定用过。像Set、List、Queue等。可以把集合框架理解为数据结构,什么是数据结构?数据结构是以某种形式将数据组织在一起的集合(在面向对象思想里,可以理解为一个容器)。我们都知道,一个数据结构不仅存储数据,还支持对数据的访问和处理操作。Java中这种有效组织和操作数据的数据结构通常称为Java集合框架(java 2引入)。
或许你用过ArrayList、或许你用过HashSet、等等,但你或许未曾了解过这些集合框架背后的东西,了解它们与其他类、接口之间的关系。感兴趣的朋友可以结合本文在java开发工具中(Ctrl+鼠标左击)跳转到那些类中去查看源码了解。
Java集合框架支持2种类型的容器:
- 集合(collection),存储一个元素集合。
- 图(map),存储键值对。
本文主要对Java集合框架的集合容器进行深入学习并介绍。
由于本文较长,特提供目录以方便大家查阅:
集合(Collection)
Java集合框架的设计都是使用接口、抽象类和具体类的方式。用接口定义框架、抽象类提供接口的部分实现、具体类用具体的数据结构实现这个接口。
Java集合框架主要支持3中类型的集合:
规则集(Set):存储一组不重复的元素
线性表(List):存储一个由元素构成的有序集合
队列(Queue):存储用先进先出的方式处理的对象。
注:上面说的功能均为它们的接口实例的功能,因为它们本身都仅为接口。
我们去打开它们的源码会发现,它们都是继承于一个Collection的父接口。它是一个处理对象集合的根接口,它提供的方法有对一个集合的基本操作,包含了处理集合中元素的方法,并且可以获取一个迭代器对象(迭代器对象为遍历集合中元素)。
说了collection接口,再说一下AbstractCollection类,它是一个实现了collection接口中大部分方法的抽象便利类。方法size()和iterator()继续设计成抽象方法在合适的子类中实现,以最大程度地减少实现此接口所需的工作。 要实现不可修改的集合,只需扩展此类并为iterator和size方法提供实现。 要实现可修改的集合,须另外重写此类的add方法,并且iterator方法返回的迭代器必须另外实现其remove方法。 因为此类的add方法被设计为抛出异常 UnsupportedOperationException 。
下面给出我自己画了一个关系图,以了解集合框架中各类与接口之间的相互关系:

其中椭圆表示接口、虚线圆角矩形表示抽象类、实线圆角矩形表示具体类。实线箭头表示继承,虚线箭头表示实现接口。本文内容都可以结合本图进行学习。如果需要深入了解各类的实现,建议去查看Java源码。Java集合框架因为泛型的优点基本都被设计为泛型类。如果你仔细研究学习这些源码的实现,你会发现框架设计的如此的精妙,设计者是如此的聪明。
规则集(Set)
规则集也即Set接口,Set接口扩展了Collection集合。它并没有引入新的方法和常量,只是规定Set的实例不包含重复的元素。
AbstractSet类是一个扩展于AbstractCollection并实现了Set接口的便利类。如果仔细去看,会发现在抽象类 AbstractCollection 中并没有实现equel()方法和hashCode()方法,而在 AbstractSet 提供了 equel()和hashCode() 的具体实现,其中 hashCode()方法获取的散列码是这个规则集中所有元素散列码的和。同样的, AbstractSet没有实现 AbstractCollection 中的抽象方法size()和iterator(),所以它仍然是一个抽象类,它也只是定义一个框架。
规则集Set接口有3个具体的子类:HashSet(散列集)、LinkedHashedSet(链式散列集)和TreeSet(树形集)。下面分别对其进行介绍:
散列集(HashSet)
可以从上面的关系图可以看出,HashSet是一个继承于AbstractSet抽象类并实现了Set接口的具体类。 AbstractSet 定义了一个框架,HashSet扩展它成为了一种具体的数据结构,用来存储互不相同的任何元素。也可以说,HashSet就是采用哈希算法存取对象的集合 。 因此也为了效率,添加到散列集中的对象必须以一种正确分散散列码的方式来实现hashCode()方法。 关于 hashCode() 方法,是为提高从集合中查找元素的效率而设计的。
下面是一个HashSet的简单应用例子:
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println("size()="+set.size());
set.remove("London");
System.out.println("set:"+set);
System.out.println("size()="+set.size());
Set<String> set2 = new HashSet<>();
set2.add("London");
set2.add("Shanghai");
set2.add("Paris");
System.out.println("set2:"+set2);
System.out.println("size()="+set2.size());
System.out.println("Is Lanzhou in set?:"+set.contains("Lanzhou"));
set.addAll(set2);//并
System.out.println("set.addAll(set2);set:"+set);
set.removeAll(set2);//差
System.out.println("set.removeAll(set2);set:"+set);
set.retainAll(set2);//交
System.out.println("set.retainAll(set2):set:"+set);
}
输出:
San Francisco
Beijing
New York
London
Paris
size()=5
set:[San Francisco, Beijing, New York, Paris]
size()=4
set2:[Shanghai, London, Paris]
size()=3
Is Lanzhou in set?:false
set.addAll(set2);set:[San Francisco, Beijing, New York, Shanghai, London, Paris]
set.removeAll(set2);set:[San Francisco, Beijing, New York]
set.retainAll(set2):set:[]
可以看出HashSet是存储数据的顺序不是按被插入规则集时的顺序,因为散列集中元素时没有特定顺序的。 输出的顺序只是按照哈希值来取得的顺序。其他的就是一些基本操作,不再多以说明。
如果仔细去看HashSet的构造方法,会发现共有5个构造方法:默认无参构造、HashSet(Collection<? extends E> c)、HashSet(int initialCapacity)、public HashSet(int initialCapacity, float loadFactor)、HashSet(int initialCapacity, float loadFactor, boolean dummy),会普遍发现构造方法中有 initialCapacity 参数和 loadFactor 参数,那是什么意思呢? initialCapacity 即初始容量, loadFactor 为客座率。具体含义为当规则集中元素个数超过了规则集总容量的客座率倍时,规则集容量翻倍。默认HashSet的初始容量16,客座率0.75,即当规则集元素个数为16*0.75=12时,规则集容量翻倍为16*2=32。
链式散列集(LinkedHashSet)
LinkedHashSet是用一个链表实现来扩展HashSet的类。与HashSet不同的时,HashSet中的元素是没有被排序的,而LinkedHashSet它支持规则集中元素的排序。 LinkedHashSet 中的元素可以按照插入规则集的顺序提取。
下面是一个LinkedHashed的示例程序,只是将上边的HashSet替换为 LinkedHashed :
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
输出:
London
Paris
New York
San Francisco
Beijing
可见,元素是按插入集合的顺序存储的,同时因其为规则集,不能存储重复元素。LinkedHashSet相对于HashSet是可以顺序存储的,通常我们在使用的过程中,如果不需要维护元素的插入顺序,应使用HashSet,显然无需维护顺序使其更高效。如果我们要强加一个不同的顺序,如升序降序,可以使用下面介绍的TreeSet。
树形集(TreeSet)
如上面的关系图,TreeSet继承于AbstractSet并实现了 NavigableSet 接口, NavigableSet 又继承于SortedSet。
SortedSet是Set接口的一个子接口,顾名思义,它确保了规则集中的元素是有序的。去研究它的实现会发现,它还提供了frist()、last()方法用来返回规则集中首尾元素,以及headSet(e)方法返回规则集中元素小于e的部分、tailSet(e)方法返回元素≥e的部分。
NavigableSet 接口扩展了SortedSet接口,提供了以下方法:
- lower(e):返回小于e的最大元素
- floor(e):返回≤e的最大元素
- ceiling(e):返回≥e的最小元素
- higher(e):返回大于e的最小元素
- pollFirst():删除并返回第一个元素
- pollLast() :删除并返回最后一个元素
TreeSet是实现了SortedSet接口的一个具体类。只要对象是可以互相比较的,就可以将它们添加到一个树形集中。
比较对象又2种方法:
- 使用Comparable接口。通常使用这种比较方法定义的顺序称为自然顺序。
- 如果类的元素没有实现Comparable接口,或者在实现了Comparable接口的类种不想使用comparaTo()方法进行比较,那么可以给规则集中的元素指定一个比较器。这种方法定义的顺序被称为比较器顺序。
下面是一个TreeSet的应用实例程序,默认按Integer实现的 Comparable 接口方法 comparaTo() 来进行比较(自然顺序):
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
set.add(36);
set.add(18);
set.add(31);
set.add(29);
set.add(11);
System.out.println("HashSet:"+set);
NavigableSet<Integer> treeset = new TreeSet<>(set);
System.out.println("TreeSet:"+treeset);
System.out.println("first:"+treeset.first());
System.out.println("last:"+treeset.last());
//<29 all
System.out.println("headSet(29):"+treeset.headSet(29));
//≥29 all
System.out.println("tailSet(29):"+treeset.tailSet(29));
//<29 one
System.out.println("lower(29):"+treeset.lower(29));
//>29 one
System.out.println("higher(29):"+treeset.higher(29));
//≤29 one
System.out.println("floor(29):"+treeset.floor(29));
//≥29 one
System.out.println("ceiling(29):"+treeset.ceiling(29));
//delect first and return first
System.out.println("pollFirst:"+treeset.pollFirst());
//delect last and return last
System.out.println("pollLast:"+treeset.pollLast());
System.out.println("NewTreeSet:"+treeset);
}
输出:
zHashSet:[18, 36, 11, 29, 31]
TreeSet:[11, 18, 29, 31, 36]
first:11
last:36
headSet(29):[11, 18]
tailSet(29):[29, 31, 36]
lower(29):18
higher(29):31
floor(29):29
ceiling(29):29
pollFirst:11
pollLast:36
NewTreeSet:[18, 29, 31]
这个例子中,我用TreeSet的构造方法TreeSet(Collection<? extends E> c)使用以创建好的HashSet创建了一个NavigableSet接口的实例。为什么我不直接用无参构造创建一个默认的空集TreeSet,再add呢?原因是为了又较高的效率,使用new TreeSet(HashSet)创建只会只排一次序,而若使用TreeSet,每一次添加元素都会重新排序。然后就是一些基本操作了,不再多以说明。
了解了3种规则集,它们都有各自不同的用处,因此我们在使用时应当依据不同的需求使用适当的规则集。当更新一个规则集时,不需要维护顺序,应使用HashSet,要使保持插入时的顺序应使用LinkedHashSet,当需要一个排序号的集合时,可以创建TreeSet。
就上面的例子而言,如果我们需要按从大到小的顺序排序,该如何处理呢?这时就需要用到比较器接口Comparator了,即上面说的第二种比较对象的方法,比较器顺序。TreeSet提供了一个参数有 Comparator 比较器接口实例的构造方法,这样在定义TreeSet的时候就规定了它的比较方法。具体如下面的程序:
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
set.add(36);
set.add(18);
set.add(31);
set.add(29);
set.add(11);
System.out.println("HashSet:"+set);
Set<Integer> treeset = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return -1*o1.compareTo(o2);
}
});
treeset.addAll(set);
System.out.println("TreeSet:"+treeset);
}
输出:
HashSet:[18, 36, 11, 29, 31]
TreeSet:[36, 31, 29, 18, 11]
当然Comparator比较器接口也可以用来比较没有实现Comparable接口的类的对象。如下面的程序:
import java.io.Serializable;
import java.util.*;
public class Test{
public static void main(String[] args){
Set<? super BaseGeometricObject> treeset = new TreeSet<>(new GeometricObjectComparator());
treeset.add(new Rectangle(3,1.8F));
treeset.add(new Circle(1.5F));
treeset.add(new Rectangle(2,3));
System.out.println("TreeSet:"+treeset);
}
}
class GeometricObjectComparator implements Comparator<BaseGeometricObject>,Serializable{
@Override
public int compare(BaseGeometricObject o1, BaseGeometricObject o2) {
float s1 = o1.getArea(),s2 = o2.getArea();
return Float.compare(s1, s2);
}
}
/**
* 几何对象
*/
abstract class BaseGeometricObject {
/**
* 获取面积
* @return 面积
*/
abstract float getArea();
/**
* 比较面积是否相等
* @param geometricObject 比较对象
* @param <E> 受限的
* @return 是否相等
*/
<E extends BaseGeometricObject> boolean equalArea(E geometricObject){
return getArea()==geometricObject.getArea();
}
@Override
public String toString() {
return "Area="+getArea();
}
}
/**
* 矩形
*/
class Rectangle extends BaseGeometricObject {
private float width;
private float height;
Rectangle(float width, float height) {
this.width = width;
this.height = height;
}
@Override
float getArea() {
return width*height;
}
public float getWidth() {
return width;
}
public void setWidth(float width) {
this.width = width;
}
public float getHeight() {
return height;
}
public void setHeight(float height) {
this.height = height;
}
@Override
public String toString() {
return "Rectangle "+super.toString();
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Rectangle rectangle = (Rectangle) o;
return Float.compare(rectangle.width, width) == 0 &&
Float.compare(rectangle.height, height) == 0;
}
@Override
public int hashCode() {
return Objects.hash(width, height);
}
}
/**
* 圆
*/
class Circle extends BaseGeometricObject {
private float radius;
private final float PI = 3.1415926f;
Circle(float radius) {
this.radius = radius;
}
@Override
float getArea() {
return PI*radius*radius;
}
@Override
public String toString() {
return "Circle "+super.toString();
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Circle circle = (Circle) o;
return Float.compare(circle.radius, radius) == 0 &&
Float.compare(circle.PI, PI) == 0;
}
@Override
public int hashCode() {
return Objects.hash(radius, PI);
}
}
为了方便输出,我重写了toString输出面积。同时为了避免出现太多不同的对象出现相同的散列码的情况,这里的Rectangle类和Circle类应该重写hashCode()方法和equals()方法。通常对于比较起来说,实现Serializable接口是一个好主意,因为他们可以被用作像TreeSet这样的可序列化数据结果的排序方法。为了实现数据结构能够成功序列化,比较器(如果提供的话)必须实现 Serializable接口 。
线性表(List)
规则集要求元素不能重复,那么为了允许在一个集合中存储重复元素,就需要使用线性表List。线性表不仅可以存储重复元素,而且允许用户指定它们存储的位置。在List中,可以通过下标来访问元素。List接口时Collection的一个子接口,以定义一个允许重复的有序集合的框架。List接口增加了对元素面向位置的操作(如get(int)、indexOf(E)等),且listIterator()与listIterator(int index)方法返回一个ListIterator对象。
关于 ListIterator ,它不同于Iterator, ListIterator 不仅支持正序遍历,而且支持逆序遍历,且 listIterator 可以通过add()方法向集合中添加元素,且 listIterator 可以通过 nextIndex()和previousIndex() 定位当前的索引位置, 且 listIterator 可以通过set()方法修改对象 。
List接口有一个实现了部分List接口方法的遍历类AbstractList。
AbstractSequentialList类对AbstractList类进行了扩展,以提供对链表的支持。
数组线性列表(ArrayList)
ArrayList类为实现List接口的一个具体类,其继承于 AbstractList 抽象类。 ArrayList 类用数组存储元素。这个数组是动态创建的,如果元素个数超过了数组的容量就创建一个更大的新数组,并把当前数组中的所有元素都复制到新数字中,具体可查看ArrayList类中add(E)->ensureCapacityInternal(int)->ensureExplicitCapacity(int)->grow(int)方法。
也可以理解为ArrayList是一个实现List接口的大小可变的数组。每个ArrayList实例都有它的容量(默认容量DEFAULT_CAPACITY = 10),即指存储线性表中元素的数组的大小(即ArrayList类中Object[] elementData的大小)。向ArrayList添加元素时,其容量会自动检测是否增大(grow)。下面带大家具体分析一下。
在创建一个空的ArrayList时(即使用无参构造),线性表中的元素数组会被初始化成{}(DEFAULTCAPACITY_EMPTY_ELEMENTDATA),线性表大小size=0,在添加第一个元素的时候:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add(E)方法调用ensureCapacityInternal(size+1)方法:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
先会调用calculateCapacity(elementData, minCapacity)方法计算下一次元素数组的大小:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
此时线性表为空,elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA,计算结果为Math.max(10, 1)=10,然后调用ensureExplicitCapacity(10)方法:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
此时由于原元素数组大小为0,10-0>0成立,执行grow(10)方法将元素数组大小扩展为10:
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);
}
记录oldCapacity =0,计算newCapacity =0+0>>1=0,0-10<0满足,newCapacity 被改为10,10没有超过最大数组大小,将元素数组扩展为10。然后将第0个元素数组位置赋值为要添加的元素,然后size++,size=1。
在执行第二次到第十次add操作时,ensureExplicitCapacity()方法的数组扩展条件一直都不会满足,在执行第11次add的时候,就需要再次grow了。会将元素数组大小扩展为10+10>>1=30,同理在第31次add时,元素数组又被扩展为30+30>>1=90,以此类推。
看了ArrayList的这部分源码,你是否觉得在某些时候比如能估计出线性表所存储的元素个数时,在新建ArrayList的时候有必要使用ArrayList的容量构造方法ArrayList(int initialCapacity),指定初始容量,以提高ArrayList效率。
关于ArrayList的具体操作的应用,下面给出简单的程序实例:
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
//3 6 9 12 15
for (int i = 0; i++ < 5; list.add(i*2+i)) {}
System.out.println(list);
ListIterator<Integer> listIterator = list.listIterator(list.size());
while (listIterator.hasPrevious()){
int previous = listIterator.previous();
listIterator.remove();
listIterator.add(previous-1);
//14 11 8 5 2
System.out.print(listIterator.previous()+" ");
}
System.out.println(list);
}
输出:
[3, 6, 9, 12, 15]
14 11 8 5 2
[2, 5, 8, 11, 14]
该程序主要测试了ListIterator迭代器的一些用法,如倒序遍历元素且使用 ListIterator 对元素进行一些操作。需要注意的是,在取逆向迭代器时要使用listIterator(list.size()),而不是listIterator()。还有就是在使用 ListIterator 的add()、set()与remove()时,需要特别注意迭代器的迭代位置,以避免造成死循环与一些异常错误。具体什么意思?如上面程序中的迭代while循环能否改成下面的程序:
while (listIterator.hasPrevious()){
int previous = listIterator.previous();
listIterator.set(previous-1);
System.out.print(listIterator.previous()+" ");
}
你会发现会报NoSuchElementException错误,为什么呢?具体分析如下:第一次取15,把15改成14,位置移动到元素12,输出12;第二次取9,把9改成8,位置移动到元素6,输出6;第三次取3,3改为2,位置移动到原元素3前面的位置,就出错了。修正只需删除sout那句即可。但在使用add()方法时,也需要注意,如下面的代码:
while (listIterator.hasPrevious()){
int previous = listIterator.previous();
listIterator.add(previous-1);
}
它将会造成死循环,每次迭代添加一个元素,下一次迭代到上次添加的那个元素,如此循环,永无止境。修正只需在add()方法后添加一句listIterator.previous()将位置跳转到下一个使下次遍历跳过刚才添加的元素即可。
链表类(LinkedList)
LinkedList是List实现的一个链表,在一个链表中存储元素。处理实现List的接口方法外,还提供了在链表两端插入和删除元素的方法,如addFirst(E)、removeLast()等。可以从一个集合创建一个LinkedList,即LinkedList的集合构造方法LinkedList(Collection<? extends E> c)。 LinkedList 也实现了Deque接口, Deque 是一个双端队列接口,具体在下面会有介绍。
下面给出了 LinkedList 的一个简单的应用示例:
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
//3 6 9 12 15
for (int i = 0; i++ < 5; list.add(i*2+i)) {}
System.out.println(list);
LinkedList<Integer> linkedList = new LinkedList<>(list);
//上句同list = Arrays.asList(3,6,9,12,15);
//3 6 8 9 12 15
linkedList.add(2,8);
//3 6 8 9 15
linkedList.remove(4);
//6 3 6 8 9 15
linkedList.addFirst(6);
//6 3 6 8 9
linkedList.removeLast();
//removeLastOccurrence为删除列表中倒找到的第一个6
//6 3 8 9
linkedList.removeLastOccurrence(6);
//8 6 3 8 9
linkedList.addFirst(8);
//8 6 3 8 9 8
linkedList.addLast(8);
//6 3 8 9 8
linkedList.remove(new Integer(8));
//上句同linkedList.removeFirstOccurrence(8);
System.out.println(linkedList);
}
输出:
[3, 6, 9, 12, 15]
[6, 3, 8, 9, 8]
基本的不再多说 了,说下removeFirstOccurrence(Object),其为删除第一个在线性表中正序出现的元素,removeLastOccurrence(Object)相反,其中 removeFirstOccurrence(Object) 即remove(Object)。还有就是可以通过静态方法创建ArrayList,如上面的list = Arrays.asList(3,6,9,12,15);。
其实ArrayList和LinkedList的操作类似,主要的不同就是它们的内部实现,一个是元素数组,一个是链表,内部的实现会影响它们的性能。如果应用程序不需要早线性表中插入和删除元素,或是 仅需提取元素和在尾部插入或删除元素 ,那么ArrayList数组是最高效的数据结构。如果要在线性表的任意位置上插入和删除元素,那么LinkedList的效率会更高一些。
向量类(Vector)和栈类(Stack)
Java集合框架在java2中引入,但在java2之前就有了Vector和Stack。为了适应Java集合框架,java2对 Vector和Stack 进行了重新设计,但为了向后兼容,保留了它们所有旧形式的写法。
Vector类是继承自AbstractList并实现了List接口的一个具体类。 Vector内部同ArrayList都是使用Object数组来存储对象的。 与ArrayList除了包含用于访问和修改向量的同步方法是一样的。同步方法用于防止多个线程同时访问某个向量时引起的数据损坏。因此对不需要同步(多线程)的应用程序,使用ArrayList比Vector更高效。
如果你打开Vector的源码,你会发现有很多方法有synchronized关键字,它即将方法修饰为同步方法。同时会发现有很多方法类似于List接口中的方法,因为它们保留了在java2引入集合框架前的方法。简单进行介绍,如elements()方法返回Enumeration枚举型接口实例对象。 Enumeration 接口是java2之前引入的,已被Iterator接口替代,在java2之前,Vector是被用的很广泛的类,因为它可以实现Java可变大小的数组,有所了解即可。
Stack类是Vector类的一个扩展类,即继承了Vector类,提供了push(E)、pop()、peek()、empty()、search(Object)方法。
empty()即isEmpty(),peek()返回栈顶元素,pop()返回栈顶元素并删除,push(E)向栈中添加元素,search(Object)返回元素在栈中的下标,用于判断元素是否在栈内。
关于Vector和Stack线程安全的应用,需要注意的是线程安全不一定就是使用安全,可以从下面的例子来说明:
/**
* Vector(Stack)线程安全测试
* 参考:https://blog.csdn.net/shecanwin/article/details/70846690
*/
public class Main {
static Vector<Integer> testVector = new Vector<>();
public static void main(String[] args) {
while (true) {
for (int i = 0; i < 10; i++) {
testVector.add(i);
System.out.println("add" + i);
}
Thread remove = new Thread(() -> {
try {
for (int i = 0; i < testVector.size(); i++) {
testVector.remove(i);
System.out.println("remove" + i);
Thread.sleep(100);
}
} catch (Exception e) {
e.printStackTrace();
}
});
Thread print = new Thread(() -> {
try {
for (int i = 0; i < testVector.size(); i++) {
System.out.println(testVector.get(i));
Thread.sleep(100);
}
} catch (Exception e) {
e.printStackTrace();
}
});
print.start();
remove.start();
//避免创建过多的线程,使始终最多保持10个线程
while (Thread.activeCount() > 10) ;
}
}
}
输出:
……
remove8
java.lang.ArrayIndexOutOfBoundsException: Array index out of range: 8
at java.util.Vector.get(Vector.java:751)
at Main.lambda$main$1(Main.java:35)
at java.lang.Thread.run(Thread.java:748)
……
这段代码看似没有问题但运行报错ArrayIndexOutOfBoundsException,因为 get()方法和remove()方法之间并没有在以上环境中做到同步,如上面报错中一个线程在get(8)时另一个线程巧合执行到remove(8),此时get(8)被阻塞等待remove(8)完成,remove8完成后再执行get(8)时,就数组下标溢出了。为了解决可以在线程运行体上加 synchronized (testVector) {……}, 使读取、删除线程中只会有一个对testVector进行操作 。
队列(Queue)与双端队列(Deque)
队列是先进先出的数据结构。添加元素被追加到队尾,从队头取元素进行删除。
Queue接口是Collection接口的一个子接口,主要添加了offer(E)、poll()、peek()等方法。offer(E)向队列中插入一个元素;poll()获取队列头并删除;peek()获取队列头但不删除;remove()方法同poll(),区别为如果队列为空,poll()返回null而remove()抛出异常;element()方法同peek(),区别同 remove()与poll()。
双端队列Deque是由Queue接口扩展而来,顾名思义,支持在两端插入和删除元素。Deque接口添加了从队列两端插入和删除元素的方法来扩展Queue(如addFirst(E)、removeFirst()、addLast(E)、removeLast()、getFirst()、getLast()这些方法)。 这里温馨提示一下发音,Queue读为”Q”,Deque读为”deck”。
前面所说过,LinkedList类也实现了Queue接口,因此可以用LinkedList来创建一个队列:
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.offer("LonelyMoon");
queue.add("Devil");
queue.offer("LemonMeowMeow");
queue.add("Smile");
//offer同add
String s;
while ((s = queue.poll())!=null){
System.out.println(s);
}
/*
//遍历方法2:
while (queue.peek()!=null){
System.out.println(queue.poll());
}//**
/*
//遍历方法3:
while (queue.size()!=0){
System.out.println(queue.poll());
}//*/
}
输出:
LonelyMoon
Devil
LemonMeowMeow
Smile
优先队列类(PriorityQueue)
PriorityQueue优先队列类是一个继承于AbstractQueue的具体类。AbstractQueue是实现了Queue部分接口方法的便利抽象类。
默认情况下,优先队列使用Comparable接口以元素的自然顺序进行排序。即拥有最小数值的元素被赋予最高优先级,最先被队列删除。具有相同最高优先级的元素,其中任意一个从队列里删除。同TreeSet,创建时,可以定义一个比较器Comparator,以实现一个比较器顺序,即构造方法PriorityQueue(Comparator<? super E> comparator)。
下面给出一个简单示例:
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.offer("LonelyMoon");
queue.add("Devil");
queue.offer("LemonMeowMeow");
queue.add("Smile");
//默认使用String实现的Comparable接口方法compareTo()来排的自然顺序
Queue<String> priorityQueue = new PriorityQueue<>(queue);
//add同offer
String s;
while ((s = priorityQueue.poll())!=null){
System.out.print(s + (priorityQueue.peek()==null?"\n":" "));
}
//使用Comparator比较器(这里直接通过工具类静态方法返回一个逆自然顺序比较器)
Queue<String> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());
priorityQueue2.addAll(queue);
while ((s = priorityQueue2.poll())!=null){
System.out.print(s + (priorityQueue2.peek()==null?"":" "));
}
}
输出:
Devil LemonMeowMeow LonelyMoon Smile
Smile LonelyMoon LemonMeowMeow Devil
在使用默认自然顺序的那部分程序使用定义好的集合queue,创建一个优先队列,即使用了构造方法PriorityQueue(Collection<? extends E> c)。在使用自定义比较器的比较器顺序的那部分程序通过工具类静态方法返回一个逆自然顺序比较器,来创建优先队列,即使用构造方法PriorityQueue(Comparator<? super E> comparator)。当然使用比较器 Comparator 接口,也可以用来处理自定义对象,如下例:
public static void main(String[] args) {
Queue<? super BaseGeometricObject> priorityQueue = new PriorityQueue<>((o1, o2) -> {
float s1 = o1.getArea(),s2 = o2.getArea();
return Float.compare(s2, s1);
});
priorityQueue.offer(new Rectangle(6,2.2F));
priorityQueue.offer(new Circle(2));
priorityQueue.offer(new Rectangle(3,4));
while (priorityQueue.size()!=0){
System.out.print(priorityQueue.poll() + (priorityQueue.peek()==null?"":" "));
}
}
输出:
Rectangle Area=13.200001 Circle Area=12.56637 Rectangle Area=12.0
示例中BaseGeometricObject、Rectangle、Circle即为上面TreeSet的示例中用到的。这里为了方便演示,PriorityQueue(Comparator<? super E> comparator)构造方法直接 Lambda 传入new的一个 Comparator 实例,建议可以写一个实现类传入,同时实现Serializable接口,TreeSet示例那有说明。
阻塞队列接口(BlockingQueue)
BlockingQueue定义了阻塞队列框架, 即可视之为一个缓冲区应用于多线程编程之中。 当队列为空时,它会阻塞所有消费者线程,而当队列为满时,它会阻塞所有生产者线程。 BlockingQueue 是Queue的一个子接口,添加了put()、take()、 drainTo()方法。 put方法将指定的元素插入队列,必要时等待空间可用,即队列已满则阻塞。 take方法返回并删除此队列的头,必要时等待元素变为可用,即若队列已空阻塞。drainTo方法从队列中删除所有可用元素并将它们添加到给定集合中。
BlockingQueue 接口有好几个具体实现类。如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue、SynchronousQueue。具体在此不做多的介绍。关于阻塞队列,在此不做过多叙述,今后在多线程的应用中涉及到时会再介绍。
线性表和集合的静态方法
规则集中可以使用TreeSet存储有序的元素(自动排序)。但在线性表中旧不支持了。但是Java集合框架提供了 Collections类 ,可以使用其对线性表进行的静态方法sort对线性表进行排序。Collections类是一个提供了对线性表、集合的静态方法的工具类,还包含了用于线性表的binarySearch(二分查找)、reverse(倒置)、shuffe(打乱)、copy(赋值)、fill(填充)等方法,以及用于集合的max、min、disjoint(是否没有交集)、frequency(统计元素出现次数)方法。
下面是一个简单的示例应用程序:
public static void main(String[] args) {
/**
* sort排序
*/
List<String> list = Arrays.asList("lemon","apple","orange","banana");
//使用默认comparable接口方法进行自然顺序排序
Collections.sort(list);
//上句同list.sort(null);
System.out.println(list);
//使用默认comparable接口方法进行逆自然顺序排序
list.sort(Collections.reverseOrder());
//上句同Collections.sort(list,Collections.reverseOrder());
System.out.println(list);
List<? extends BaseGeometricObject> geometriclist = Arrays.asList(new Rectangle(3,4),new Circle(2),new Rectangle(1.5F,6));
Collections.sort(geometriclist, (o1, o2) -> Float.compare(o1.getArea(),o2.getArea()));
//上句同geometriclist.sort((o1, o2) -> Float.compare(o1.getArea(),o2.getArea()));
//也可以对BaseGeometricObject实现Compareable接口后使用Collections.sort(geometriclist);或geometriclist.sort(null);
System.out.println(geometriclist);
/**
* 复制
*/
List<Integer> list1 = Arrays.asList(7,4,8,2,9,3,6);
List<Integer> list2 = Arrays.asList(new Integer[list1.size()]);
System.out.println(list2);
Collections.copy(list2,list1);
System.out.println(list2);
//返回包含某对象N个副本的列表,如下返回包含10个6的list
list2 = Collections.emptyList();
list2 = Collections.nCopies(10,6);
System.out.println(list2);
//上面的nCopies(10,6);可以用下面的fill实现
/**
* 填充
*/
list2 = Arrays.asList(new Integer[10]);
Collections.fill(list2,6);
System.out.println(list2);
/**
* binarySearch二分查找
*/
list1 = Arrays.asList(7,4,8,2,9,3,6);
list1.sort(null);
System.out.println(list1);
//2 3 4 6 7 8 9
System.out.println(Collections.binarySearch(list1,8));
System.out.println(Collections.binarySearch(list1,5));
/**
* 倒置
*/
Collections.reverse(list1);
System.out.println(list1);
/**
* 打乱
*/
Collections.shuffle(list1);
System.out.println(list1);
/**
* Collections对于集合的一些静态方法
*/
System.out.println("max:"+Collections.max(list1));
System.out.println("min:"+Collections.min(list1));
list1 = new ArrayList<>(Arrays.asList(6, 3, 3, 6, 9, 6, 6));
list2 = new ArrayList<>(Arrays.asList(1, 8, 9, 7, 2, 5, 3));
//frequency获取list1中6出现的次数
System.out.println(Collections.frequency(list1,6));
//disjoint判断list1和list2是否没有交集
System.out.println(Collections.disjoint(list1,list2));
}
输出:
[apple, banana, lemon, orange]
[orange, lemon, banana, apple]
[Rectangle Area=9.0, Rectangle Area=12.0, Circle Area=12.56637]
[null, null, null, null, null, null, null]
[7, 4, 8, 2, 9, 3, 6]
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
[2, 3, 4, 6, 7, 8, 9]
5
-4
[9, 8, 7, 6, 4, 3, 2]
[9, 7, 4, 6, 3, 2, 8]
max:9
min:2
4
true
Collections.sort()方法其实也是调用线性表本身的sort方法,使用自然顺序时即sort(null),使用比较器时即list.sort(c)。copy函数使用时需要目标线性表的长度(非容量大小)大于等于源线性表的长度。
如文章有任何错误,请不吝指正,欢迎评论交流。
发表评论