【集合系列】- 初探java集合框架圖

一、集合類簡介

Java集合就像一種容器,可以把多個對象(實際上是對象的引用,但習慣上都稱對象)“丟進”該容器中。從Java 5 增加了泛型以後,Java集合可以記住容器中對象的數據類型,使得編碼更加簡潔、健壯。

Java集合大致可以分為兩大體系,一個是Collection,另一個是Map

  • Collection :主要由List、Set、Queue接口組成,List代表有序、重複的集合;其中Set代表無序、不可重複的集合;Java 5 又增加了Queue體系集合,代表一種隊列集合實現。
  • Map:則代表具有映射關係的鍵值對集合。

java.util.Collection下的接口和繼承類關係簡易結構圖:

java.util.Map下的接口和繼承類關係簡易結構圖:

其中,Java 集合框架中主要封裝的是典型的數據結構和算法,如動態數組、雙向鏈表、隊列、棧、Set、Map 等。

將集合框架挖掘處理,可以分為以下幾個部分
1) 數據結構
List列表、Queue隊列、Deque雙端隊列、Set集合、Map映射
2) 比較器
Comparator比較器、Comparable排序接口
3) 算法
Collections常用算法類、Arrays靜態數組的排序、查找算法
4) 迭代器
Iterator通用迭代器、ListIterator針對 List 特化的迭代器

二、有序列表(List)

List集合的特點就是存取有序,可以存儲重複的元素,可以用下標進行元素的操作

List主要實現類:ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList

ArrayList是一個動態數組結構,支持隨機存取,尾部插入刪除方便,內部插入刪除效率低(因為要移動數組元素);如果內部數組容量不足則自動擴容,因此當數組很大時,效率較低。

2.2、LinkedList

LinkedList是一個雙向鏈表結構,在任意位置插入刪除都很方便,但是不支持隨機取值,每次都只能從一端開始遍歷,直到找到查詢的對象,然後返回;不過,它不像 ArrayList 那樣需要進行內存拷貝,因此相對來說效率較高,但是因為存在額外的前驅和後繼節點指針,因此佔用的內存比 ArrayList 多一些。

2.3、Vector

Vector也是一個動態數組結構,一個元老級別的類,早在jdk1.1就引入進來類,之後在jdk1.2里引進ArrayList,ArrayList大部分的方法和Vector比較相似,兩者是不同的,Vector是允許同步訪問的,Vector中的操作是線程安全的,但是效率低,而ArrayList所有的操作都是異步的,執行效率高,但不安全!

關於Vector,現在用的很少了,因為裏面的getsetadd等方法都加了synchronized,所以,執行效率會比較低,如果需要在多線程中使用,可以採用下面語句創建ArrayList對象

List<Object> list =Collections.synchronizedList(new ArrayList<Object>());

也可以考慮使用複製容器 java.util.concurrent.CopyOnWriteArrayList進行操作,例如:

final CopyOnWriteArrayList<Object> cowList = new CopyOnWriteArrayList<String>(Object);

2.4、Stack

Stack是Vector的一個子類,本質也是一個動態數組結構,不同的是,它的數據結構是先進后出,取名叫棧!

關於Stack,現在用的也很少,因為有個ArrayDeque雙端隊列,可以替代Stack所有的功能,並且執行效率比它高!

三、集(Set)

Set集合的特點:元素不重複,存取無序,無下標;

Set主要實現類:HashSet、LinkedHashSet和TreeSet。

3.1、HashSet

HashSet底層是基於 HashMap 的k實現的,元素不可重複,特性同 HashMap。

3.2、LinkedHashSet

LinkedHashSet底層也是基於 LinkedHashMap 的k實現的,一樣元素不可重複,特性同 LinkedHashMap。

3.3、TreeSet

同樣的,TreeSet也是基於 TreeMap 的k實現的,同樣元素不可重複,特性同 TreeMap;

