JAVA進階程式設計——集合

目錄

1.1  JAVA集合架構概述

1.2 Collection接口的方法

1.3 Collection子接口

1.3.1  Collection子接口一：List

1.3.2  Collection子接口一：Set

1.4 Map接口

1.5  Collections工具類

1.1  JAVA集合架構概述

 |----Collection接口：單列集合，用來存儲一個一個的對象 

|----List接口：存儲有序的、可重複的資料。 --->“動态”數組 

                   |----ArrayList、LinkedList、Vector

|----Set接口：存儲無序的、不可重複的資料。--->高中講的“集合” 

                   |----HashSet、LinkedHashSet、TreeSet

|----Map接口：雙列集合，用來存儲一對(key - value)一對的資料 --->高中函數：y = f(x)

|----HashMap、LinkedHashMap、TreeMap、Hashtable、Properities

1.2 Collection接口的方法

• add(Object e):将元素e添加到集合coll中
• size():擷取添加的元素的個數
• addAll(Collection coll1):将coll1集合中的元素添加到目前的集合中
• clear():清空集合元素
• isEmpty():判斷目前集合是否為空
• contains(Object obj):判斷目前集合中是否包含obj，在判斷時會調用obj對象所在類的equals()
• containsAll(Collection coll1):判斷形參coll1中的所有元素是否都存在于目前集合中
• remove(Object obj):從目前集合中移除obj元素
• removeAll(Collection coll1):差集：從目前集合中移除coll1中所有的元素
• retainAll(Collection coll1):交集：擷取目前集合和coll1集合的交集，并傳回給目前集合
• equals(Object obj):要想傳回true，需要目前集合和形參集合的元素都相同
• hashCode():傳回目前對象的哈希值
• toArray()：集合--->數組
• Arrays.asList():數組 ---> 集合
• iterator():傳回Iterator接口的執行個體，用于周遊集合元素——

                            Iterator iterator = coll.iterator();  

                            while(iterator.hasNext()){ //next():①指針下移；②将下移以後集合位置上的元素傳回

                                           System.out.println(iterator.next());

                            }

                           foreach:

for(Object obj : coll){
                      System.out.println(obj);
                  }
           

1.3 Collection子接口

1.3.1  Collection子接口一：List

(1)List接口架構

|----List接口：存儲有序的、可重複的資料。 --->“動态”數組

* |----ArrayList：作為List接口的主要實作類；線程不安全的，效率高；底層使用Object[] elementData存儲,1.5倍擴容

* |----LinkedList：對于頻繁的插入、删除操作，使用此類效率比ArrayList高；底層使用雙向連結清單存儲

* |----Vector：作為List接口的古老實作類；線程安全的，效率低；底層使用Object[] elementData存儲,2倍擴容

(2)ArrayList的源碼分析：

* 2.1 jdk 7 的情況下

* ArrayList list = new ArrayList();//底層建立了長度是10的Object[]數組elementData

* list.add(123);//elementData[0] = new Integer(123);

 ...

* list.add(11);//如果此次的添加導緻底層elementData數組容量不夠，則擴容。預設情況下，擴容為原來的容量的1.5倍，同時需要将原有數組中的資料複制到新的數組中。

* 結論：建議開發中使用帶參的構造器：ArrayList list = new ArrayList(int capacity);

* 2.2 jdk 8 中ArrayList的變化：

* ArrayList list = new ArrayList();//底層Object[] elementData初始化為{}，并沒有建立長度為10的數組

* list.add(123);//第一次調用add()時，底層才建立了長度為10的數組，并将資料123添加到elementData[0]

...

* 後續的添加和擴容操作與jdk 7 無異

（3）LinkedList的源碼分析：

* LinkedList list = new LinkedList();内部聲明了Node類型的first和last屬性，預設值為null

* list.add(123);//将123封裝到Node中，建立了Node對象。

* 其中，Node定義為：展現了LinkedList的雙向連結清單的說法

private static class Node<E> {

            E item;

            Node<E> next;

            Node<E> prev; //雙指針

            Node(Node<E> prev, E element, Node<E> next) {

                             this.item = element;

                             this.next = next;

                             this.prev = prev;

            }

 }

（4）Vector的源碼分析：

