集合学习总结

集合

1、java集合框架概述

​ 1.集合、數組都是多個數據存儲操作的結構，簡稱java容器

​ 說明：主要指的存儲是內存層面的存儲，不涉及到持久化的存儲

​ 可以分為Collection和Map兩種：

​ Collection接口：單列數據，定義了存取一組對象的方法的集合。

​ List：存儲有序、可重複的集合（ArrayList、LinkedList、Vector）

​ Set：存儲無序、不可重複的集合（HashSet、LinkedHashSet、TreeSet）

​ Map接口：雙列數據，保存具有映射關係“key-value對”的集合

​ HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

2、Collection接口方法

​ 增、刪、改、查、插、長度、遍歷

添加：add(Object o)、addAll(Collection coll)

獲取有效元素的個數：int size()

清空集合：void clear()

是否空集合：boolean isEmpty()

是否包含某個元素：boolean contains(Object o)、boolean containAll(Collection c)（通過調用equals方法來挨個判斷比較）

刪除：boolean remove(Object o)、boolean removeAll(Collection coll)

取兩個集合的交際：boolean retainAll(Collection coll)

集合是否相等：boolean equals(Object o)

轉成對象數組：Object[] toArray()

獲取集合對象的哈希值：hashCode()

遍歷：iterator()（返回迭代器對象）

3、Iterator迭代器接口

3.1 概述

​ Iterator对象称为迭代器(设计模式的一种)，主要用于遍歷 Collection 集合中的元素。GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。 迭代器模式，就是为容器而生。集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

3.2 使用原理

​ 調用.next()方法之前必須調用.hasNext()進行檢測。若不調用，且下一條記錄無效，直接調用.next()會拋出NoSuchElementException異常。

​ 實例：

Iterator iterator = coll.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

3.3 Iterato接口中的remove()

​ 注意：如果還未調用next()或在上一次調用 next 方法之后已經調用了 remove 方法，再調用remove都會报IllegalStateException。

​ 實例：

Iterator iter = coll.iterator();
while(iter.hasNext()){
    Object obj = iter.next();
    if(obj.equals("Tom")){
        iter.remove();
    }
}

4、Collection子接口一：List

4.1 概述

​ 通常用List代替數組。元素有序、可重複，集合中的每個元素都有對應的順序索引。其List接口的實現類常用有：ArrayList、LinkedList、Vector。

​ List接口：

​ ArrayLis：作為List接口的主要實現類，線程不安全，效率高；底層使用Object[] elementData存儲

​ LinkedList：對於頻繁的插入、刪除操作，使用此類效率比ArrayList高；底層使用雙向鏈錶存儲

​ Vector：作為List接口的古老實現類，線程安全，效率低；底層使用Object[]存儲

4.2 List接口方法

​ 除了從Collection集合繼承的方法外，還新增了以下的方法：

void add(int index,Object ele):在index位置插入ele元素

boolean addAll(int index, Collection eles):從index位置開始將eles中的所有元素添加進來

Object get(int index):獲取指定index位置的元素

int indexOf(Object obj):返回obj在集合中首次出現的位置

int lastIndexOf(Object obj):返回obj在當前集合中末次出現的位置

Object remove(inr index):移除指定index位置的元素，並返回此元素

Object set(int index, Object ele):設置指定index位置的元素為ele

List subList(int fromIndex, int toIndex):返回fromIndex到toIndex位置的子集合

4.3 List的實現類

4.3.1 ArrayList

​ 概述：作為List接口的主要實現類，線程不安全，效率高；底層使用Object[] elementData存儲

jdk7源碼分析：

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

jdk8源碼分析：

​ ArrayList list = new ArrayList();//底層Object[] elementData初始化為{}。並沒有創建長度為10的數組

​ list.add(123);//第一次調用add()時，底層才創建長度10的數組，並將數據123添加到elementData* …

​ 後續跟jdk7一致

