文档章节

Java基础之容器类库

klink
 klink
发布于 2014/05/29 17:32
字数 3148
阅读 56
收藏 2

java.util提供了各种各样的基础容器类库,如List, Set, Queue以及 Map。总的来讲,java的基础容器类库可以分出两大类:Conllection,Map (List, Set, Queue都继承自Collection)。

  1. Collection: 指的通常是只存储value的数据容器。
  2. Map: 存储的是Key-Value的键值对。其中Key必须是唯一的,用户可以通过Key查找相应的Value。

Iterable

Collection接口继承了Iterable接口。该接口只定义了一个iterator()方法,并返回Iteractor接口。Iteractor的优势在于:我们可以使用Iteractor来遍历不同类型的容器,不论是List, Queue还是Set,他们都继承了Iterable。 Iterable 的接口方法,请参考Java API Doc。

http://docs.oracle.com/javase/7/docs/api/java/lang/Iterable.html

Iterator 的接口方法,请参考 Java API Doc。

http://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

Collection

Collection 作为所有一维类型容器的基类,提供了一些操作容器的常用方法。详细的接口方法,请参考Java API Doc. http://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

List

List继承了Collection所有的接口方法,并且定义一些额外的方法:允许随机访问集合中的元素,可以在集合的中间进行插入和删除操作。

void	add(int index, E element)
//Inserts the specified element at the specified position in this list (optional operation).

boolean	addAll(int index, Collection<? extends E> c)
//Inserts all of the elements in the specified collection into this list at the specified position (optional operation).

E	get(int index)
//Returns the element at the specified position in this list.

int	indexOf(Object o)
//Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.


int	lastIndexOf(Object o)
//Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.


ListIterator<E>	listIterator()
//Returns a list iterator over the elements in this list (in proper sequence).

ListIterator<E>	listIterator(int index)
//Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.

E	remove(int index)
//Removes the element at the specified position in this list (optional operation).

E	set(int index, E element)
//Replaces the element at the specified position in this list with the specified element (optional operation).

List<E>	subList(int fromIndex, int toIndex)
//Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

从上面的列表中,我们可以看到不同于Iteractor接口的 ListIterator 接口。 这个接口的继承自Iteractor,它除了具有Iteractor往后遍历的功能之外,还可以往前遍历。并且可以获取当前元素在容器中的下标Index。

List有两种实现:ArrayList和LinkedList。

ArrayList

可以随机访问集合中的任意元素。但是在删除和插入时需要移动集合中的其他元素,效率较低。

ArrayList除了继承List的所有接口函数外,还继承了RadomAccess的接口。但是RadomAccess并没有接口方法。

ArrayList是非线程安全的,内部并没有提供同步机制。

ArrayList自己本身还实现了一些public方法

void	ensureCapacity(int minCapacity)
//Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

void	trimToSize()
//Trims the capacity of this ArrayList instance to be the list's current size.

LinkedList

只能顺序的访问集合中的元素,但是当插入和删除时不需要移动其他元素,效率很高。

LinkedList是非线程安全的,内部没有提供同步机制。

LinkedList也继承了List接口,并且实现了List接口中的所有方法。 此外ListedList还继承了Deque接口。而Deque继承了Queue接口。所以它可以用作 Stack, Queue, Double-ended Queue(双队列)。

Queue

Queue接口同样也继承了Collection接口。所不同的是Queue增加了队列的基本操作(First-in First-Out)。Queue的接口:

boolean	add(E e)
//Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element()
//Retrieves, but does not remove, the head of this queue.
boolean	offer(E e)
//Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E	peek()
//Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll()
//Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove()
//Retrieves and removes the head of this queue.

Deque

Deque继承自Queue接口。并提供了双向队列的一些操作。