jdk7和jdk8中通過Vector()構造器建立對象時，底層都建立了長度為10的數組。 在擴容方面，預設擴容為原來的數組長度的2倍。

（5）List接口中的常用方法：

• 增：add(Object obj)
• 删：remove(int index) / remove(Object obj)
• 改：set(int index,Object ele)
• 查：get(int index)
• 插：add(int index,Object ele)
• 長度：size()
• 周遊：①Iterator疊代器方式 ②增強for循環 ③普通的for循環

1.3.2  Collection子接口一：Set

(1)Set接口架構

|----Set接口：存儲無序的、不可重複的資料。--->高中講的“集合”

1.無序性：不等于随機性。存儲的資料在底層數組中并非按照數組索引的順序添加。而是根據資料的哈希值決定的。

2.不可重複性：保證添加的元素按照equals()判斷時，不能傳回true。即：相同的元素隻能添加一個。

|----HashSet：作為Set接口的主要實作類；線程不安全的；可以存儲null值

                    |----LinkedHashSet：作為HashSet的子類；周遊其内部資料時，可以按照添加的順序周遊。對于頻繁的周遊操作，LinkedHashSet效率高于HashSet

|----TreeSet：可以按照添加對象的指定屬性，進行排序。（隻能添加相同類的對象）

（2）Set添加元素的過程（以HashSet為例）

        要求：向Set中添加的資料，其所在的類一定要重寫hashCode()和equals()方法。

我們向HashSet中添加元素a，首先調用元素a所在類的hashCode()方法，計算元素a的哈希值，

此哈希值接着通過某種算法計算出在HashSet底層數組中的存放位置（即為：索引位置），判斷數組此位置上是否已經有元素：

       如果此位置上沒有其他元素，則元素a添加成功。 --->情況1

       如果此位置上有其他元素b（或以連結清單形式存在的多個元素），則比較元素a與元素b的hash值：

              如果hash值不相同，則元素a添加成功。 --->情況2

              如果hash值相同，進而需要調用元素a所在類的equals()方法：

                     equals()傳回true，元素a添加失敗

                     equals()傳回false，則元素a添加成功。--->情況3

對于添加成功的情況2和情況3而言：

       元素a與已經存在指定索引位置上資料以連結清單的方式存儲。 jdk 7 :元素a放在數組中，指向原來的元素。 jdk 8 :原來的元素在數組中，指向元素a。總結：七上八下

HashSet底層：數組+連結清單的結構。

（3）LinkedHashSet的使用

LinkedHashSet作為HashSet的子類，在添加資料的同時，每個資料還維護了兩個引用，記錄此資料前一個 資料和後一個資料。

優點：對于頻繁的周遊操作，LinkedHashSet效率高于HashSet

（4）TreeSet排序

（a）自然排序：比較兩個對象是否相同的标準為：compareTo()傳回0，不再是equals()。

1.類實作Comparable接口

2.重寫compareTo方法

（b）定制排序：比較兩個對象是否相同的标準為：compareTo()傳回0，不再是equals()。

1.自己建立一個Comparator

Comparator com = new Comparator() {

           //按照年齡從小到大排列

           @Override

           public int compare(Object o1, Object o2) {

                     if(o1 instanceof User && o2 instanceof User){

                                        User u1 = (User) o1;

                                        User u2 = (User) o2;

                                        return Integer.compare(u1.getAge(),u2.getAge());

                            }else{

                                       throw new RuntimeException("輸入的資料類型不比對");

                            }

                   }

};

2.TreeSet set = new TreeSet(com);

1.4 Map接口

（1）Map接口架構

|----Map：雙列資料，存儲key-value對的資料 

|----HashMap:作為Map的主要實作類；線程不安全的，效率高；存儲null的key和value

                     |----LinkedHashMap:保證在周遊map元素時，可以按照添加的順序實作周遊。 原因：在原有的HashMap底層結構基礎上，添加了一對指針，指向前一個和後一個元素。對于頻繁的周遊操作，此類執行效率高于HashMap。

HashMap的底層：數組+連結清單（jdk7及之前）；數組+連結清單+紅黑樹（jdk8）

|----TreeMap:保證按照添加的key-value對進行排序，實作排序周遊。此時考慮key的自然排序或定制排序。 底層使用紅黑樹。

