文档章节

Java基础之容器类库

klink
 klink
发布于 2014/05/29 17:32
字数 3148
阅读 57
收藏 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
读书笔记之《Java并发编程的艺术》-并发编程容器和框架(重要)

读书笔记部分内容来源书出版书,版权归本书作者,如有错误,请指正。 欢迎star、fork,读书笔记系列会同步更新 git https://github.com/xuminwlt/j360-jdk module j360-jdk-thread/me.j360....

Hi徐敏
2015/11/11
0
1
应用容器云:接过Java EE的枪

本文根据DCOS联盟第4期线上分享整理而成 讲师介绍 主题大纲: 大家好,首先自我介绍一下。 src="https://mmbiz.qlogo.cn/mmbizjpg/tibrg3AoIJTuJYJOrPmDD4LOoZsT5GzmMk1IOdnKf0ia1nM0VN69EBI...

宋潇男
2016/12/20
0
0
Java类加载器ClassLoader

JAVA类装载方式,有两种: 1.隐式装载, 程序在运行过程中当碰到通过new 等方式生成对象时,隐式调用类装载器加载对应的类到jvm中。 2.显式装载, 通过class.forname()等方法,显式加载需要的...

兴国First
10/14
0
0
从读取properties文件说开去,浅谈web容器中类加载器

今天刚好有人让我写个通过读取properties连接数据库的小demo. 汗啊,普通项目中可以使用的文件读取,在web项目中总报空指针异常. 查阅了资料明白,赶紧记录下来,希望遇到此类问题的童鞋能引起重...

jeffsui
2012/10/31
0
10

没有更多内容

加载失败,请刷新页面

加载更多

linux脚本中父shell与子shell 执行的几种方式

本文主要介绍以下几个命令的区别: shell subshell source $ (commond) `commond` Linux执行Scripts有两种方式,主要区别在于是否建立subshell 1. source filename or . filename 不创建sub...

问题终结者
8分钟前
1
0
git简单操作

1、 git init 初始化仓库 git add 1.txt 添加文件 git commit -m ”commit” 提交更新,添加注释 git status 查看仓库状态 git log 查看日志 //修改文件后提交更新 git diff 查看有哪些修改 ...

xiaobai1315
13分钟前
1
0
基于vue的Element-ui定义自己的select组件

基于vue的Element-ui定义自己的select组件 <template> <div> <el-select v-model="svalue" placeholder="请选择" filterable> <el-option v-for="item in options"......

莫沫达
14分钟前
1
0
对象检测(object detection)算法图解

摘要: 本文简要介绍图像检测中常用的深度学习方法——RCNN家族系列算法,以图像讲解形式,便于理解。 在生活中,经常会遇到这样的一种情况,上班要出门的时候,突然找不到一件东西了,比如钥...

阿里云官方博客
16分钟前
1
0
计算机通信协议学习-Http

HTTP协议: 引用:http://www.cnblogs.com/ranyonsue/p/5984001.html HTTP简介 HTTP协议是Hyper Text Transfer Protocol(超文本传输协议)的缩写,是用于从万维网( WWW:World Wide Web)服务...

xiaoyaoyoufang
19分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部