一般般帅
上一篇:无
容器类概述
2554 2017-09-11 2020-06-25
前言：面试中不可避免的会被问到Java容器类，这次从全局上过一遍，体会一下作者的设计思路以及了解一些需要注意的地方。
一、Java容器类图
网上大部分的类图都是来源于《Java编程思想》，这里借用一下网上的（这里有个错误，LinkIterator应为ListIterator），如下：
二、Collection接口
可以理解为一个独立元素的序列，我们抽取里面部分方法进行讲解：
| 方法 | 说明 |
|---|---|
| 比较常用的抽象方法（这些方法不做特别说明） | int size()、boolean isEmpty()、boolean contains(Object o)、boolean add(E e)、boolean remove(Object o)、void clear()、boolean equals(Object o) |
| Iterator iterator() | 这个方法表明只要是Java类库中的序列，或者说实现Collection接口的类（以下简称实现类）都可以通过xxx.iterator获得一个Iterator接口类型的迭代器 |
| Object[] toArray() | 这个方法表明实现类可以向数组转换 |
| 这个方法说明实现类可以向指定类型数组转换，形如toArray(new Integer(){1, 2}) | |
| int hashCode() | 这个方法说明实现类有哈希值 |
下面是一些测试代码
private static void testCollection() {
Collection<Integer> collection = Arrays.asList(1, 2, 3, 4);
Integer[] temp = collection.toArray(new Integer[collection.size()]);
Iterator<Integer> it = collection.iterator();
while (it.hasNext()) {
Integer i = it.next();
System.out.println(i + "(hashCode=" + i.hashCode() + ")");
}
// 此步会抛出UnsupportedOperationException
// collection.clear();
System.out.println(collection.size());
// 输出结果略
}
// 这个ArrayList并不是我们认为的那个ArrayList，他只是Arrays的一个静态内部类而已
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable {
// 注意并没有重写clear方法，其他略
}
// 下面是异常信息，不难看出结果了吧
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.AbstractList.remove(AbstractList.java:161)
at java.util.AbstractList$Itr.remove(AbstractList.java:374)
at java.util.AbstractList.removeRange(AbstractList.java:571)
at java.util.AbstractList.clear(AbstractList.java:234)
public E remove(int index) {
throw new UnsupportedOperationException();
}
1、List接口
List接口维护一个有序列表，在Collection的基础上添加了大量针对元素位置操作的方法。还是抽取部分，如下：
| 方法 | 说明 |
|---|---|
| 比较常用的抽象方法（这些方法不做特别说明） | E get(int index)、E set(int index, E element)、void add(int index, E element)、E remove(int index) |
| int indexOf(Object o) | 返回目标对象第一次出现的位置 |
| int lastIndexOf(Object o) | 返回目标最后一次出现的位置 |
| ListIterator listIterator() | 返回Iterator接口的一个实现类 |
| ListIterator listIterator(int index) | 返回Iterator接口的一个实现类 |
| List subList(int fromIndex, int toIndex) | 返回一个子列表 |
下面是一些测试代码
private static void testList() {
List<String> one = new LinkedList<>();
List<String> two = new ArrayList<>();
for (int i = 100000; i > 0; i--) {
one.add(String.valueOf(i));
two.add(String.valueOf(i));
}
long startTime = System.currentTimeMillis();
one.sort(null);
System.out.println("LinkedList排序耗时" + (System.currentTimeMillis() - startTime) + "ms");
two.sort(null);
System.out.println("ArrayList排序耗时" + (System.currentTimeMillis() - startTime) + "ms");
startTime = System.currentTimeMillis();
for(String s : one) {
System.out.print(s);
}
System.out.println("\nLinkedList遍历耗时" + (System.currentTimeMillis() - startTime) + "ms");
startTime = System.currentTimeMillis();
for(String s : one) {
System.out.print(s);
}
System.out.println("\nArrayList遍历耗时" + (System.currentTimeMillis() - startTime) + "ms");
}
// 部分结果如下
LinkedList排序耗时55ms
ArrayList排序耗时84ms
LinkedList遍历耗时248ms
ArrayList遍历耗时213ms
结合两者的具体实现，由上面的输出结果来看，LinkedList在添加、删除、插入方面速度快，而ArrayList遍历较快。其原因是LinkedList底层是链表，对节点的操作很方便，增删改很方便，而ArrayList底层是数组实现，物理位置连续，所以遍历较快。
2、Set接口
Set接口维护一个无序的列表，Collection接口中有19个方法，而Set接口中只有16个方法。这说明，大部分Collection中的操作就是Set接口中的操作了，理解为接口规范（注释需要）即可。
下面是一些测试代码
private static void testSet() {
Set<String> one = new HashSet<>();
Set<String> two = new LinkedHashSet<>();
for (int i = 0; i < 6; i++) {
one.add(String.valueOf(i * 31));
two.add(String.valueOf(i * 31));
}
for (String s : one) {
System.out.print(s + " ");
}
System.out.println();
for (String s : two) {
System.out.print(s + " ");
}
}
// 输出结果如下
0 155 124 93 62 31
0 31 62 93 124 155
其实HashSet和LinkedHashSet的区别就是HashMap和LinkedHashMap的区别，这个我们后面再讲。
3、Queue接口
队列维护一个先进先出的有序列表，它在Collection的基础上添加了自己的6个方法，而这6个方法又分为两部分，这里引用官方文档说明，如下：
| 方法 | 说明 |
|---|---|
| boolean add(E e) | 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException |
| boolean offer(E e) | 将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常 |
| E remove() | 获取并移除此队列的头 |
| E poll() | 获取并移除此队列的头，如果此队列为空，则返回 null |
| E element() | 获取，但是不移除此队列的头 |
| E peek() | 获取但不移除此队列的头；如果此队列为空，则返回 null |
下面是一些测试代码
private static void testQueue() {
Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new LinkedList<>();
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < 4; i++) {
queue.add(i);
deque.offer(i);
stack.push(i);
}
System.out.println(queue.poll());
System.out.println(deque.pollLast());
System.out.println(stack.pop());
}
// 输出结果0 3 3
值得注意的是有个双端队列接口Deque，这个到LinkedList再讲。
4、AbstractCollection
Collection有AbstractCollection，List有AbstractList，Set有AbstractSet，Map有AbstractMap，它们都是对接口一种半实现，留下一些抽象方法由子类重写以完成子类独有的特征。以AbstractCollection为例
public abstract class AbstractCollection<E> implements Collection<E> {
protected AbstractCollection() {
}
public abstract Iterator<E> iterator();
public abstract int size();
public boolean isEmpty() {
return size() == 0;
}
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // fewer elements than expected
if (a == r) {
r[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
// more elements than expected
return it.hasNext() ? finishToArray(r, it) : r;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// 其他略
}
下面是一些测试代码
private static void testAbstractCollection() {
List<String> one = new ArrayList<>();
List<String> two = new ArrayList<>();
for (int i = 0; i < 10; i++) {
one.add(String.valueOf(i));
two.add(String.valueOf(i));
}
String[] str1 = (String[]) one.toArray();
String[] str2 = two.toArray(new String[two.size()]);
for (String t : str1) {
}
for (String t : str2) {
}
}
// 直接运行是会抛出异常的，信息如下
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
at site.xiaokui.common.hk.blog.CollectionTest.testAbstractCollection(CollectionTest.java:22)
at site.xiaokui.common.hk.blog.CollectionTest.main(CollectionTest.java:12)
// 强制转换只能针对单个对象，对于数组还是要一个一个转过来，推荐使用第二种
三、Map接口
可以理解为一组键值对对象，Map接口是同Collection接口一样，处于最顶层。代码确实不少，我们抽取部分方法来看下：
| 方法 | 说明 |
|---|---|
| 比较常用的抽象方法（这些方法不做特别说明） | int size()、boolean isEmpty()、boolean containsKey(Object key)、boolean containsValue(Object value)、V get(Object key)、V put(K key, V value)、V remove(Object key) |
| Set keySet() | 返回一个键Set |
| Collection values() | 返回一个值Collection |
| Set<Map.Entry<K, V>> entrySet() | 返回内部接口Entry中的一个Set集合 |
| 其他 | 剩下的大部分是default方法，暂时不管 |
对于Map可以展开的有太多太多，这一部分我们留到后面再继续。
四、具体子类的实现
上面提到的都是些顶级接口或抽象类，没有具体的实现，这里我们看一下具体的子类实现。列表如下（自底向上，从左往右）：
| 类名 | 说明 |
|---|---|
| Stack | 栈是Vector的一个子类，它实现了一个标准的后进先出的栈 |
| Vector | 该类和ArrayList非常相似，但是该类是同步的，可以用在多线程的情况，该类允许设置默认的增长长度，默认扩容方式为原来的2倍 |
| ArrayList | 该类也是实现了List的接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。该类也是非同步的,在多线程的情况下不要使用。ArrayList 增长当前长度的50%，插入删除效率低 |
| LinkedList | 该类实现了List接口，允许有null（空）元素。主要用于创建链表数据结构，该类没有同步方法，如果多个线程同时访问一个List，则必须自己实现访问同步，解决方法就是在创建List时候构造一个同步的List |
| LinkedHashSet | 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现 |
| HashSet | 该类实现了Set接口，不允许出现重复元素，不保证集合中元素的顺序，允许包含值为null的元素，但最多只能一个 |
| TreeSet | 该类实现了Set接口，可以实现排序等功能 |
| SortedSet | 继承于Set保存有序的集合 |
| WeakHashMap | 继承AbstractMap类，使用弱密钥的哈希表 |
| LinkedHashMap | 继承于HashMap，使用元素的自然顺序对元素进行排序 |
| HashMap | HashMap 是一个散列表，它存储的内容是键值对(key-value)映射 |
| TreeMap | 继承了AbstractMap，并且使用一颗树 |
| SortedMap | 继承于Map，使Key保持在升序排列 |
具体的分析将在后面的篇章进行讲解。
总访问次数: 314次, 一般般帅 创建于 2017-09-11, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！