java容器簡圖

image

對象引用保存

1. 數(shù)組

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

2. 容器

   用于解決在任意時刻，任意位置络拌，創(chuàng)建任意數(shù)量的對象的問題俭驮。

容器基本概念

java容器類庫的用途是“保存對象”，并將其分為兩個不同的概念

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

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)萍恕，修改時僅修改創(chuàng)建位置即可

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

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

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

添加元素

單個元素

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: 元素不存在時才添加

List：將對象放入容器逸嘀，不關(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ī)訪問元素快翼岁，插入、移除元素慢（數(shù)據(jù)的連續(xù)性）

LinkedList

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

迭代器

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

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

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是一個更加強(qiáng)大的Iterator子類型晃跺，它只能用于各種List的訪問，

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完全一樣的接口二打，因此沒有任何額外的功能
• Set就是Collection，只是行為不同（繼承與多態(tài)的典型應(yīng)用）
• Set基于對象的值來確定歸屬性

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é)果掂榔，無重復(fù)
• 輸出順序無規(guī)律

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

TreeSet

將元素存儲在紅黑樹中,TreeMap

LinkedHashSet

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

使用場景

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

Map

將對象映射到其他對象的能力是解決編程問題的殺手锏。

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)計

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)的方法凡简，對于queue繼承的Collection,在不需要其他任何方法的情況下，就可以擁有一個可用的Queue

PriorityQueue

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

先進(jìn)先出聲明的是下一個元素應(yīng)該是等待時間最長的元素肋杖；

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

默認(rèn)順序?qū)⑹褂脤ο蟮淖匀豁樞蛲诤悄憧梢允褂米约旱腃omparator來修改這個順序;

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

使用案例

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)津畸，其中沒有不必要的代碼重復(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)繼承其他類時不能再繼承
• 生成Iterator -> 將隊列與消費(fèi)隊列的方法連接在一起的耦合度最小的方式與實(shí)現(xiàn)collection相比肉拓，在序列類上添加的約束也少得多

Foreach與迭代器

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

Collection與foreach

編譯時利用Iterable的iterator()方法產(chǎn)生一個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();

}

測試代碼

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);
        }
    }

}

編譯后測試代碼

//
// 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

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

測試代碼

public class ArrayForEachTest {

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

}

編譯后測試代碼

//
// 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提供了大量持有對象的方式：

1. 數(shù)組將數(shù)字與對象聯(lián)系起來。它保存類型明確的對象暖途，查詢對象時卑惜，不需要對結(jié)果做類型轉(zhuǎn)換。它可以是多維的驻售，可以保存基本類型型的數(shù)據(jù)露久。但是，數(shù)組一旦生成欺栗，其容量就不能改變毫痕。
2. Collection保存單一的元素，而Map保存相關(guān)聯(lián)的鍵值對迟几。有了java的泛型消请，你就可以知道容器存放的對象類型，因此你就不會將錯誤類型的對象放置到容器中类腮，并且在容器中獲取元素時臊泰，不必進(jìn)行類型轉(zhuǎn)換。各種類型的Collection和各種Map都可以在你向其中田間更多的元素時存哲，自動調(diào)整其尺寸因宇。容器不能持有基本類型，但是自動包裝機(jī)制會仔細(xì)地執(zhí)行基本類型到容器中所持有的包裝器類型之間雙向轉(zhuǎn)換祟偷。
3. 像數(shù)組一樣察滑，List也建立數(shù)字索引與對象的關(guān)聯(lián)，因此修肠，數(shù)組和List都是排好序的容器贺辰，List能夠自動擴(kuò)容。
4. 如果要進(jìn)行大量的隨機(jī)訪問嵌施，就使用ArrayList饲化；如果要經(jīng)常從表中間插入或刪除元素，則應(yīng)該使用LinkedList.
5. 各種Queue和Stack的行為吗伤，由LinkedList支持吃靠。
6. Map是一種將對象（而非數(shù)字）與對象相關(guān)聯(lián)的設(shè)計。Hashmap設(shè)計用來快速訪問足淆；而TreeMap保持"鍵"始終處于排序狀態(tài)巢块，所以沒有HashMap快礁阁。LinkedHash保持元素的插入順序，但也通過散列提供了快速訪問的能力族奢。
7. Set不接受重復(fù)元素姥闭。HashSet提供最快的查詢速度，而TreeSet保持元素處于排序狀態(tài)越走。LinedHashSet以插入順序保存元素棚品。
8. 新程序不應(yīng)該使用過時的Vector、Hashtable廊敌、Stack.