Set集合的實現,基本都是基於Map中的鍵做文章,使用Map中鍵不能重複、無序的特性;所以,我們只需要重點關注Map的實現即可!

四、隊列(Queue)

Queue是一個隊列集合,隊列通常是指“先進先出”(FIFO)的容器。新元素插入(offer)到隊列的尾部,訪問元素(poll)操作會返回隊列頭部的元素。通常,隊列不允許隨機訪問隊列中的元素。

Queue主要實現類:ArrayDeque、LinkedList、PriorityQueue。

4.1、ArrayDeque

ArrayQueue是一個基於數組實現的雙端隊列,可以想象,在隊列中存在兩個指針,一個指向頭部,一個指向尾部,因此它具有“FIFO隊列”及“棧”的方法特性。

既然是雙端隊列,那麼既可以先進先出,也可以先進后出,以下是測試例子!

先進先出

public static void main(String[] args) {
                ArrayDeque<String> queue = new ArrayDeque<>();
        //入隊
        queue.offer("AAA");
        queue.offer("BBB");
        queue.offer("CCC");
        System.out.println(queue);
        //獲取但不出隊
        System.out.println(queue.peek());
        System.out.println(queue);
        //出隊
        System.out.println(queue.poll());
        System.out.println(queue);
}

輸出結果:

[AAA, BBB, CCC]
AAA
[AAA, BBB, CCC]
AAA
[BBB, CCC]

先進后出

public static void main(String[] args) {
                ArrayDeque<String> stack = new ArrayDeque<>();
        //壓棧,此時AAA在最下,CCC在最外
        stack.push("AAA");
        stack.push("BBB");
        stack.push("CCC");
        System.out.println(stack);
        //獲取最後添加的元素,但不刪除
        System.out.println(stack.peek());
        System.out.println(stack);
        //彈出最後添加的元素
        System.out.println(stack.pop());
        System.out.println(stack);
}

輸出結果:

[CCC, BBB, AAA]
CCC
[CCC, BBB, AAA]
CCC
[BBB, AAA]

4.2、LinkedList

LinkedList是List接口的實現類,也是Deque的實現類,底層是一種雙向鏈表的數據結構,在上面咱們也有所介紹,LinkedList可以根據索引來獲取元素,增加或刪除元素的效率較高,如果查找的話需要遍歷整合集合,效率較低,LinkedList同時實現了stack、Queue、PriorityQueue的所有功能。

例子

public static void main(String[] args) {
                LinkedList<String> ll = new LinkedList<>();
        //入隊
        ll.offer("AAA");
        //壓棧
        ll.push("BBB");
        //雙端的另一端入隊
        ll.addFirst("NNN");
        ll.forEach(str -> System.out.println("遍歷中:" + str));
        //獲取隊頭
        System.out.println(ll.peekFirst());
        //獲取隊尾
        System.out.println(ll.peekLast());
        //彈棧
        System.out.println(ll.pop());
        System.out.println(ll);
        //雙端的後端出列
        System.out.println(ll.pollLast());
        System.out.println(ll);
}

輸出結果:

遍歷中:NNN
遍歷中:BBB
遍歷中:AAA
NNN
AAA
NNN
[BBB, AAA]
AAA
[BBB]

4.3、PriorityQueue

PriorityQueue也是一個隊列的實現類,此實現類中存儲的元素排列並不是按照元素添加的順序進行排列,而是內部會按元素的大小順序進行排列,是一種能夠自動排序的隊列。

例子

public static void main(String[] args) {
        PriorityQueue<Integer> queue1 = new PriorityQueue<>(10);

        System.out.println("處理前的數據");
        Random rand = new Random();
        for (int i = 0; i < 10; i++) {
                Integer num = rand.nextInt(90) + 10;
                System.out.print(num + ", ");
            queue1.offer(num); // 隨機兩位數
        }

        System.out.println("\n處理后的數據");
        for (int i = 0; i < 10; i++) { // 默認是自然排序 [升序]
            System.out.print(queue1.poll() + ", ");
        }
}

