《Java编程思想》读书笔记（四）

《Java编程思想》读书笔记 —— 集合。

这部分只是还是挺重要的，面试题里面有好多。

第11章 持有对象

Java 容器类提供了完善的方法保存对象，并经其划分为 Collection 和 Map 两个不同的概念。

Collection 一个独立的元素序列；Map 一组成对的“键值对”对象。

Collection

1.Collection 一个独立的元素序列，这些元素服从一条或者多条规则。

List 必须按照插入的顺序保存元素，而 Set 不能有重复的元素。
Queue 按照排队规则来确定对象产生的顺序。

public class SimpleCollection {
  public static void main(String[] args) {
    Collection<Integer> c = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++)
      c.add(i); // Autoboxing
    for(Integer i : c)
      System.out.print(i + ", ");
  }
}
/* Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
*/

2.Arrays 和 Collections 类有很多实用的方法，可以在 Collection 中添加一组元素。

public class AddingGroups {
  public static void main(String[] args) {
    Collection<Integer> collection =
      new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
    Integer[] moreInts = { 6, 7, 8, 9, 10 };
    collection.addAll(Arrays.asList(moreInts));
    // Runs significantly faster, but you can't
    // construct a Collection this way:
    Collections.addAll(collection, 11, 12, 13, 14, 15);
    Collections.addAll(collection, moreInts);
    // Produces a list "backed by" an array:
    List<Integer> list = Arrays.asList(16, 17, 18, 19, 20);
    list.set(1, 99); // OK -- modify an element
    // list.add(21); // Runtime error because the
                     // underlying array cannot be resized.
  }
}

Arrays.asList() 接受一个数组或者可变参数列表，并将之转换为 List 对象。
需要注意的是，此种方式获得的 List 对象，由于底层实现仍然是数组，在添加或者删除元素时会出现 UnsupportedOperationException 异常。

Collections.addAll() 接收一个 Collection 对象、一个数组或者是可变参数列表作为参数，得到新的 Collection 对象。

3.容器的打印

public class PrintingContainers {
  static Collection fill(Collection<String> collection) {
    collection.add("rat");
    collection.add("cat");
    collection.add("dog");
    collection.add("dog");
    return collection;
  }
  static Map fill(Map<String,String> map) {
    map.put("rat", "Fuzzy");
    map.put("cat", "Rags");
    map.put("dog", "Bosco");
    map.put("dog", "Spot");
    return map;
  }	
  public static void main(String[] args) {
    print(fill(new ArrayList<String>()));
    print(fill(new LinkedList<String>()));
    print(fill(new HashSet<String>()));
    print(fill(new TreeSet<String>()));
    print(fill(new LinkedHashSet<String>()));
    print(fill(new HashMap<String,String>()));
    print(fill(new TreeMap<String,String>()));
    print(fill(new LinkedHashMap<String,String>()));
  }
}
/* Output:
[rat, cat, dog, dog]
[rat, cat, dog, dog]
[dog, cat, rat]
[cat, dog, rat]
[rat, cat, dog]
{dog=Spot, cat=Rags, rat=Fuzzy}
{cat=Rags, dog=Spot, rat=Fuzzy}
{rat=Fuzzy, cat=Rags, dog=Spot}
*/

Collection 打印出来的内容用 [ ] 括住，Map 打印出来的内容用 { } 括住。

List

List 接口在 Collection 基础上添加了大量的方法。可分为 ArrayList 和 LinkedList 两种。

ArrayList 数据结构采用的是线性表，优势是访问和查询十分方便，但添加和删除的时候效率很低。
LinkedList 数据结构采用的是链表，优势是删除和添加的效率很高，但随机访问元素时效率较 ArrayList 类低。

List 重要价值在于提供了一种可修改的序列。

contains(Object o) 确定某个对象是否在列表中。
remove(int index) 移除指定位置上的元素。
indexOf() 返回列表中首次出现指定元素的索引，如果不包含该元素，返回-1。

LikedList 增加了可以使其用作栈、队列或双端队列的方法。

public class Stack<T> {
    private LinkedList<T> storage = new LinkedList<>();
    public void push(T v){
        storage.addFirst(v);
    }
    public T peek(){
        return storage.getFirst();
    }
    public T pop(){
        return storage.removeFirst();
    }
    public boolean empty(){
        return storage.isEmpty();
    }
    public String toString(){
        return storage.toString();
    }
}

LikedList 具有直接实现栈（LIFO）的所有功能的方法。

addFirst(E e)/addLast(E e)：将元素添加到列表的开头/结尾
getFirst()/element()：返回列表的第一个元素
peek()/peekFirst()：获取但不移除列表的第一个元素
offer(E e)/offerLast(E e)：将元素插入到列表末尾

Queue

队列是典型的先进先出（FIFO）的容器。