ArrayList帶參構造器：initialCapacity傳入列表的初始容量，當初始容量為0時，this.element = EMPTY_ELEMENTDATA; 其中jdk8中定義EMPTY_ELEMENTDATA為Object類型的空集合：

private static final Object[] EMPTY_ELEMENTDATA = {}

區別於jdk7，內存少相對減少損耗。

4.3.2 LinkedList

​ 概述：雙向鏈錶，內部沒有聲明數組，而是定義了Node類型的first和last，用於記錄首末元素。同時，定義內部類Node，作為LinkedList中保存數據的基本結構。Node除了保存數據還定義了兩個變量：prev（記錄前一個元素的位置）、next（記錄下一個元素的位置。

源碼分析：

​ LinkedList llist = 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.3.3 Vector

​ 概述：古老的集合。相較於ArrayList是線程安全的，但效率低。比較少使用。

​ 新增方法：

​ void addElement(Object obj)

​ void insertElement(Object obj, int index)

​ void setElement(Object obj, int index)

​ void removeElement(Object obj)

​ void removeAllElement()

5、Collection子接口二：Set

5.1 概述

​ Collection的子接口，set接口沒有提供額外的方法。存儲無序的、不可重複的數據。其中無序性：不等於隨機性。存儲的數據在底層數組中並非按照數組索引的順序添加，二手根據數組的哈希索引值決定的。不可重複性：保證添加的元素按照equals()判斷時，不能返回true，即：相同的元素只能添加一個。

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

​ LinkedHashSet：作為HashSet的子類；遍歷其內部數據時，可以按照添加的順序進行排序

​ TreeSet：可以按照添加對象的指定屬性，進行排序。

5.2 Set的實現類

5.2.1 HashSet

​ 概述：底層也是數組，初始容量為16，當如果使用率超過0.75（16*0.75=12），就會擴大容量為原來的2倍。其中0.75指加載因子，具體參照HashMap章節。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tSpJwJzT-1648999110786)(D:\Typroa\集合\图片\1648910939633.png)]

​ 添加元素的過程：

向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與已經存在指定索引位置上數據以鏈錶的方式存儲。

HashSet底層：數組+鏈錶的結構。

jdk7：元素a放到數組中，指向原來的元素；jdk8：原來的元素在數組中，指向元素a

要求：向Set中添加的數據所在的類一定要重寫hashCode()和equals()，並盡可能保持一致性：相等的對象必須有相等的散列碼。對象中用作equals()方法比較的Field，都應該用來計算hashCode值。

其中關於hashCode()重寫：重寫hashCode()時係數是31，原因：選擇係數的時候要盡量大，因為計算出來的hash地址越大，所謂“沖突”就越少，查找起來效率也會越高。

5.2.2 LinkedHashSet

​ LinkedHashSet的使用：作為HashSet的子類，在添加數據的同時，每個數據還維護了兩個引用，記錄次數據的前一個數據和後一個數據。優點：對於頻繁的遍歷操作，LinkedHashSet效率高於HashSet。

Set set = new LinkedHashSet();
set.add(new String("AA"));
set.add(456);
set.add(456);
set.add(new Customer("劉德華",1001));

5.2.3 TreeSet

TreeSet的使用：

​ 1.向TreeSet中添加的數據，要求是相同類的對象；

​ 2.兩種排序方式：自然排序 實現Comparable接口；定制排序 實現comparator接口

​ 3.自然排序中，比較兩個對象是否相同的標準為：compareTo()返回0，不再是equals()

​ 4.定制排序中，比較兩個對象是否相同的標準為：compare()返回0，不再是equals()

自然排序

​ 概述：向TreeSet中添加元素時，只有第一個元素無需比較compareTo()方法，後面添加的元素都會。，所以向TreeSet中添加的應該是同一類的對象。判斷兩個對象是否相等的唯一標準是：兩個對象通過compareTo(Object obj)方法比較返回值。

​ 實例：