輸出結果:

處理前的數據
36, 23, 24, 11, 12, 26, 79, 96, 14, 73, 
處理后的數據
11, 12, 14, 23, 24, 26, 36, 73, 79, 96, 

五、映射表(Map)

Map是一個雙列集合,其中保存的是鍵值對,鍵要求保持唯一性,值可以重複。

Map 主要實現類:HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties。

5.1、HashMap

關於HashMap,相信大家都不陌生,繼承自AbstractMap,key 不可重複,因為使用的是哈希表存儲元素,所以輸入的數據與輸出的數據,順序基本不一致,另外,HashMap最多只允許一條記錄的 key 為 null。

5.2、LinkedHashMap

HashMap 的子類,內部使用鏈表數據結構來記錄插入的順序,使得輸入的記錄順序和輸出的記錄順序是相同的。LinkedHashMap與HashMap最大的不同處在於,LinkedHashMap輸入的記錄和輸出的記錄順序是相同的!

5.3、TreeMap

能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序,也可以指定排序的比較器,當用 Iterator 遍歷時,得到的記錄是排過序的;如需使用排序的映射,建議使用 TreeMap。TreeMap實際使用的比較少!

5.4、IdentityHashMap

繼承自AbstractMap,與HashMap有些不同,在獲取元素的時候,通過==代替equals ()來進行判斷,比較的是內存地址

get方法源碼部分

public V get(Object key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);
        while (true) {
            Object item = tab[i];
            //用==比較k和元素是否相等
            if (item == k)
                return (V) tab[i + 1];
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
}

5.5、WeakHashMap

WeakHashMap繼承自AbstractMap,被稱為緩存Map,向WeakHashMap中添加元素,再次通過鍵調用方法獲取元素方法時,不一定獲取到元素值,因為WeakHashMap 中的 Entry 可能隨時被 GC 回收。

5.6、Hashtable

Hashtable,一個元老級的類,鍵值不能為空,與HashMap不同的是,方法都加了synchronized同步鎖,是線程安全的,但是效率上,沒有HashMap快!

同時,HashMap 是 HashTable 的輕量級實現,他們都完成了Map 接口,區別在於 HashMap 允許K和V為空,而HashTable不允許K和V為空,由於非線程安全,效率上可能高於 Hashtable。

如果需要在多線程環境下使用HashMap,可以使用如下的同步器來實現或者使用併發工具包中的ConcurrentHashMap

Map<String, Object> map =Collections.synchronizedMap(new HashMap<>());

5.7、Properties

Properties繼承自HashTable,Properties新增了load()和和store()方法,可以直接導入或者將映射寫入文件,另外,Properties的鍵和值都是String類型。

六、比較器

Comparable和Comparator接口都是用來比較大小的,一般在TreeSet、TreeMap接口中使用的比較多,主要用於解決排序問題。

6.1、Comparable

Comparable:對實現它的每個類的對象進行整體排序

package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}

若一個類實現了Comparable 接口,實現 Comparable 接口的類的對象的 List 列表 ( 或數組)可以通過 Collections.sort(或 Arrays.sort)進行排序。

此外,實現 Comparable 接口的類的對象 可以用作 “有序映射 ( 如 TreeMap)” 中的鍵或 “有序集合 (TreeSet)” 中的元素,而不需要指定比較器。

使用例子:

/**
  * 實體類Person實現Comparable接口
  */
public class Person implements Comparable<Person>{
    private int age;
    private String name;

    public Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Person o){
        return this.age-o.age;
    }
    
    @Override
    public String toString(){
        return name+":"+age;
    }
}

測試

public static void main(String[] args) {
        Person person1 = new Person("張三",18);
        Person person2 = new Person("李四",17);
        Person person3 = new Person("王五",19);

        List<Person> list = new ArrayList<>();
        list.add(person1);
        list.add(person2);
        list.add(person3);

        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
}

輸出:

[張三:18, 李四:17, 王五:19]
[李四:17, 張三:18, 王五:19]
6.2、Comparator

Comparator:也是對實現它的每個類的對象進行排序

package java.util;
import ***;

public interface Comparator<T> {
    int compare(T o1, T o2);
    ......
}

如果我們的這個類Person無法修改或者沒有繼承Comparable接口,我們又要對其進行排序,Comparator就可以派上用場了。

將類Person實現的Comparable接口去掉

/**
  * 實體類Person
  */
public class Person {
    private int age;
    private String name;
    
    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString(){
        return name+":"+age;
    }
}

測試類:

public static void main(String[] args) {
        Person person1 = new Person("張三",18);
        Person person2 = new Person("李四",17);
        Person person3 = new Person("王五",19);

        List<Person> list = new ArrayList<>();
        list.add(person1);
        list.add(person2);
        list.add(person3);

        System.out.println(list);
        Collections.sort(list, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                if(o1 == null || o2 == null){
                    return 0;
                }
                //o1比o2小,返回負數
                //o1等於o2,等於0
                //o1大於o2,返回正數
                return o1.getAge()-o2.getAge();
            }
        });
        System.out.println(list);
}

輸出:

[張三:18, 李四:17, 王五:19]
[李四:17, 張三:18, 王五:19]

七、常用工具類

7.1、Collections類

java.util.Collections工具類為集合框架提供了很多有用的方法,這些方法都是靜態的,在編程中可以直接調用。整個Collections工具類源碼差不多有4000行,這裏只針對一些典型的方法進行闡述。

7.1.1、addAll

addAll:向指定的集合c中加入特定的一些元素elements

public static <T> boolean addAll(Collection<? super T> c, T… elements)
7.1.2、binarySearch

binarySearch:利用二分法在指定的集合中查找元素

#集合元素T實現Comparable接口的方式,進行查詢
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

#元素以外部實現Comparator接口的方式,進行查詢
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
7.1.3、sort
#集合元素T實現Comparable接口的方式,進行排序
public static <T extends Comparable<? super T>> void sort(List<T> list)

#元素以外部實現Comparator接口的方式,進行排序
public static <T> void sort(List<T> list, Comparator<? super T> c)
7.1.4、shuffle

shuffle:混排,隨機打亂原來的順序,它打亂在一個List中可能有的任何排列的蹤跡。

#方法一
public static void shuffle(List<?> list)

#方法二,指定隨機數訪問
public static void shuffle(List<?> list, Random rnd)
7.1.5、reverse

reverse:集合排列反轉

#直接反轉集合的元素
public static void reverse(List<?> list)

#返回可以使集合反轉的比較器Comparator
public static <T> Comparator<T> reverseOrder()

#集合的反轉的反轉,如果cmp不為null,返回cmp的反轉的比較器,如果cmp為null,效果等同於第二個方法.
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
7.1.6、synchronized系列

synchronized系列:確保所封裝的集合線程安全(強同步)

#同步Collection接口下的實現類
public static <T> Collection<T> synchronizedCollection(Collection<T> c)

#同步SortedSet接口下的實現類
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)

#同步List接口下的實現類
public static <T> List<T> synchronizedList(List<T> list)

#同步Map接口下的實現類
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

#同步SortedMap接口下的實現類
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)

7.2、Arrays類

java.util.Arrays工具類也為集合框架提供了很多有用的方法,這些方法都是靜態的,在編程中可以直接調用。整個Arrays工具類源碼有3000多行,這裏只針對一些典型的方法進行闡述。

7.2.1、asList

asList:將一個數組轉變成一個List,準確來說是ArrayList

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
}

注意:這個List是定長的,企圖添加或者刪除數據都會報錯java.lang.UnsupportedOperationException

7.2.2、sort

sort:對數組進行排序,適合byte,char,double,float,int,long,short等基本類型,還有Object類型

#基本數據類型,例子int類型數組
public static void sort(int[] a)

