Java集合框架
集合的接口与实现
当在程序中使用队列时，一旦构建了集合就不需要知道究竟使用了哪种实现。因此， 只 有在构建集合对象时，使用具体的类才有意义。可以使用接口类型存放集合的引用。
public class CircularArrayQueue<E> implements Queue<E>{
...;
}
public class LinkedListQueue<E> implements Queue<E>{
...;
}
//将实现与接口分离
Queue<Customer> expresslane = new CircularArrayQueue<>(100);
expressLane.add(new Customer("Harry"));
Queue<Custoaer> expressLane = new LinkedListQueueo<>( );
/*选择另外一种实现，只需要修改成另一个构造器即可*/
expressLane.add(new Custonier("Harry"));实现自己的队列类
两种方法：
实现Queue接口
扩展AbstractQueue抽象类
class Px<T> extends AbstractQueue<T>{ @Override public boolean offer(T e) { // TODO Auto-generated method stub return false; } @Override public T poll() { // TODO Auto-generated method stub return null; } @Override public T peek() { // TODO Auto-generated method stub return null; } @Override public Iterator<T> iterator() { // TODO Auto-generated method stub return null; } @Override public int size() { // TODO Auto-generated method stub return 0; } } //可见，扩展AbstractQueue类时，需要覆盖的方法较少
迭代器
应该将 Java 迭代器认为是位于两个元素之间。 当调用 next 时，迭代器就越过下 一个元素，并返回刚刚越过的那个元素的引用。
import java.util.ArrayList;
import java.util.Iterator;
public class Hello {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> s = new ArrayList<>();
s.add("hello");
s.add("world");
s.add("你好");
Iterator<String> it = s.iterator();
while (it.hasNext()) {
System.out.println(it.next());
// will print hello\n world\n 你好\n
}
for (String str : s) {// “ for each” 循环可以与任何实现了 Iterable 接口的对象一起工作
System.out.println(str);
// will print hello\n world\n 你好\n
}
try {
it = s.iterator();
it.remove();// 会出现异常
} catch (IllegalStateException e) {
e.printStackTrace();
}
try {
it = s.iterator();
it.next();
it.remove();// 不会出现异常
} catch (IllegalStateException e) {
e.printStackTrace();
}
System.out.println("OK");
// will print OK
/*Iterator 接口的 remove 方法将会删除上次调用 next 方法时返回的元素。在大多数情况
下，在决定删除某个元素之前应该先看一下这个元素是很具有实际意义的。然而， 如果想要
删除指定位置上的元素， 仍然需要越过这个元素。所以得先调用next()*/
}
}定义一个实现iterator的类
class Px<T> implements Iterator<T>{
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public T next() {
// TODO Auto-generated method stub
return null;
}
}覆盖原来的迭代器方法
class Px<T> implements Iterable<T> {
@Override
public Iterator<T> iterator() {
// TODO Auto-generated method stub
return null;
}
}泛型实用方法
可以使用抽象类来间接实现接口中的一部分方法。比如说，，Java 类库提供了一个类 AbstractCollection， 它将Collection接口中的基础方法 size 和 iterator 抽象化了，通过拓展这个抽象类，仅需要在具体类中提供这两个方法就可以了；而不是简单地实现Collection接口，并把接口中的所有方法都实现一遍。
interface A {
public void a();
public void b();
public void c();
}
abstract class B implements A {
public abstract void a();
public void b() {
}
public void c() {
}
}
class C extends B {
public void a() {
}
//在C类这里，只实现了接口A中的a方法
}具体的集合
链表
add方法
链表里的add方法是ListIterator接口里的，与 Collection.add 不同， 这个方法不返回 boolean 类型的值， 它假定添加操作总会改变链表。
interface ListIterator<E> extends Iterator<E>
{
void add(E element);//Add 方法在迭代器位置之前添加一个新对象
E next();
E previous();
boolean hasnext();
boolean hasPrevious();//与 next 方法一样，previous 方法返回越过的对象。
void set(E);//set 方法用一个新元素取代调用 next 或 previous 方法返回的上一个元素
}注意：如果迭代 器发现它的集合被另一个迭代器修改了， 或是被该集合自身的方法修改了， 就会抛出一个 ConcurrentModificationException 异常。
所以，为了避免发生并发修改的异常，请遵循下述简单规则：可以根据需要给容器附加许多的 迭代器，但是这些迭代器只能读取列表。另外，再单独附加一个既能读又能写的迭代器。
数组列表
ArrayList 类
这个类也实现了 List 接口。ArrayList 封 装了一个动态再分配的对象数组。可以通过get和set随机地访问每个元素。
注意：Vector 类的所有方法都是同步的。 可 以由两个线程安全地访问一个 Vector 对象。
但是， 如果由一个线程访问 Vector, 代码要 在同步操作上耗费大量的时间。
而 ArrayList 方法不是同步的， 因此，建议在不需要同步时使用 ArrayList, 而不要使用 Vector。
散列集
HashSet类
可以用 add 方法添加 元素。contains方法已经被重新定义，用来快速地查看是否某个元素已经出现在集中。它只 在某个桶中査找元素，而不必查看集合中的所有元素。由于散列将元素分散在表的各个位置上，所以访问 它们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用 HashSet。
树集
TreeSet类（使用了红黑树）
TreeSet 类与散列集十分类似，不过，它比散列集有所改进。树集是一个有序集合 ( sorted collection) 。可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值 自动地按照排序后的顺序呈现。
SortedSet<String> sorter = new TreeSet<>(); // TreeSet implements SortedSet
sorter.add("Bob");
sorter.add("Aniy");
sorter.add("Carl");
for (String s : sorter) System.println(s);
//will print Aniy Bob Carl队列与双端队列
在 Java SE 6中引人了 Deque 接口， 并由 ArrayDeque 和 LinkedList 类实现，可以让人们有效地在头部和尾部同时添加或删除元素，而且可以设定容量。
优先队列
优先级队列（priority queue) 中的元素可以按照任意的顺序插人，却总是按照排序的顺序 进行检索。也就是说，无论何时调用 remove 方法，总会获得当前优先级队列中最小的元素。
映射
Java提供了两个通用的映射实现：HashMap和TreeMap。它们都实现了Map接口。
HashMap对键进行散列，而TreeMap利用键的整体顺序对键进行排序。所以，如果不需要对键排列，用HashMap就可以了。
基本映射操作
要想检索一个对象，必须通过一个键。
String id = "987-98-9996";
e = staff.get(id);// gets harry如果映射中不存在那个键，则返回null。
可以自己给映射设定一个不存在的键，这样就不用返回null了。
Map<String, Integer> scores = . . .;
int score = scores.get(id, 0); // Gets 0 if the id is not present键必须是唯一的。不能对同一个键存放两个值。如果对同一个键两次调用 put 方法， 第二个值就会取代第一个值。实际上，put 将返回用这个键参数存储的上一个值。
public class Hello {
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> p = new HashMap<>();
p.put("hello", 1);
p.put("world", 2);
p.put("hh", 3);
Integer pre = p.put("hh", 4);// "hh"这个键的值被更新为4
System.out.println(pre);//will print 3,这是这个键上一的值
//用lambda表达式遍历映射
p.forEach((k, v) -> System.out.println("key: " + k + " vlaue: " + v));
/*will print key: hh vlaue: 4
key: world vlaue: 2
key: hello vlaue: 1
*/
}
}更新映射项
处理映射时的一个难点就是更新映射项。正常情况下，可以得到与一个键关联的原值， 完成更新， 再放回更新后的值。
但也有一些特殊情况，比如说要统计一个单词在文本中出现的次数
counts.put(word, counts.get(word) + 1);这貌似是可行的，但是当第一次遇到word键时，get就会返回null，就会出现异常。
作为一个简单的补救， 可以使用 getOrDefault 方法：
counts.put(word, counts.getOrDefault(word, 0) + 1);还可以调用putIfAbsent方法：
counts.putlfAbsent(word, 0);//word不存在时才会放入0
counts.put(word, counts.get(word)+ 1); 用merge方法可以做得更好：
counts.merge(word, 1, Integer::sum);
//如果键不存在，那这个键会与1关联，否则和sum与1的和进行关联映射视图
键集
Set<String> keys = map.keySet();//获取键集
for (String key : keys)
{
do something with key;
}值集
Collection<Integer> values = map.values();//获取键集
for (Integer value : values)
{
do something with value;
}键值对集
for (Map.Entry<String, Employee> entry : staff.entrySet())
{
String k = entry.getKey()；
Employee v = entry.getValue();
do something with k, v;
}还有更高效的方法：
counts.forEach((k，v) -> {
do somethingwith k, v
})；如果在键集视图上调用迭代器的 remove方法， 实际上会从映射中删除这个键和与它关联的值。不过，不能向键集视图增加元素，键值对集也有一样的限制。
算法
排序与混排
排序
List<String> staff = new LinkedList<>();
fill collection;
Collections.sort(staff);逆序
staff.sort(Comparator.reverseOrder());
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed())；重写Comparetor
Arrays.sort(int[] a, Comparator<Integer>() {
public int compare(int a, int b){
return a - b; 升序
// return b - a; 降序
/* a-b>0 交换ab位置，反之不变， 即返回值为正数时，交换数组中正在比较
的两个元素的位置，返回值为负数时，不交换。 记住第一个参数去比较第二个
参数就是升序，第二个参数比较第一个参数就是降序就OK了。
*/
}
})
//Collections同理混排
ArrayList<Card> cards = . . .;
Collections.shuffle(cards);只有当列表是可修改的，才可以执行排序算法（即当列表支持set方法）。
二分查找
i = Collections.binarySearch(c, element);
i = Collections.binarySearch(c, element, comparator);//自定义比较方法注：当没有找到匹配的元素时，将会返回一个负值i，此时可以利用这个负值(-i - 1)将元素插入到合适的位置，来保证列表的有序性。
if (i < 0)
c.add(-i - 1, element);批操作
colll.removeAll(coll2);//将从 coll1中删除co112中出现的所有元素
colli.retainAll(coll2);//从 coll1中删除所有未在 co112中出现的元素集合与数组的转换
public class Hello {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> p = new ArrayList<>();
p.add("hello");
p.add("world");
p.add("hh");
Object s[] = p.toArray();// toArray返回一个Object数组
for (Object str : s)
System.out.println(str);
String[] m = p.toArray(new String[0]);
/*
* 提供一个所需类型而且长度为 0 的数组。 这样一来返回的数组就会创建为相同的数组类型
*/
for (String str : m)
System.out.println(str);
String[] t = p.toArray(new String[p.size()]);
// 优化的做法提供具体大小的情况下，不会创建新数组
//因为当提供的数组大小不够时，会抛弃原数组，创建新数组
for (String str : t)
System.out.println(str);
}
}