@Override
public int compareTo(Object o){
    if(o instanceof Employee){
        Employee e = (Employee)o;
        return this.name.compareTo(e.name);
    }else{
        throw new RuntimeException("傳入數據類型不一致");
    }
}

定制排序

​ 概述：通過Comparator接口來實現。需要重寫compare(T o1, T o2)方法。利用int compare(T o1,T o2)方法，比較o1和o2的大小；如果方法返回正整數，則表示o1大於o2；如果返回0，表示相等；返回負整數，表示o1小於o2.仍然只能想TreeSet中添加類型相同的對象。

​ 實例：

@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());
    }
    throw new RuntimeException("輸入的類型不一致");
}

兩種排序方式暫時不用到泛型

新增的方法

​ TreeSet是SortedSet接口的實現類，TreeSet可以確保集合元素處於排序狀態。TreeSet底層使用紅黑樹結構存儲數據，新增以下方法：

Comparator comparator()

Object fist()

Object last()

Object lower(Object e)

Object higher(Object e)

SortedSet subSet(fromElement, toElement)

SortedSet headSet(toElement)

SortedSet tailSet(fromElement)

6、Map接口

6.1 概述

​ 與Collection並列存在。用於保存具有映射關係的數據：key-value。其中key和value都可以是任何引用類型數據，key是用Set來存放，不允許重複，即同一個Map對象所對應的類，必須重寫hashCode()和equals()方法，Map接口的常用實現類：HashMap、TreeMap、LinkedHashMap和Properties。其中HashMap是Map接口使用頻率最高的實現類。