#Object類型數組
#如果使用Comparable進行排序,Object需要實現Comparable
#如果使用Comparator進行排序,可以使用外部比較方法實現
public static void sort(Object[] a)
7.2.3、binarySearch

binarySearch:通過二分查找法對已排序的數組進行查找。如果數組沒有經過Arrays.sort排序,那麼檢索結果未知。

適合byte,char,double,float,int,long,short等基本類型,還有Object類型和泛型。

#基本數據類型,例子int類型數組,key為要查詢的參數
public static int binarySearch(int[] a, int key)

#Object類型數組,key為要查詢的參數
#如果使用Comparable進行排序,Object需要實現Comparable
#如果使用Comparator進行排序,可以使用外部比較方法實現
public static int binarySearch(Object[] a, Object key)
7.2.4、copyOf

copyOf:數組拷貝,底層採用System.arrayCopy(native方法)實現。

適合byte,char,double,float,int,long,short等基本類型,還有泛型數組。

#基本數據類型,例子int類型數組,newLength新數組長度
public static int[] copyOf(int[] original, int newLength)

#T為泛型數組,newLength新數組長度
public static <T> T[] copyOf(T[] original, int newLength)
7.2.5、copyOfRange

copyOfRange:數組拷貝,指定一定的範圍,底層採用System.arrayCopy(native方法)實現。

適合byte,char,double,float,int,long,short等基本類型,還有泛型數組。

#基本數據類型,例子int類型數組,from:開始位置,to:結束位置
public static int[] copyOfRange(int[] original, int from, int to)

#T為泛型數組,from:開始位置,to:結束位置
public static <T> T[] copyOfRange(T[] original, int from, int to)
7.2.6、equals和deepEquals

equals:判斷兩個數組的每一個對應的元素是否相等(equals, 對於兩個數組的元素a和a2有a==null ? a2==null : a.equals(a2))

#基本數據類型,例子int類型數組,a為原數組,a2為目標數組
public static boolean equals(int[] a, int[] a2)

#Object數組,a為原數組,a2為目標數組
public static boolean equals(Object[] a, Object[] a2)

deepEquals:主要針對一個數組中的元素還是數組的情況(多維數組比較)

#Object數組,a1為原數組,a2為目標數組
public static boolean deepEquals(Object[] a1, Object[] a2)
7.2.7、toString和deepToString

toString:將數組轉換成字符串,中間用逗號隔開

#基本數據類型,例子int類型數組,a為數組
public static String toString(int[] a)

#Object數組,a為數組
public static String toString(Object[] a)

deepToString:當數組中又包含數組,就不能單純的利用Arrays.toString()了,使用此方法將數組轉換成字符串

#Object數組,a為數組
public static String deepToString(Object[] a)

八、迭代器

JCF的迭代器(Iterator)為我們提供了遍歷容器中元素的方法。只有容器本身清楚容器里元素的組織方式,因此迭代器只能通過容器本身得到。每個容器都會通過內部類的形式實現自己的迭代器。

ArrayList<String> list = new ArrayList<String>();
list.add(new String("a1"));
list.add(new String("a2"));
list.add(new String("a3"));
Iterator<String> it = list.iterator();//得到迭代器
while(it.hasNext()){
    String obj = it.next();//訪問元素
    System.out.println(obj);
}

JDK 1.5 引入了增強的for循環,簡化了迭代容器時的寫法

//使用增強for迭代
ArrayList<String> list = new ArrayList<String>();
list.add(new String("a1"));
list.add(new String("a2"));
list.add(new String("a3"));
for(String obj : list){
    //enhanced for statement
    System.out.println(obj);
}

九、總結

以上,主要是對java集合的整體架構進行簡單的介紹,如果有理解不當之處,歡迎指正。

十、參考

1、JDK1.7&JDK1.8 源碼
2、
3、

作者:炸雞可樂
原文出處:

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

※評比南投搬家公司費用收費行情懶人包大公開