java基礎-集合

1、集合

????????在java中，集合（Collection）指的是一組數據容器，它可以存儲多個對象，并且允許用戶通過一些方法來訪問與操作這些對象。j

????????集合的實現原理都基于數據結構和算法，如下：

數據結構：

線性表：數組，鏈表（單鏈表，雙鏈表），棧，隊列（普通隊列，雙端隊列）。
散列表：散列函數（哈希算法）。
樹：平衡二叉樹，二叉查找樹，平衡二叉查找樹（紅黑樹）。

算法：

排序算法：冒泡排序，插入排序，選擇排序，歸并排序。
搜索：深度優先搜索，廣度優先搜索。
查找：線性表查找，樹結構查找，散列表查找。

?2、java集合

2.1、java集合框架圖（只做了解）

從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最后是具體實現類。

2.2、集合框架體系圖

Java 集合框架提供了一套性能優良，使用方便的接口和類，java集合框架位于java.util包中，所以當使用集合框架的時候需要進行導包。

2.3、常用的集合框架

? ? ? ? 2.3.1、ArrayList? ? ? ?

? ? ? ? ArrayList實現了List的接口，實現了可變大小的數組，隨機訪問和遍歷元素時，提供更好的性能。該類也是非同步的,在多線程的情況下不要使用，插入刪除效率低。

? ? ? ? PS:數組的特點：查詢快，增刪慢

????????當創建ArrayList對象時，如果使用的是無參構造器，則初始elementData容量為0 ，第一次添加則擴容elementData為10，如需要再次擴容，則擴容elementData為1.5 倍

? ? ? ? ps:

????????JDK 1.7：直接創建一個初始容量為10的數組
????????JDK 1.8：一開始創建一個長度為0的數組，當添加第一個元素時再創建一個始容量為10的數組

????????如過一次性添加多個元素，1.5倍放不下，則新創建數組的長度以實際為準

? ? ? ? 三種構建方式：

ArrayList():構造一個默認大小為10容量的空列表。
ArrayList(int initialCapacity):構造一個大小為指定int initialCapacity容量的空列表。
ArrayList(Collection c):構造一個和參數c相同元素的ArrayList對象

?常用api:

add()	將元素插入到指定位置的 arraylist 中
addAll()	添加集合中的所有元素到 arraylist 中
clear()	刪除 arraylist 中的所有元素
clone()	復制一份 arraylist
contains()	判斷元素是否在 arraylist
get()	通過索引值獲取 arraylist 中的元素
indexOf()	返回 arraylist 中元素的索引值
removeAll()	刪除存在于指定集合中的 arraylist 里的所有元素
remove()	刪除 arraylist 里的單個元素
size()	返回 arraylist 里元素數量
isEmpty()	判斷 arraylist 是否為空
subList()	截取部分 arraylist 的元素
set()	替換 arraylist 中指定索引的元素
sort()	對 arraylist 元素進行排序
toArray()	將 arraylist 轉換為數組
toString()	將 arraylist 轉換為字符串
ensureCapacity()	設置指定容量大小的 arraylist
lastIndexOf()	返回指定元素在 arraylist 中最后一次出現的位置
retainAll()	保留 arraylist 中在指定集合中也存在的那些元素
containsAll()	查看 arraylist 是否包含指定集合中的所有元素
trimToSize()	將 arraylist 中的容量調整為數組中的元素個數
removeRange()	刪除 arraylist 中指定索引之間存在的元素
replaceAll()	將給定的操作內容替換掉數組中每一個元素
removeIf()	刪除所有滿足特定條件的 arraylist 元素
forEach()	遍歷 arraylist 中每一個元素并執行特定操作

2.3.2、LinkedList

? ? ? ? LinkedList實現了List接口，允許有null（空）元素。LinkedList的底層是?雙向鏈表結構。由于鏈表沒有將元素存儲在連續的空間中，元素存儲在單獨的節點中，然后通過引用將節點連接起來了，因此在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。

? ? ? ? 構建方式：

LinkedList():構造一個空的LinkedList對象。
LinkedList(Collection c):構造一個和參數c相同元素的LinkedList對象。

? ? ? ? ?PS:鏈表表不存在容量不足的問題，沒有擴容機制

??常用api:

public boolean add(E e)	鏈表末尾添加元素，返回是否成功，成功為 true，失敗為 false。
public void add(int index, E element)	向指定位置插入元素。
public boolean addAll(Collection c)	將一個集合的所有元素添加到鏈表后面，返回是否成功，成功為 true，失敗為 false。
public boolean addAll(int index, Collection c)	將一個集合的所有元素添加到鏈表的指定位置后面，返回是否成功，成功為 true，失敗為 false。
public void addFirst(E e)	元素添加到頭部。
public void addLast(E e)	元素添加到尾部。
public boolean offer(E e)	向鏈表末尾添加元素，返回是否成功，成功為 true，失敗為 false。
public boolean offerFirst(E e)	頭部插入元素，返回是否成功，成功為 true，失敗為 false。
public boolean offerLast(E e)	尾部插入元素，返回是否成功，成功為 true，失敗為 false。
public void clear()	清空鏈表。
public E removeFirst()	刪除并返回第一個元素。
public E removeLast()	刪除并返回最后一個元素。
public boolean remove(Object o)	刪除某一元素，返回是否成功，成功為 true，失敗為 false。
public E remove(int index)	刪除指定位置的元素。
public E poll()	刪除并返回第一個元素。
public E remove()	刪除并返回第一個元素。
public boolean contains(Object o)	判斷是否含有某一元素。
public E get(int index)	返回指定位置的元素。
public E getFirst()	返回第一個元素。
public E getLast()	返回最后一個元素。
public int indexOf(Object o)	查找指定元素從前往后第一次出現的索引。
public int lastIndexOf(Object o)	查找指定元素最后一次出現的索引。
public E peek()	返回第一個元素。
public E element()	返回第一個元素。
public E peekFirst()	返回頭部元素。
public E peekLast()	返回尾部元素。
public E set(int index, E element)	設置指定位置的元素。
public Object clone()	克隆該列表。
public Iterator descendingIterator()	返回倒序迭代器。
public int size()	返回鏈表元素個數。
public ListIterator listIterator(int index)	返回從指定位置開始到末尾的迭代器。
public Object[] toArray()	返回一個由鏈表元素組成的數組。
public T[] toArray(T[] a)	返回一個由鏈表元素轉換類型而成的數組。

2.3.2、HashMap

HashMap 是一個散列表，它存儲的內容是鍵值對(key-value)映射，默認長度是16，擴容因子0.75。
HashMap 實現了 Map 接口，根據鍵的 HashCode 值存儲數據，具有很快的訪問速度，最多允許一條記錄的鍵為 null，不支持線程同步。
HashMap 是無序的，即不會記錄插入的順，線程不安全，key、value 都可以為 null，key是包裝類型。
HashMap 繼承于AbstractMap，實現了 Map、Cloneable、java.io.Serializable 接口。
jdk1.7采用頭插法，由數組 + 鏈表組成，鏈表是為了解決哈希沖突。
jdk1.8采用尾插法，由數組 + 鏈表+紅黑樹。（紅黑樹條件：鏈表長度大于8，且數組長度大于64）。

?常用api:

clear()	刪除 hashMap 中的所有鍵/值對
clone()	復制一份 hashMap
isEmpty()	判斷 hashMap 是否為空
size()	計算 hashMap 中鍵/值對的數量
put()	將鍵/值對添加到 hashMap 中
putAll()	將所有鍵/值對添加到 hashMap 中
putIfAbsent()	如果 hashMap 中不存在指定的鍵，則將指定的鍵/值對插入到 hashMap 中。
remove()	刪除 hashMap 中指定鍵 key 的映射關系
containsKey()	檢查 hashMap 中是否存在指定的 key 對應的映射關系。
containsValue()	檢查 hashMap 中是否存在指定的 value 對應的映射關系。
replace()	替換 hashMap 中是指定的 key 對應的 value。
replaceAll()	將 hashMap 中的所有映射關系替換成給定的函數所執行的結果。
get()	獲取指定 key 對應對 value
getOrDefault()	獲取指定 key 對應對 value，如果找不到 key ，則返回設置的默認值
forEach()	對 hashMap 中的每個映射執行指定的操作。
entrySet()	返回 hashMap 中所有映射項的集合集合視圖。
keySet()	返回 hashMap 中所有 key 組成的集合視圖。
values()	返回 hashMap 中存在的所有 value 值。
merge()	添加鍵值對到 hashMap 中
compute()	對 hashMap 中指定 key 的值進行重新計算
computeIfAbsent()	對 hashMap 中指定 key 的值進行重新計算，如果不存在這個 key，則添加到 hasMap 中
computeIfPresent()	對 hashMap 中指定 key 的值進行重新計算，前提是該 key 存在于 hashMap 中。