void	addFirst(E e)
//Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions.
void	addLast(E e)
//Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions.
boolean	contains(Object o)
//Returns true if this deque contains the specified element.
Iterator<E>	descendingIterator()
//Returns an iterator over the elements in this deque in reverse sequential order.
E	getFirst()
//Retrieves, but does not remove, the first element of this deque.
E	getLast()
//Retrieves, but does not remove, the last element of this deque.
boolean	offerFirst(E e)
//Inserts the specified element at the front of this deque unless it would violate capacity restrictions.
boolean	offerLast(E e)
//Inserts the specified element at the end of this deque unless it would violate capacity restrictions.
E	peekFirst()
//Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
E	peekLast()
//Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
E	pollFirst()
//Retrieves and removes the first element of this deque, or returns null if this deque is empty.
E	pollLast()
//Retrieves and removes the last element of this deque, or returns null if this deque is empty.
E	pop()
//Pops an element from the stack represented by this deque.
void	push(E e)
//Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
boolean	remove(Object o)
//Removes the first occurrence of the specified element from this deque.
E	removeFirst()
//Retrieves and removes the first element of this deque.
boolean	removeFirstOccurrence(Object o)
//Removes the first occurrence of the specified element from this deque.
E	removeLast()
//Retrieves and removes the last element of this deque.
boolean	removeLastOccurrence(Object o)
//Removes the last occurrence of the specified element from this deque.
int	size()
//Returns the number of elements in this deque.

从Interface的列表中,可以看到了pop和push的方法,因此Deque其实也提供了Stack的操作。(First-in, Last-out)

E	pop()
//Pops an element from the stack represented by this deque.
void	push(E e)
//Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

此外在JDK1.0的时候,java提供了java.util.Stack类,Stack类提供了Stack的操作,但是并没有继承Deque接口。所以java在jdk 1.6推荐使用java.util.ArrayDeque类替代Stack类来实现Stack的功能。ArrayDeque实现了Deque接口。

ArrayDeque和LinkedList都实现了Deque的接口,所以都可以用作Stack,但是ArrayDeque和LinkedList内部实现是不同的,Array是基于顺序数组存储数据的,而LinkedList是基于链表存储数据的。

PriorityQueue

普通的Queue是遵循First-in, First-Out的准则的,但是PriorityQueue打破了这样的准则,当向PriorityQueue中放入元素时,它会基于Comparator定义的方法进行优先级比较,它会把优先级高的放到队列的最前面。

值得一提的是,PriorityQueue有6个构造函数,其中实用PriorityQueue(),PriorityQueue(int initialCapacity)构造的PriorityQueue队列,其队列中元素仍是按照插入的顺序排列的(First-in, First-out)。如果使用Comparator接口或者其子接口作为参数,PriorityQueue队列中的元素会依据Comparator的规则进行优先级对比。

PriorityQueue()
//Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue(Collection<? extends E> c)
//Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(int initialCapacity)
//Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
//Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue<? extends E> c)
//Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet<? extends E> c)
//Creates a PriorityQueue containing the elements in the specified sorted set.

Example 1: 使用PriorityQueue()构造的PriorityQueue

package io.github.klink;

import java.util.*;

public class PriorityQueueTest {

	public static void main(String[] args) {
		Queue<Integer> intQ = new PriorityQueue<Integer>();

		intQ.add(20);
		intQ.add(10);
		intQ.add(100);
		intQ.add(2);
		
		print(intQ);

	}

	public static void print(Queue<?> q) {
		Iterator<?> iter = q.iterator();

		while(iter.hasNext()) {
			System.out.print(iter.next()+"  ");
			
		}
	}
}

输出结果是插入的顺序:

2  10  100  20  

Example 2: 使用PriorityQueue(int initialCapacity, Comparator<? super E> comparator)构造的PriorityQueue

package io.github.klink;

import java.util.*;

public class PriorityQueueTest {

