点击进入我的博客
本章包含了Java编程思想第11章和17章的内容
我们需要在任意时刻和任意位置创建任意数量的对象，所以依靠创建需要命名的引用来持有对象已经满足不了需求。Java可以用数组和其他容器类来（List、Set、Queue、Map）来解决这个问题，不同的容器类有各自的特性，满足不同的需求。
1 范型和类型安全的容器
Java SE5之前是没有范型的，一个容器内（以List为例）可以放置任意的对象。
public class Test {
// 用@SuppressWarnings抑制编译器对“不受检查的异常”的警告
@SuppressWarnings("unchecked")
public static void main(String[] args) {
// (1)
List strList = new ArrayList() {
{
add("spider");
add(520);
}
};
// (2)
for (Object obj : strList) {
System.out.println(((String) obj).length());
}
}
}
没有范型的问题：
如上所示，(1)处的代码在编译和运行的时候都没有任何问题；但是当你在(2)处需要把Object类型强制转型成你需要的对象类型的时候，这个时候就会出现问题，因为Integer是无法转型成String类型的。
范型的好处
- 所以更安全的做法是，我们在创建一个容器的时候就明确它能存放的类型是什么
List<String> strList = new ArrayList<>();。 - 编译器将阻止我们放置其他类型的对象；
- 而且你在从容器中取出对象的时候，也不必在强制转型，因为
List知道你需要的对象类型是什么，它将会帮你自动转型。 - 我们可以将声明类型的子类放入该容器（即子类的向上转型）。
2 基本概念
2.1 容器类图
容器类图
Java容器类类库的用途是“保存对象”，从上述类图可以发现有两个顶层接口，并可以依次将容器划分为两个不同的概念。
-
Collection：一个独立元素的序列。所有Collection都可以用
foreach遍历。 - Map：一组成对的“键值对”对象，允许你使用键来查找值。
2.2 Java SE5中的新增容器
- Queue接口及其实现PriorityQueue和各种风格的BlockingQueue。
- ConcurrentMap接口及其实现ConcurrentHashMap，它们也是用于多线程机制的。
- CopyOnWriteArrayList和CopyOnWriteArraySet，它们也是用于多线程机制的。
- EnumSet和EnumMap，为使用enum而设计的Set和Map的特殊实现。
- Collections类中的多个便利方法。
3 容器填充元素
Arrays.asList()Collections.addAll()Collections.fill()Collections.nCopies()collection.addAll()-
Collection的构造器可以接受一个Collection来初始化
Collection<Integer> collection = new ArrayList<>(Arrays.asList(1, 2, 3));
collection.addAll(Arrays.asList(new Integer[]{1, 2, 3}));
Arrays.asList(new int[]{1, 2, 3});
Arrays.asList(1, 2, 3);
Collections.addAll(collection, new Integer[]{1, 2, 3});
Collections.addAll(collection, 1, 2, 3);
4 可选操作
执行各种不同的添加和移除的方法在Collection接口中都是可选操作，对于不支持的操作会抛出UnsupportedOperationException。
- Arrays.asList()返回的ArrayList不可以添加元素，此ArrayList和java.util.ArrayList不是同一个类。
- Collections.unmodifiableCollection()也会产生不可修改的列表
5 容器的打印
- 如果你要打印一个数组，需要用
Arrays.toString()方法，直接打印数组显示的是[I@61bbe9ba这种之前介绍过的格式。 - 容器由于重写了
toString()方法，所以可以直接打印出可读性强的结果。 - 由于不同
Collection或Map的子类元素放置的规则和顺序不同，所以向容器内添加相同的元素，打印的结果不一定相同。 -
HashMap提供了最快的查找技术，没有任何明显的顺序来保存其元素；TreeMap按照比较结果的升序保存键；LinkedHashMap按照插入顺序保存键，同时还保留了HashMap的查询速度。
6 List
List是一种可修改的序列，它允许在创建之后添加、移除元素，或者自我调整尺寸。
有两种基本的List：
- 基本的ArrayList，它擅长随机访问元素，但是在List的中间插入和删除元素时较慢
- LinkedList，它通过代价较低的方式在List中进行插入和删除操作，提供了优化的顺序访问；但是随机访问方面相对较慢。
6.1 LinkedList
如前所述，LinkedList也像ArrayList一样实现了基本的List接口，但是它执行插入和移除时比ArrayList要更高效，但是在随机访问操作方面要慢。
LinkedList还添加了可以使其用作栈、队列或双端队列的方法（是Queue的子类）。
LinkedList中的相同方法
- 正是由于LinkedList添加了栈和队列的方法，使得内部多了一些功能相同但名称不同（为了覆盖父类）的方法
- getFirst() == element() ≈ peek()：都是返回第一个元素，但是在空
List的时候处理不一样 - removeFirst() == remove() ≈ poll()：都是移除并返回列表的头，但是在空
List的时候处理不一样 - addFirst() == addLast()：都将某个元素插入队尾
7 迭代器
迭代器是一个对象，他的工作是遍历并选择序列中的对象，而程序员不必知道该序列的底层结构，即将遍历序列的操作和序列底层的结构分离。
迭代器通常被成为轻量级对象：创建它的代价很小。
Java的迭代器Iterator
- Java的迭代器只能向前移动
- 使用方法
iterator()要求容器返回一个Iterator，Iterator准备好返回序列的第一个元素 - 使用
next()获取序列中的下一个元素 - 使用
hasNext()检查序列中是否还有元素 - 使用
remove()将迭代器新近返回的元素删除
更强大的迭代器 ListIterator
- 它是
Iterator的子类型，只能用于List的访问。 - 它可以双向移动
- 它可以返回当前位置前一个元素和后一个元素的索引（即下标）
- 可使用时
set()方法替换访问过的最近的元素 - 可以使用
listIterator(int index)直接创建一个指向索引处的ListIterator
Collection和Iterator
Java中，实现Collection就必须提供iterator()方法，这有的时候会带来麻烦。
直接生成Iterator是将队列与消费队列的方法链接在一起耦合度最小的方式，并且与实现Collection相比，它在序列类上所施加的约束也少得多。
Foreach与迭代器
-
foreach可以用于数组和所有Collection对象，之所以能够工作，是因为Collection继承了Iterable接口。 - 数组不是
Iterable。 -
Iterable接口包含一个能够产生Iterator的iterator()方法，并且Iterable接口被foreach用来在序列中移动。换言之，任何实现了Iterable接口的类，都可以用与foreach语法。
适配器方法惯用法
如果需要多个foreach遍历一个类的方法，例如该类需要支持向前和向后遍历。这是只实现Iterable是不行的，可以编写其他返回类型为Iterable的方法来满足foreach语句。这就是编写适配器。
// 反向遍历部分代码
public class Test<E> extends ArrayList<E> {
public Test(Collection<? extends E> c) {
super(c);
}
public Iterable<E> reverse() {
return new Iterable<E>() {
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int index = size() - 1;
@Override
public boolean hasNext() {
return index >= 0;
}
@Override
public E next() {
return get(index--);
}
};
}
};
}
}
8 Stack 栈
栈是一种先进后出（Last In First Out，LIFO）的容器（数据结构）。
LinkedList能实现栈所有的功能。
主要方法
- peek()：返回栈顶元素
- pop()：返回并移除栈顶元素
- push()：元素入栈
- empty()：栈是否为空
9 Set 集合
Set不保存重复的元素。
Set与Collection有完全一样的接口（方法），因此没有任何额外的功能，实际上Set就是Collection只是行为不同（这就是继承和多态思想的典型应用：体现不同的行为）。
常用的几种Set
- HashSet：使用的是散列函数，这也是大多数使用场景的选择
- TreeSet：将元素存储在红-黑树数据结构中。TreeSet默认是按照字典序排序的；初始化TreeSet的时候可以设定排序的方式，如
String.CASE_INSENSITIVE_ORDER就是按照字母序排列；你也可以写一个你自己的比较器Comparator。 - LinkedHashSet：是HashSet的扩展，但是元素顺序是按照放插入顺序保存的。
SortedSet接口
- SortedSet中的元素可以保证处于排序状态。
- SortedSet的意思是——按照对象的比较函数对元素进行排序，而不是插入顺序。
10 Queue 队列
队列是一个典型的先进先出（First In First Out，FIFO）的容器。
队列通常被当作一种可靠的将对象从程序的一个区域传输到另一个区域的途径，尤其在并发编程中十分重要。
主要方法
-
offer()：将元素插入队尾。 -
add()：同offer()，但是当超出队列长度当时候抛出异常。 -
peek()：不移除的返回队头元素；为空时返回null。 -
element()：同peek()，为空时抛出NoSuchElementException。 -
poll()：移除并返回队头元素，为空时返回null。 -
remove()：同poll()，为空时抛出NoSuchElementException异常。
PriorityQueue
优先级队列：按照优先级的顺序维护的队列。
当你在PriorityQueue上调用offer()方法来插入一个对象时，这个对象会在队列中被排序。默认的排序将使用对象在队列中自然顺序，但是你可以通过提供自己的Comparator来修改这个顺序。PriorityQueue可以确保当你调用相关方法时，获取的元素将是队列中优先级最高的元素。
11 Map映射表
性能是映射表中的一个重要问题,当在get()中使用线性搜索时,执行速度回相当的慢,而这正是HashMap提高速度的地方。HashMap使用了特殊的值,称作散列码,来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值,它是通过将该对象的某些信息进行转换搜索而成的。
11.1 Map的实现
| Map子类 | 说明 |
|---|---|
| HashMap | Map基于散列表的实现(它取代了HashTable)。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子,以调整容器的性能。 |
| LinkedHashMap | 类似于HashMap，但是迭代遍历时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点；而在迭代访问时反映更快，因为它使用的链表维护内部次序。 |
| TreeMap | 基于红黑树的实现。查看“键”或“键值对”时，它们会被排序（次序由Comparable或者Comparator决定）。TreeMap特点在于所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。 |
| WeakHashMap | 弱键(weak key)映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾回收器回收。 |
| ConcurrentHashMap | 一种线程安全的Map，它不涉及同步加锁。 |
| IdentityHashMap | 使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题设计的。 |
11.2 各种Map性能比较
- 除了IdentityHashMap，所有Map实现的插入操作都会随着Map尺寸的变大而明显变慢。
- Hashtable的性能大体上与HashMap相当。
- TreeMap通常比HashMap要慢。
- LinkedHashMap插入时比HashMap慢一点。
11.3 HashMap实现原理
- 数组并不保存键本身，而是通过键对象生成一个数字（即计算散列码），将其作为数组的下标。
- 由于散列码计算可能会产生冲突，所以数组并不直接保存值，而是保存值的List。
- Java的散列函数都使用2的整数次方来作为散列表的理想容量。对现代的处理器来说，除法和求余是最慢的动作。使用2的整数次方的散列表，可用掩码代替除法。因为get()是使用最多的操作，求余数的%操作是其开销的大部分。
11.4 HashMap的性能因子
我们可以通过手工调整HashMap来提高其性能，从而满足我们特定应用的需求。为了在调整HashMap时能理解性能的问题，某些术语是必须要了解的：
- 容量：表中的桶位数
- 初始容量：表在创建时所拥有的桶位数。HashMap和HashSet都具有允许指定初始容量的构造器——默认为16
- 尺寸：表中当前存储的项数
- 负载因子：尺寸/容量。空表的负载因子为0，而半满表的负载因子为0.5，依次类推。负载轻的表产生的冲突可能性较小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap和HashSet都具有允许指定初始容量的构造器，当负载情况达到负载因子的水平时，容器将会自动增加容量，实现方式是容量大致加倍，并重新将现在对象分布到新的桶位中（这被称为再散列）。
HashMap使用的默认负载因子为0.75（只有当表达到四分之三满时，才会进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间，但是会增加查找代价，这很重要，因为查找是我们在大多数时间里所进行的操作（包括get和put）。如果您知道将要在HashMap中存储多少项，那么创建一个具有恰当大小的初始容量将可以避免自动再散列的开销。
11.5 WeakHashMap
- WeakHashMap用来保存WeakReference。它使得规范映射更易于使用，在这种映射中，每个值只保存一份实例以节省存储空间。当程序需要那个值的时候，便在映射中查询现有的对象，然后使用它。映射可将值做为其初始化的一部分，不过通常在需要的时候才生成值。
- 这是一种节约存储空间的技术，因为WeakHashMap允许垃圾回收器自动清理键和值，所以十分便。对于WeakHashMap添加键和值的操作，则没有什么特殊要求，映射会自动使用WeakReference包装他们。
12 散列与散列码
12.1 hashCode与equals
默认的hashCode和equals
Object.equals()方法比较的是对象的地址
Object.hashCode()方法默认是使用对象的地址计算散列码
12.2 equals方法的条件
- 自反性：对于任何非null的引用值x，
x.equals(x)=true - 对称性：对于任何非null的引用x、y，
x.equals(y)=true，那么y.equals(y)=true。 - 传递性：对于任何非null的引用x、y、z，如果
x.equals(y)=true、x.equals(z)=true那么y.equals(z)=true - 一致性：对于任何非null的引用x和y，只要equals的操作涉及的类信息没有改变，则x.equals(y)的结果一直不变。
- 对于任何为null的引用，
x.equals(null)=false。
12.3 hashCode方法的约定
- 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。
- 如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任一个对象的hashCode方法必须产生同样的整数结果。因此重写了equals方法必须重写hashCode方法。
- 如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。
12.4 覆盖hashCode注意事项
- 无论何时，同一个对象调用hashCode()都应该生成同样的值
- 不应该使hashCode()依赖于具有唯一性的对象信息，尤其是this的值。
- 散列码更应该关注生成速度，而不是唯一性
- hashCode的值的范围不重要，只要保证是int即可。
13 总结
- 数组将数字与对象联系起来。
- Collection保存单一的元素，而Map保存相关联的键值对。
- List也建立数字索引与对象的关联，List能够自动扩充容量。
- 如果要进行大量的随机访问，就使用ArrayList；如果要经常从表中间出入或删除元素，则应该使用LinkedList。
- 各种Queue以及栈的行为，由LinkedList提供支持。
- Map是一种将对象（而非数字）与对象相关联的设计。HashMap设计用来快速访问；而TreeMap保持“键”始终处于排序状态，所以没有HashMap快。LinkedHashMap保持元素插入的顺序，但是也通过散列提供了快速访问能力。
- Set不接受重复元素。HashSet提供最快的查询速度，而TreeSet保持元素处于排序状态，LinkedHashSet以插入顺序保存元素。
- 不要使用已过时的Vector、Hashtable和Stack。
网友评论