java容器簡(jiǎn)圖

image

對(duì)象引用保存

1. 數(shù)組

• 編譯器支持類型
• 保存一組對(duì)象最有效的方式
• 保存基本類型數(shù)據(jù)時(shí)推薦使用
• 大小固定，不知道需要多少對(duì)象時(shí)受限

2. 容器

   用于解決在任意時(shí)刻，任意位置，創(chuàng)建任意數(shù)量的對(duì)象的問(wèn)題。

容器基本概念

java容器類庫(kù)的用途是“保存對(duì)象”，并將其分為兩個(gè)不同的概念

1. Collection: 一個(gè)獨(dú)立元素序列，這些元素都服從一條或多條規(guī)則
   • List：必須按照插入順序保存元素
   • Set：不能有重復(fù)元素
   • Queue：按照隊(duì)列規(guī)則來(lái)確定對(duì)象產(chǎn)生的順序（通常與他們的插入順序相同）
2. Map：一組成對(duì)的“鍵值對(duì)”對(duì)象，允許你使用鍵來(lái)查找值

Collection

public interface Collection<E> extends Iterable<E> {
    // Query Operations
  
    int size();
  
    boolean isEmpty();
  
    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    // Modification Operations

    boolean add(E e);

    boolean remove(Object o);

    // Bulk Operations

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);

    void clear();

    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();
}

使用方法

創(chuàng)建容器

1. 聲明接口，創(chuàng)建實(shí)現(xiàn)，修改時(shí)僅修改創(chuàng)建位置即可

List<Apple> apples = new ArrayList<>();

2. 聲明和創(chuàng)建具體實(shí)現(xiàn)（需要具體實(shí)現(xiàn)中額外的功能）

ArrayList<Apple> apples = new ArrayList<>();

添加元素

單個(gè)元素

import java.util.ArrayList;
import java.util.Collection;

public class SimpleCollection {

    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            // autoboxing
            c.add(i);
        }
        for (Integer i : c) {
            System.out.print(i + ", ");
        }
    }

}

Set: 元素不存在時(shí)才添加

List：將對(duì)象放入容器，不關(guān)注是否重復(fù)

一組元素

import java.util.*;

public class AddGroups {

    public static void main(String[] args) {
        Collection<Integer> collection = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        Integer[] moreInts = {6, 7, 8, 9, 10};
        collection.addAll(Arrays.asList(moreInts));
        // runs significantly faster, buy you can`t
        // construct a Collect 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);
        // Ok -- modify an element
        list.set(1, 99);
        // Runtime error because the underlying array cannot be resized
        list.add(21);
    }


}

• 注意collection.addAll()與Collections.addAll()的區(qū)別
• 注意可選參數(shù)
• 注意不可變數(shù)組

容器打印

import java.util.*;


public class PrintContainers {

    /**
     * fill collection
     *
     * @param collection collection wait to fill
     * @return
     */
    static Collection<String> fill(Collection<String> collection) {
        collection.add("rat");
        collection.add("cat");
        collection.add("dog");
        collection.add("dog");
        return collection;
    }

    /**
     * fill map
     *
     * @param map map wait to fill
     * @return
     */
    static Map<String, String> 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) {
        System.out.println(fill(new ArrayList<String>()));
        System.out.println(fill(new LinkedList<String>()));
        System.out.println(fill(new HashSet<String>()));
        System.out.println(fill(new TreeSet<String>()));
        System.out.println(fill(new LinkedHashSet<String>()));
        System.out.println(fill(new HashMap<String, String>()));
        System.out.println(fill(new TreeMap<String, String>()));
        System.out.println(fill(new LinkedHashMap<String, String>()));
    }
}

• 默認(rèn)調(diào)用容器的toString()方法即可生成可讀性很好的結(jié)果

List

承諾將元素維護(hù)在特定的序列中；

添加方法以實(shí)現(xiàn)在list的中間插入、移除元素。

public interface List<E> extends Collection<E> {
    // Query Operations
  
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    // Modification Operations

    boolean add(E e);

    boolean remove(Object o);

    // Bulk Modification Operations

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean addAll(int index, Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);

    void clear();

    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();

    // Positional Access Operations

    E get(int index);

    E set(int index, E element);

    void add(int index, E element);

    E remove(int index);