	public static void main(String[] args) {
		
		Queue<String> strQ = new PriorityQueue<String>(20,
				new Comparator<String>() {

					@Override
					public int compare(String str1, String str2) {
						// TODO Auto-generated method stub
						return str1.compareTo(str2);
					}
					
				});
		
		strQ.add("Hello");
		strQ.add("World");
		strQ.add("Nice");
		strQ.add("To");
		strQ.add("Meet");
		strQ.add("You");
		
		print(strQ);

	}

	public static void print(Queue<?> q) {
		Iterator<?> iter = q.iterator();

		while(iter.hasNext()) {
			System.out.print(iter.next()+"  ");
			
		}
	}
}

输出结果为:

Hello  Meet  Nice  World  To  You  

Set

Set接口只是继承了Collection的所有方法,本身并没有提供额外的方法。

Set的主要特点在于Set不能存储重复的值,当向Set中插入重复的值时,会报错。 基于Set接口的实现类有HashSet,LinkedHashSet,TreeSet。

HashSet

在往HashSet中存储数据时,会调用存储对象的getHashCode()方法,计算出唯一的hash值,该hash值会映射容器的一个位置,然后就会将该值存储在这个位置。所以HashSet中的元素是乱序的,我们利用Iteractor遍历HashSet时,获取的顺序并不是数据插入的顺序。

HashSet会初始化一段数组空间,当元素逐渐增多时,数据空间也会随之增大。

LinkedHashSet

它继承自HashSet,所以它的内部存储结构跟HashSet是一样的。

但是它除了具有HashSet的功能之外,还维护了一个链表,这个链表保存了HashSet中元素的插入顺序。所以通过Iteractor遍历LinkedHashSet时,元素获取的顺序是插入时的顺序。

TreeSet

TreeSet除了继承了Set接口之外,还继承了NavigableSet接口。NavigableSet又继承了SortedSet接口。NavigableSet是在java 1.6出现的,在java 1.5之前,TreeSet是直接继承的SortedSet接口。

TreeSet基于红-黑二叉树实现的,关于红-黑二叉树的介绍可参考http://blog.csdn.net/v_JULY_v/article/details/6105630

将元素存储到TreeSet,TreeSet中的元素会基于comparator()方法对元素进行比较后插入树中。所以利用Iteractor遍历TreeSet时,元素获取的顺序已经是通过comparactor()排完序的结果了。

SortedSet

SortedSet接口也继承了Set接口。并提供了一些额外的方法。具体每个方法的含义可参考注释。

Comparator<? super E>	comparator()
//Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
E	first()
//Returns the first (lowest) element currently in this set.
SortedSet<E>	headSet(E toElement)
//Returns a view of the portion of this set whose elements are strictly less than toElement.
E	last()
//Returns the last (highest) element currently in this set.
SortedSet<E>	subSet(E fromElement, E toElement)
//Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E>	tailSet(E fromElement)
//Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

NavigableSet

NavigableSet继承了SortedSet接口,除此之外还定义了额外的一些方法。感觉很强大的样子。

E	ceiling(E e)
//Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
Iterator<E>	descendingIterator()
//Returns an iterator over the elements in this set, in descending order.
NavigableSet<E>	descendingSet()
//Returns a reverse order view of the elements contained in this set.
E	floor(E e)
//Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
NavigableSet<E>	headSet(E toElement, boolean inclusive)
//Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E	higher(E e)
//Returns the least element in this set strictly greater than the given element, or null if there is no such element.
Iterator<E>	iterator()
//Returns an iterator over the elements in this set, in ascending order.
E	lower(E e)
//Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
E	pollFirst()
//Retrieves and removes the first (lowest) element, or returns null if this set is empty.
E	pollLast()
//Retrieves and removes the last (highest) element, or returns null if this set is empty.
NavigableSet<E>	subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
//Returns a view of the portion of this set whose elements range from fromElement to toElement.
NavigableSet<E>	tailSet(E fromElement, boolean inclusive)
//Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

TreeSet则完全实现这些方法。除此之外并没有提供额外的方法。

Map