public class QueueDemo {
    public static void printQ(Queue queue) {
  while(queue.peek() != null)
      System.out.print(queue.remove() + " ");
  System.out.println();
    }
    public static void main(String[] args) {
  Queue<Integer> queue = new LinkedList<Integer>();
  Random random = new Random(47);
  for(int i = 0; i < 10; i++)
      queue.offer(random.nextInt(i+10));
  printQ(queue);
  Queue<Character> qCharacters = new LinkedList<Character>();
  for(char c : "Brontosaurus".toCharArray())
      qCharacters.offer(c);
  printQ(qCharacters);
    }
}
/* Output:
 8 1 1 1 5 14 3 1 0 1
 B r o n t o s a u r u s
*/

LinkedList 提供了方法以支持队列的行为，并且它实现了 Queue 接口，
因此 LinkedList 可以用作 Queue 的一种实现，也可以将 LinkedList 向上转型为 Queue 。

PriorityQueue 优先级队列声明下一个弹出的元素是最需要的元素(具有最高的优先级)，可以确保当调用 peek()、poll() 和 remove() 方法时，获取的元素将是队列中优先级最高的元素。

PriorityQueue priorityQueue = new PriorityQueue<Integer>(
  inis.size(),Collections.reverseOrder()
);

Set

Set 具有与 Collection 完全一样的接口，实际上就是 Collection ，只是行为不同。

HashSet 数据结构采用的是散列表，主要是设计用来做高性能集运算的，例如对两个集合求交集、并集、差集等。
集合中包含一组不重复出现且无特性顺序的元素，其值是不可重复与无序的。

LinkedHashSet 的核心概念相对于 HashSet 来说就是一个可以保持顺序的Set集合。

TreeSet 数据结构使用的是红黑树，性能上低于HashSet，用于排序。

Map

Map：一组成对的“键值对”对象，允许使用键来查找值；
映射表允许我们使用另一个对象来查找某个对象，它被称为“关联数组”，因为它将某些对象与另外一些对象关联在了一起，或者被称为“字典”

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

get(Object o)：返回指定键所映射的值，如果不包含该键的映射关系，返回 null 。
put(K key, V value)：将指定的值与此映射中的指定键关联，如果已经存在映射关系，更新值。
hashCode()：返回此映射的哈希码值。

Map 的三种实现

HashMap：基于“拉链法”实现的散列表，一般用于单线程中，不是线程安全的。
HashTable：基于“拉链法”实现的散列表，一般用于多线程中，是线程安全的。
TreeMap：有序的散列表，通过红黑树实现的，一般用于单线程中存储有序的映射。

Iterator

迭代器，用于遍历容器，JDK源码如下：

package java.util;
import java.util.function.Consumer;
public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

Java 的 Iterator 只能单向移动：

public class SimpleIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.arrayList(12);
    Iterator<Pet> it = pets.iterator();
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
    // A simpler approach, when possible:
    for(Pet p : pets)
      System.out.print(p.id() + ":" + p + " ");
    System.out.println();	
    // An Iterator can also remove elements:
    it = pets.iterator();
    for(int i = 0; i < 6; i++) {
      it.next();
      it.remove();
    }
    System.out.println(pets);
  }
}
/* Output:
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
[Pug, Manx, Cymric, Rat, EgyptianMau, Hamster]
*/

Iterator() 要求容器返回一个Iterator。Iterator 准备好返回序列的第一个元素。
next() 获得序列中的下一个元素。
hasNext() 检查序列中是否还有元素。
remove() 将迭代器新近返回的元素删除。

ListIterator

ListIterator 是 Iterator 的一个子类，只能用于各种List的访问。
ListIterator 可以双向移动，可以产生当前位置的前一个和后一个元素的索引，并且可以使用 set() 方法，将最近访问过的元素进行替换。
此外，还可以通过 listIterator(int index) 的方法，获得一个一开始就指向 index 位置的 ListIterator。

Foreach 与迭代器

foreach 语法主要用于数组，同样可以用于 Collection 对象。

public class ForEachCollections {
  public static void main(String[] args) {
    Collection<String> cs = new LinkedList<String>();
    Collections.addAll(cs,
      "Take the long way home".split(" "));
    for(String s : cs)
      System.out.print("'" + s + "' ");
  }
}
/* Output:
'Take' 'the' 'long' 'way' 'home'
*/

因为 java SE5 引入了 Iterable 接口，该接口包含产生 Iterator 的 iterator 方法，
并且 Iterable 接口被 foreach 用来造序列中移动。

第17章 容器深入研究

现在还不太深入，后面再看。

参考资料
1、Java 容器知识整理 - FullStackDeveloper - SegmentFault
https://segmentfault.com/a/1190000002903035
2、Java编程思想读书笔记——持有对象 - CSDN博客
http://blog.csdn.net/baidu_21088863/article/details/78175347
3、Java编程思想第四版读书笔记——第十一章 持有对象 - CSDN博客
http://blog.csdn.net/severusyue/article/details/49491441
4、深入Java源码解析容器类List、Set、Map - 简书
http://www.jianshu.com/p/047e33fdefd2
5、《Java编程思想》读书笔记 第十一章 持有对象 02 Map
https://zhuanlan.zhihu.com/p/25816448