|----Hashtable:作為古老的實作類；線程安全，效率低；不能存儲null的key和value

                      |----Properties:常用來處理配置檔案。key和value都是String類型

（2）Map結構的了解：

* Map中的key：無序的、不可重複的，使用Set存儲所有的key ---> key所在的類要重寫equals()和hashCode()（以HashMap為例）

* Map中的value：無序的、可重複的，使用Collection存儲所有的value --->value所在的類要重寫equals()

* 一個鍵值對：key-value構成了一個entry對象。

* Map中的entry：無序的、不可重複的，使用Set存儲所有的entry

（3）HahsMap的底層實作原理（以jdk7為例說明）：

* HashMap map = new HashMap()：

* 在執行個體化以後，底層建立了長度是16的一維數組Entry[] table。

 ...可能已經執行過多次put... map.put(key1,value1):

* 首先，調用key1所在類的hashCode()計算key1哈希值，此哈希值經過某種算法計算以後，得到在Entry數組中的存放位置。

* 如果此位置上的資料為空，此時的key1-value1添加成功。 ---情況1

* 如果此位置上的資料不為空，(意味着此位置上存在一個或多個資料(以連結清單形式存在))，比較key1和已經存在的一個或多個資料的哈希值：

         * 如果key1的哈希值與已經存在的資料的哈希值都不相同，此時key1-value1添加成功。 ---情況2

         * 如果key1的哈希值和已經存在的某一個資料的哈希值相同，繼續比較：調用key1所在類的equals(key2)方法，比較：

                  * 如果equals()傳回false：此時key1-value1添加成功。 ---情況3

                  * 如果equals()傳回true：使用value1替換value2。

* 補充：關于情況2和情況3：此時key1-value1和原來的資料以連結清單的方式存儲。

* 在不斷的添加過程中，會涉及到擴容問題，當超出臨界值（且要存放的位置非空）時，擴容。預設的擴容方式：擴容為原來容量的2倍，并将原有的資料複制過來。

 * jdk8相較于jdk7在底層實作方面的不同：

           * 1.new HashMap():底層沒有建立一個長度為16的數組

           * 2.jdk 8底層的數組是：Node[]，而非Entry[]

           * 3.首次調用put()方法時，底層建立長度為16的數組

           * 4.jdk7底層結構隻有：數組+連結清單。jdk8中底層結構：數組+連結清單+紅黑樹 。當數組的某一個索引位置上的元素以連結清單形式存在的資料個數 > 8 且目前數組的長度 > 64時， 此時此索引位置上的所有資料改為使用紅黑樹存儲。

                              * DEFAULT_INITIAL_CAPACITY : HashMap的預設容量，16

                              * DEFAULT_LOAD_FACTOR : HashMap的預設加載因子:0.75

                              * threshold : 擴容的臨界值，=容量*填充因子：16*0.75>=12

                             * TREEIFY_THRESHOLD : Bucket中連結清單長度大于該預設值，轉化為紅黑樹:8

                             * MIN_TREEIFY_CAPACITY:桶中的Node被樹化時最小的hash表容量：64

（3）LinkedHashMap的底層實作原理(了解)：

源碼中：

static class Entry<K,V> extends HashMap.Node<K,V>{

           Entry<K,V> before,after;//能夠記錄添加的元素的先後順序

           Entry(int hash,K key,V value,Node<K,V> next){

                     super(hash,key,value,next);

           }

 }

（4）Map中定義的方法

* 添加：put(Object key,Object value)

* 删除：remove(Object key)

* 修改：put(Object key,Object value)

* 查詢：get(Object key)

* 長度：size()

* 包含：containsKey(Object key)

* 周遊：keySet()/values()/entrySet()

（5）TreeMap排序——同TreeSet排序

1.5  Collections工具類

reverse(List):反轉List中元素的順序

shuffle(List)：對List集合元素進行随機排序

sort(List):根據元素的自然順序對指定List集合元素按升序排序

sort(List,Comparator):根據指定的Comparator産生的順序對List集合元素進行排序

swap(List , int , int):将指定list集合中的i處元素和j處元素進行交換 //Object max(Collection):

Object max(Collection,Comparator):

Object min(Collection):

Object min(Collection,Comparator):

int frequency(Collection,Object):傳回指定集合中指定元素的出現次數

boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替換List對象的所有舊值