    // Search Operations

    int indexOf(Object o);

    int lastIndexOf(Object o);

    // List Iterators

    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);

    // View

    List<E> subList(int fromIndex, int toIndex);
}

ArrayList

基于數(shù)組,下標(biāo)隨機(jī)訪問(wèn)元素快，插入、移除元素慢（數(shù)據(jù)的連續(xù)性）

LinkedList

• List中間插入和移除是高效
• 下標(biāo)隨機(jī)訪問(wèn)較低
• 支持棧、隊(duì)列、雙端隊(duì)列的方法

迭代器

面對(duì)具體的容器編寫的代碼，并不能很好的用于另外一種容器，我們需要更高層次的抽象，迭代器能能夠幫助我們達(dá)成目的。

迭代器是一個(gè)對(duì)象，他的工作是遍歷并選擇序列中的對(duì)象，而客戶端程序員不必關(guān)心序列底層的結(jié)構(gòu)。統(tǒng)一了對(duì)容器的訪問(wèn)方式。

public interface Iterable<T> {

    /**
     * Returns an iterator over a set of elements of type T.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
}

public interface Iterator<E> {
    
    boolean hasNext();

    E next();

    void remove();
}

ListIterator

ListIterator是一個(gè)更加強(qiáng)大的Iterator子類型，它只能用于各種List的訪問(wèn)，

public interface ListIterator<E> extends Iterator<E> {
   
    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void remove();

    void set(E e);

    void add(E e);
}

Stack

后進(jìn)先出容器（LIFO)

public interface Stack<E>{

    E push(E item)；

    E pop()；

    E peek()；

    boolean empty()；

}

LinkedList已經(jīng)實(shí)現(xiàn)棧相關(guān)功能，我們可以使用組合的方式,完成自定義Stack，屏蔽LinkedList中的其他方法；

public class Stack<E> {
  
  private LinkedList storate = new LinkedList<E>();
  
  public E push(E e) {
    return storate.addFirst(v);
  }
  
  pulic E pop() {
    return storate.removeFirst();
  }
  
  public E peek() {
    return return storate.getFirst();
  }
  
  public boolean empty() {
    return storage.empty();
  }
  
}

Set

不保存重復(fù)的元素

public interface Set<E> extends Collection<E> {
    // Query Operations
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);

    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean retainAll(Collection<?> c);

    boolean removeAll(Collection<?> c);

    void clear();


    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();
}

• Set具有和Collection完全一樣的接口，因此沒(méi)有任何額外的功能
• Set就是Collection，只是行為不同（繼承與多態(tài)的典型應(yīng)用）
• Set基于對(duì)象的值來(lái)確定歸屬性

HashSet

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class SetOfInteger {

    public static void main(String[] args) {
        Random random = new Random(47);
        Set<Integer> integerSet = new HashSet<>();
        for (int i = 0; i < 10000; i++) {
            integerSet.add(random.nextInt(30));
        }
        System.out.println(integerSet);
    }

}

• 注意打印結(jié)果，無(wú)重復(fù)
• 輸出順序無(wú)規(guī)律

使用散列函數(shù),HashMap

TreeSet

將元素存儲(chǔ)在紅黑樹(shù)中,TreeMap

LinkedHashSet

同樣適用了散列函數(shù),HashMap，但使用了鏈表來(lái)維護(hù)元素的插入順序

使用場(chǎng)景

優(yōu)先使用HashSet,需要對(duì)結(jié)果排序可以考慮使用TreeSet

Map

將對(duì)象映射到其他對(duì)象的能力是解決編程問(wèn)題的殺手锏。

public interface Map<K,V> {

    // Query Operations
    int size();

    boolean isEmpty();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    // Modification Operations

    V put(K key, V value);

    V remove(Object key);

    // Bulk Operations

    void putAll(Map<? extends K, ? extends V> m);

    void clear();

    // Views

    Set<K> keySet();

    Collection<V> values();

    Set<Map.Entry<K, V>> entrySet();

    interface Entry<K,V> {

        K getKey();

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();
    }

    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();

}

用于統(tǒng)計(jì)

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Statistics {

    public static void main(String[] args) {
        Random rand = new Random(47);
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < 10000; i++) {
            // Produce a number between 0 and 20
            int r = rand.nextInt(20);
            Integer freq = m.get(r);
            freq = freq == null ? 1 : freq + 1;
            m.put(r, freq);
        }
        System.out.println(m);
    }

}

Queue

典型的先進(jìn)先出容器，從容器的一端放入，從另一端取出，并且放入容器的順序與取出順序一致。

public interface Queue<E> extends Collection<E> {
     /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);
    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);
    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();
    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();
      /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();
       /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

• 注意add()與offer()

• 注意remove()與poll()

• 注意element()與peek()

• LinkedList提供了與Queue相關(guān)的方法，對(duì)于queue繼承的Collection,在不需要其他任何方法的情況下，就可以擁有一個(gè)可用的Queue

PriorityQueue

先進(jìn)先出描述了最典型的隊(duì)列規(guī)則，隊(duì)列規(guī)則是指在給定一組隊(duì)列中元素的情況下，確定下一個(gè)彈出隊(duì)列元素的規(guī)則。

先進(jìn)先出聲明的是下一個(gè)元素應(yīng)該是等待時(shí)間最長(zhǎng)的元素；

優(yōu)先級(jí)隊(duì)列聲明下一個(gè)彈出元素是最高優(yōu)先級(jí)的元素；

默認(rèn)順序?qū)⑹褂脤?duì)象的自然順序，但是你可以使用自己的Comparator來(lái)修改這個(gè)順序;

PriorityQueue可以確保你調(diào)用peak()、poll()、和remove()方法時(shí)，獲取到的元素是隊(duì)列中優(yōu)先級(jí)最高的元素

使用案例

import java.util.*;

public class PriorityQueueDemo {

    public static <E> void printQ(Queue<E> queue) {
        while (queue.peek() != null) {
            System.out.print(queue.remove() + " ");
        }
        System.out.println();

    }

    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        Random random = new Random(47);
        for (int i = 0; i < 10; i++) {
            priorityQueue.offer(random.nextInt(i + 10));
        }
        printQ(priorityQueue);

        List<Integer> ints = Arrays.asList(25, 22, 20, 10, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);
        priorityQueue = new PriorityQueue<>(ints);
        printQ(priorityQueue);

        priorityQueue = new PriorityQueue<>(ints.size(), Collections.reverseOrder());
        priorityQueue.addAll(ints);
        printQ(priorityQueue);

        String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
        List<String> strings = Arrays.asList(fact.split(""));
        PriorityQueue<String> stringPriorityQueue = new PriorityQueue<>(strings);
        printQ(stringPriorityQueue);

        stringPriorityQueue = new PriorityQueue<>(strings.size(), Collections.reverseOrder());
        stringPriorityQueue.addAll(strings);
        printQ(stringPriorityQueue);

    }

}

Collection和Iterator

Collection是描述所有序列容器共性的根接口

java.util.AbstractCollection類提供了Collection的默認(rèn)實(shí)現(xiàn)，其中沒(méi)有不必要的代碼重復(fù)

實(shí)現(xiàn)Collection接口就意味著需要提供iterator()方法

iterable比iterator()方法要方便，可以使用foreach結(jié)構(gòu)，從而使代碼更加清晰

實(shí)現(xiàn)遍歷的方式

• 實(shí)現(xiàn)Collection接口 -> 強(qiáng)制去實(shí)現(xiàn)遍歷用不到的collection相關(guān)方法
• 繼承AbstractCollection抽象類 -> 已經(jīng)繼承其他類時(shí)不能再繼承
• 生成Iterator -> 將隊(duì)列與消費(fèi)隊(duì)列的方法連接在一起的耦合度最小的方式與實(shí)現(xiàn)collection相比，在序列類上添加的約束也少得多

Foreach與迭代器

foreach語(yǔ)法主要用于集合與數(shù)組

Collection與foreach

編譯時(shí)利用Iterable的iterator()方法產(chǎn)生一個(gè)iterator,用于集合的迭代遍歷

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
}

public interface Collection<E> extends Iterable<E> {
    
    Iterator<E> iterator();

}

測(cè)試代碼

import java.util.Arrays;
import java.util.Collection;

public class CollectionForEachTest {

    public static void main(String[] args) {
        Collection<Integer> collections = Arrays.asList(1, 2, 3, 4);
        for (Integer i : collections) {
            System.out.println(i);
        }
    }

}

編譯后測(cè)試代碼

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

public class CollectionForEachTest {
    public CollectionForEachTest() {
    }

    public static void main(String[] args) {
        Collection<Integer> collections = Arrays.asList(1, 2, 3, 4);
        Iterator var2 = collections.iterator();

        while(var2.hasNext()) {
            Integer i = (Integer)var2.next();
            System.out.println(i);
        }

    }
}

數(shù)組與foreach

編譯時(shí)利用簡(jiǎn)單for循環(huán)和下標(biāo)自增的方法實(shí)現(xiàn)數(shù)組遍歷

測(cè)試代碼

public class ArrayForEachTest {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        for (Integer i : arr) {
            System.out.println(i);
        }
    }

}

編譯后測(cè)試代碼

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

public class ArrayForEachTest {
    public ArrayForEachTest() {
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int[] var2 = arr;
        int var3 = arr.length;

        for(int var4 = 0; var4 < var3; ++var4) {
            Integer i = var2[var4];
            System.out.println(i);
        }

    }
}

Iterable接口適配

適配foreach所需的Iterable接口，從而實(shí)現(xiàn)多種foreach遍歷順序

import java.util.*;

public class ReversibleArrayList<T> extends ArrayList<T> {

    public ReversibleArrayList(Collection<T> c) {
        super(c);
    }

    public Iterable<T> reversed() {

        return new Iterable<T>() {
            @Override
            public Iterator<T> iterator() {
                return new Iterator<T>() {
                    int current = size() - 1;

                    @Override
                    public boolean hasNext() {
                        return current > -1;
                    }

                    @Override
                    public T next() {
                        return get(current--);
                    }
                };
            }
        };

    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6);
        ReversibleArrayList<Integer> reversibleArrayList = new ReversibleArrayList<>(list);
        for (Integer i : reversibleArrayList) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (Integer i : reversibleArrayList.reversed()) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

}

總結(jié)

Java提供了大量持有對(duì)象的方式：

1. 數(shù)組將數(shù)字與對(duì)象聯(lián)系起來(lái)。它保存類型明確的對(duì)象，查詢對(duì)象時(shí)，不需要對(duì)結(jié)果做類型轉(zhuǎn)換。它可以是多維的，可以保存基本類型型的數(shù)據(jù)。但是，數(shù)組一旦生成，其容量就不能改變。
2. Collection保存單一的元素，而Map保存相關(guān)聯(lián)的鍵值對(duì)。有了java的泛型，你就可以知道容器存放的對(duì)象類型，因此你就不會(huì)將錯(cuò)誤類型的對(duì)象放置到容器中，并且在容器中獲取元素時(shí)，不必進(jìn)行類型轉(zhuǎn)換。各種類型的Collection和各種Map都可以在你向其中田間更多的元素時(shí)，自動(dòng)調(diào)整其尺寸。容器不能持有基本類型，但是自動(dòng)包裝機(jī)制會(huì)仔細(xì)地執(zhí)行基本類型到容器中所持有的包裝器類型之間雙向轉(zhuǎn)換。
3. 像數(shù)組一樣，List也建立數(shù)字索引與對(duì)象的關(guān)聯(lián)，因此，數(shù)組和List都是排好序的容器，List能夠自動(dòng)擴(kuò)容。
4. 如果要進(jìn)行大量的隨機(jī)訪問(wèn)，就使用ArrayList；如果要經(jīng)常從表中間插入或刪除元素，則應(yīng)該使用LinkedList.
5. 各種Queue和Stack的行為，由LinkedList支持。
6. Map是一種將對(duì)象（而非數(shù)字）與對(duì)象相關(guān)聯(lián)的設(shè)計(jì)。Hashmap設(shè)計(jì)用來(lái)快速訪問(wèn)；而TreeMap保持"鍵"始終處于排序狀態(tài)，所以沒(méi)有HashMap快。LinkedHash保持元素的插入順序，但也通過(guò)散列提供了快速訪問(wèn)的能力。
7. Set不接受重復(fù)元素。HashSet提供最快的查詢速度，而TreeSet保持元素處于排序狀態(tài)。LinedHashSet以插入順序保存元素。
8. 新程序不應(yīng)該使用過(guò)時(shí)的Vector、Hashtable、Stack.