java容器简图

image

对象引用保存

1. 数组

• 编译器支持类型
• 保存一组对象最有效的方式
• 保存基本类型数据时推荐使用
• 大小固定，不知道需要多少对象时受限

2. 容器

   用于解决在任意时刻，任意位置，创建任意数量的对象的问题。

容器基本概念

java容器类库的用途是“保存对象”，并将其分为两个不同的概念

1. Collection: 一个独立元素序列，这些元素都服从一条或多条规则
   • List：必须按照插入顺序保存元素
   • Set：不能有重复元素
   • Queue：按照队列规则来确定对象产生的顺序（通常与他们的插入顺序相同）
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();
}

使用方法

创建容器

1. 声明接口，创建实现，修改时仅修改创建位置即可

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

2. 声明和创建具体实现（需要具体实现中额外的功能）

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：将对象放入容器，不关注是否重复

一组元素

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()的区别
• 注意可选参数
• 注意不可变数组

容器打印

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

• 默认调用容器的toString()方法即可生成可读性很好的结果

List

承诺将元素维护在特定的序列中；

添加方法以实现在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

基于数组,下标随机访问元素快，插入、移除元素慢（数据的连续性）

LinkedList

• List中间插入和移除是高效
• 下标随机访问较低
• 支持栈、队列、双端队列的方法

迭代器

面对具体的容器编写的代码，并不能很好的用于另外一种容器，我们需要更高层次的抽象，迭代器能能够帮助我们达成目的。

迭代器是一个对象，他的工作是遍历并选择序列中的对象，而客户端程序员不必关心序列底层的结构。统一了对容器的访问方式。

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是一个更加强大的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

后进先出容器（LIFO)

public interface Stack<E>{

    E push(E item)；

    E pop()；

    E peek()；

    boolean empty()；

}

LinkedList已经实现栈相关功能，我们可以使用组合的方式,完成自定义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

不保存重复的元素

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，只是行为不同（继承与多态的典型应用）
• 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);
    }

}

• 注意打印结果，无重复
• 输出顺序无规律

使用散列函数,HashMap

TreeSet

将元素存储在红黑树中,TreeMap

LinkedHashSet

同样适用了散列函数,HashMap，但使用了链表来维护元素的插入顺序

使用场景

优先使用HashSet,需要对结果排序可以考虑使用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();

}

用于统计

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

典型的先进先出容器，从容器的一端放入，从另一端取出，并且放入容器的顺序与取出顺序一致。

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相关的方法，对于queue继承的Collection,在不需要其他任何方法的情况下，就可以拥有一个可用的Queue

PriorityQueue

先进先出描述了最典型的队列规则，队列规则是指在给定一组队列中元素的情况下，确定下一个弹出队列元素的规则。

先进先出声明的是下一个元素应该是等待时间最长的元素；

优先级队列声明下一个弹出元素是最高优先级的元素；

默认顺序将使用对象的自然顺序，但是你可以使用自己的Comparator来修改这个顺序;

PriorityQueue可以确保你调用peak()、poll()、和remove()方法时，获取到的元素是队列中优先级最高的元素

使用案例

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的默认实现，其中没有不必要的代码重复

实现Collection接口就意味着需要提供iterator()方法

iterable比iterator()方法要方便，可以使用foreach结构，从而使代码更加清晰

实现遍历的方式

• 实现Collection接口 -> 强制去实现遍历用不到的collection相关方法
• 继承AbstractCollection抽象类 -> 已经继承其他类时不能再继承
• 生成Iterator -> 将队列与消费队列的方法连接在一起的耦合度最小的方式与实现collection相比，在序列类上添加的约束也少得多

Foreach与迭代器

foreach语法主要用于集合与数组

Collection与foreach

编译时利用Iterable的iterator()方法产生一个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);
        }

    }
}

数组与foreach

编译时利用简单for循环和下标自增的方法实现数组遍历

测试代码

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接口，从而实现多种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();
    }

}

总结

Java提供了大量持有对象的方式：

1. 数组将数字与对象联系起来。它保存类型明确的对象，查询对象时，不需要对结果做类型转换。它可以是多维的，可以保存基本类型型的数据。但是，数组一旦生成，其容量就不能改变。
2. Collection保存单一的元素，而Map保存相关联的键值对。有了java的泛型，你就可以知道容器存放的对象类型，因此你就不会将错误类型的对象放置到容器中，并且在容器中获取元素时，不必进行类型转换。各种类型的Collection和各种Map都可以在你向其中田间更多的元素时，自动调整其尺寸。容器不能持有基本类型，但是自动包装机制会仔细地执行基本类型到容器中所持有的包装器类型之间双向转换。
3. 像数组一样，List也建立数字索引与对象的关联，因此，数组和List都是排好序的容器，List能够自动扩容。
4. 如果要进行大量的随机访问，就使用ArrayList；如果要经常从表中间插入或删除元素，则应该使用LinkedList.
5. 各种Queue和Stack的行为，由LinkedList支持。
6. Map是一种将对象（而非数字）与对象相关联的设计。Hashmap设计用来快速访问；而TreeMap保持"键"始终处于排序状态，所以没有HashMap快。LinkedHash保持元素的插入顺序，但也通过散列提供了快速访问的能力。
7. Set不接受重复元素。HashSet提供最快的查询速度，而TreeSet保持元素处于排序状态。LinedHashSet以插入顺序保存元素。
8. 新程序不应该使用过时的Vector、Hashtable、Stack.