Map用于存储Key-Value的容器。在Map容器中Key是唯一的,不能重复。可以看出Map与Set有很多相似之处。(其实Set的实现如HashSet,都是基于Map的实现进行封装的如HashMap)具体Map接口的方法,请参考Java API Doc http://docs.oracle.com/javase/7/docs/api/java/util/Map.html

Map的实现主要有HashMap, LinkedHashMap, TreeMap。

原理与Set一样。

历史遗留的类库

Vector

Vector是在java 1.0的时候开发的,当时是作为单独的容器提供了ArrayList的功能。后面在java 1.2中,也让Vector重新继承了List接口。

Stack

在上面的介绍中,也提到过,继承自Vector。

Dictionary 以及HashTable

HashTable起初设计是并没有考虑到可扩展性,但是也在java 1.2中,重新继承了Map接口。 HashTable是线程安全的。

© 著作权归作者所有

共有 人打赏支持
klink
粉丝 0
博文 24
码字总数 29450
作品 0
苏州
跳槽时,这些Java面试题99%会被问到

我在 Oracle 已经工作了近 7 年,面试过从初级到非常资深的Java工程师,且由于 Java 组工作任务的特点,我非常注重面试者的计算机科学基础和编程语言的理解深度,可以不要求面试者非要精通 ...

Java小铺
08/15
0
0
JDK源码之ClassLoader

Java类加载器ClassLoader总结 JAVA类装载方式,有两种: 1.隐式装载, 程序在运行过程中当碰到通过new 等方式生成对象时,隐式调用类装载器加载对应的类到jvm中。 2.显式装载, 通过class.for...

村长大神
2014/03/27
0
0
从java程序员到CTO的成长路线图

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

6pker
2013/10/24
0
2
Spring Boot实战之基础回顾

本文作者: 吴伟祥 本文链接: https://wuweixiang.cn/2018/08/21/Spring-Boot实战之基础回顾/ 版权声明: 本博客所有文章除特别声明外均为原创,采用CC BY-NC-SA 4.0 许可协议。转载请在文章开...

吴伟祥
08/21
0
0
linux web篇---之三--tomcat

一、java概述 1、java的四个独立却又相关的技术: java程序设计语言: java源程序 java API: 以连接java的库文件,官方提供很多库文件,以提高java的开发速度,通过API连接到相应的库文件。...

kuang_hp
07/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day96-20180923-英语流利阅读-待学习

英国王子也不看好人工智能,理由却和霍金不同 Daniel 2018-09-23 1.今日导读 2016 年 3 月 9 日至 15 日,世界围棋冠军李世石与谷歌研发的计算机围棋程序 AlphaGo 进行人机大战并以 1 比 4 ...

飞鱼说编程
今天
4
0
今天在码云遇到一个很有意思的人 for Per.js

今天在码云遇到一个很有意思的人,他在我的Per.js项目下面评论了一句,大意为“你试试这句代码,看看速度到底是你快还是Vue快”【当然,这个评论被我手残不小心删掉了...】。 然后我就试了,...

Skyogo
今天
31
0
Java -------- 首字母相关排序总结

Java 字符串数组首字母排序 字符串数组按首字母排序:(区分大小写) String[] strings = new String[]{"ba","aa","CC","Ba","DD","ee","dd"}; Arrays.sort(strings); for (int i ...

切切歆语
今天
2
0
还在用 Git 的 -f 参数强推仓库,你这是在作死!

最近,美国一个程序员因为同事不写注释,代码不规范,最严重的是天天使用 git push -f 参数强行覆盖仓库,该程序员忍无可忍向四名同事开抢,其中一人情况危急!!! 不写注释、代码不规范是一...

红薯
今天
535
0
NPM报错终极大法

所有的错误基本上都跟node的版本相关 直接删除系统中的node 重新安装 sudo rm -rf /usr/local/{bin/{node,npm},lib/node_modules/npm,lib/node,share/man/*/node.*} 重新安装 $ n lts$ npm...

lilugirl
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部