​ Map中的key：無需的、不可重複的，使用Set存儲所有的key–>所在類重寫equals()/hashCode()(以HashMap為例）

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

​ 一個鍵值對：key-value構成了一個Entry對象

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

6.2 常用方法

添加、刪除、修改：

Object put(Object key, Object value):建指定key-value添加到（或修改）當前map對象中；

void putAll(Map m):將m中的所有key-value對，並返回value；

Object remove(Object key):移除指定key的key-value對，並返回value；

void clear():清空當前map中的所有數據。

元素查詢的操作：

Object get(Object key):獲取指定key對應的value；

boolean containsValue(Object value):是否包含指定的value；

boolean containsKey(Object key):是否包含指定的key；

int size():返回map中key-value對的個數；

boolean isEmpty():判斷當前map是否空；

boolean equals(Object obj):判斷當前map和參數對象obj是否相等。

元視圖操作的方法：

Set keySet():返回所有key構成的Set集合；

Collection values():返回所有value構成的Collection集合

Set entrySet():返回所有key-value對構成的Set集合

6.3 Map的實現類

6.3.1 HashMap

​ 概述：允許使用null鍵和null值，與HashSet一樣，不保證映射順序。作為Map的主要實現類；線程不安全，效率高。

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的哈希值和已經存在的某一個數據（key2-value2）的哈希值相同，繼續比較：調用key1所在類的equals（key2）方法

​ 如果equals()返回false：此時key1-value1添加成功。—>情況3

​ 如果equals()返回true：使用value1替換value2.

補充：關於情況2和情況3：此時key1-value1和原來的數據以鏈錶的方式存儲。

在不斷地添加過程中，會涉及到擴容問題，默認的擴容方式：擴容為原來的餓2倍，並將原有的數據複製過來。

jdk8源碼分析：

jdk 8 相較於jdk 7在底層實現方面不同：

1.newHashMap():底層沒有創建一個長度16的數組

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

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

4.jdk 7底層結構只有：數組+鏈錶。jdk8 中底層結構：數組+鏈錶+紅黑樹

當數組的某一個索引位置上的元素以鏈錶形式存在的數據個數 > 8且當前數組的長度 > 64時，此時此索引位置上的所有數據改為使用紅黑樹存儲。

jdk8中HashMap源碼中的重要常量：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //HashMap的默認容量，16

static final int MAXIMUM_CAPACITY = 1 << 30; //HashMap的最大支持容量，2^30

static final float DEFAULT_LOAD_FACTOR = 0.75f; //HashMap的默認加載因子，0.75

static final int TREEIFY_THRESHOLD = 8; //Bucket中鏈錶長度大於該默認值，轉化為紅黑樹，8

static final int UNTREEIFY_THRESHOLD = 6; //Bucket中紅黑樹存儲的Node小於該默認值，轉化為鏈錶，6

static final int MIN_TREEIFY_CAPACITY = 64; //桶中的Node被樹化時最小的hash表容量。（當桶中Node的數量大到需要變紅黑樹時，若hash表容量小於MIN_TREEIFY_CAPACITY時，此時應該執行resize擴容操作這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。）

transient Node<K,V>[] table; //存儲元素的數組，總是2的n次冪

transient Set<Map.Entry<K,V>> entrySet; //存儲具體元素的集

transient int size; //HashMap中存儲的鍵值對的數量

transient int modCount; //HashMap擴容和結構改變的次數

int threshold; //擴容的臨界值，=容量*填充因子

final float loadFactor; //填充因子

6.3.2 LinkedHashMap

​ 概述：LinkedHashMap是HashMap的子類，，雙向鏈錶結構，保證在遍歷Map元素時，可以按照添加的順序實現遍歷。原因：在原有的HashMap底層結構基礎上，添加了一對指針，指向前一個和後一個元素。對於頻繁的遍歷操作，此類執行效率高於HashMap。

​ 源碼中：

LinkedHashMap中的內部類：Entry

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

HashMap中的內部類：Node

static class Node<K,V> implements Map.Entry<K,V>{
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

6.3.3 TreeMap

​ 概述：TreeMap存儲key-value對時，需要根據key-value對進行排序，保證所有鍵值對處於有序狀態，底層使用紅黑樹機構存儲數據。對key的排序有：自然排序和定制排序。判斷兩個key相等的標準：兩個key通過compareTo()方法或者compare()方法返回0。

自然排序

TreeMap的所有key必須實現Comparable接口，而且所有的key應該是同一個類的對象，否則將會拋出ClasssCastException。

​ 實例：

@Override
public int compareTo(Object o){
    if(o instanceof Employee){
        Employee e = (Employee)o;
        return this.name.compareTo(e.name);
    }else{
        throw new RuntimeException("傳入數據類型不一致");
    }
}

定制排序

創建TreeMap時，傳入一個Comparator對象，該對象負責對TreeMap中的所有key進行排序名詞是不需要Map的key實現Comparable接口。

​ 實例：

@Override
public int compareTo(Object o){
    if(o instanceof Employee){
        Employee e = (Employee)o;
        return this.name.compareTo(e.name);
    }else{
        throw new RuntimeException("傳入數據類型不一致");
    }
}

6.3.4 Hashtable

​ 概述：是個古老的Map實現類，不同於HashMap，其線程是安全的。實現原理和HashMap相同，底層都用哈希表結構，查詢速度快；與HashMap不同，其不允許使用null作為key和value。

6.3.5 Properties

​ 概述：是Hashtable的子類，用於處理屬性文件。Properties裡的key和value都是字符串類型，存取數據時，建議使用setProperty(String key, String value)方法和getProperty(String key)方法。

實例：

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);

7、Collections工具类

7.1 概述

​ Collections是一個操作Set、List和Map等集合的工具類(操作數組的工具類Arrays)，提供了一系列靜態的方法對集合元素進行排序、查詢和修改等操作，還提供了對集合對象設置不可變、對集合對象實現同步控制等方法。

7.2 常用方法

​ 操作順序：（均為static方法）

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):根據Comparator指定的順序，返回給定集合中的最大元素

Object min(Collection)、Object min(Collection, Comparator)

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

void copy(List dest, List src):將src中的內容複製到dest中

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

​ 同步控制：