Java集合基礎知識

一、集合概述

什么是集合？

集合是Java提供的一種容器，用來存盤多個資料

集合的特點有什么？

• 物件封裝資料，物件多了也需要存盤，集合用于存盤物件，

• 物件的個數確定可以使用陣列，物件的個數不確定的可以用集合，因為集合是可變長度的，

集合和陣列的區別有哪些？

• 集合長度可變，陣列是固定長度
• 集合僅可以存盤參考資料型別，陣列既可以存盤基本資料型別也可以存盤參考資料型別
• 集合可以存盤不同資料型別，陣列只可以存盤同一種資料型別

集合的好處有哪些？

• 容器自動增長
• 提供了高性能的資料結構和演算法，提高了程式的速度和質量

常用的集合類有哪些？

集合框架底層資料結構

• List
  ArrayList：陣列
  Vector：陣列
  LinkedList：雙向回圈鏈表
• Set
  HashSet：基于HashMap實作
  LinkedHashSet：繼承HashSet，內部通過LinkedHashMap
  TreeSet：紅黑樹
• Map
  HashMap：
  • jdk1.8前：陣列+鏈表
  • jdk1.8后：陣列+鏈表/紅黑樹（鏈表長度達到8，鏈表轉為紅黑樹）減少搜索時間
    LinkedHashMap：繼承自HashMap，底層仍然是陣列和鏈表或紅黑樹組成另外，增加了一條雙向鏈表，保證鍵值對的加入順序
    HashTable：陣列+鏈表，陣列是HashTable主體，鏈表是為了解決哈希沖突
    TreeMap：紅黑樹

List介面

迭代器Iterator是什么？

Iterator介面提供遍歷任何Collection的介面

Iterator的使用

1.使用集合中方法iterator（）獲取迭代器的實作類物件，使用Iterator介面接收（多型）
2.使用Integer介面中方法hasNext判斷有無下一個元素
3.使用Integer介面中方法next取出集合中下一個元素

如何一邊遍歷一邊移除Collection中的元素

使用Iterator…remove（）方法

遍歷List集合的方式

• for回圈比阿尼了，基于計數器依次讀取元素
• 迭代器遍歷
• foreach增強for回圈

ArrayList的優缺點

優點：底層是陣列，查詢快，按順序添加也方便
缺點：洗掉或插入元素的時候，需要做一次元素復制操作，

如何實作陣列和List之間的轉換

陣列轉LIst：Arrays.asList（array）
List轉陣列：使用List自帶的toArray（）

ArrayList 和 LinkedList 的區別是什么？

• 資料結構實作：ArrayList 是動態陣列的資料結構實作，而 LinkedList 是雙向鏈表的資料結構實作，
• 隨機訪問效率：ArrayList 比 LinkedList 在隨機訪問的時候效率要高，因為 LinkedList 是線性的資料存盤方式，所以需要移動指標從前往后依次查找，
• 增加和洗掉效率：在非首尾的增加和洗掉操作，LinkedList 要比 ArrayList 效率要高，因為 ArrayList 增刪操作要影響陣列內的其他資料的下標，
• 記憶體空間占用：LinkedList 比 ArrayList 更占記憶體，因為 LinkedList 的節點除了存盤資料，還存盤了兩個參考，一個指向前一個元素，一個指向后一個元素，
• 執行緒安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證執行緒安全；

List 和 Set 的區別

List , Set 都是繼承自Collection 介面

List 特點：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引，常用的實作類有 ArrayList、LinkedList 和 Vector，

Set 特點：一個無序（存入和取出順序有可能不一致）容器，不可以存盤重復元素，只允許存入一個null元素，必須保證元素唯一性，Set 介面常用實作類是 HashSet、LinkedHashSet 以及 TreeSet，

另外 List 支持for回圈，也就是通過下標來遍歷，也可以用迭代器，但是set只能用迭代，因為他無序，無法用下標來取得想要的值，

Set和List對比

Set：檢索元素效率低下，洗掉和插入效率高，插入和洗掉不會引起元素位置改變，
List：和陣列類似，List可以動態增長，查找元素效率高，插入洗掉元素效率低，因為會引起其他元素位置改變

HashSet的實作原理

HashSet 是基于 HashMap 實作的，HashSet的值存放于HashMap的key上，HashMap的value統一為PRESENT，因此 HashSet 的實作比較簡單，相關 HashSet 的操作，基本上都是直接呼叫底層 HashMap 的相關方法來完成，HashSet 不允許重復的值，

HashSet如何檢查重復？

hashCode（）與equals（）的相關規定：

• 如果兩個物件相等，則hashcode一定也是相同的
• 兩個物件相等,對兩個equals方法回傳true
• 兩個物件有相同的hashcode值，它們也不一定是相等的
  綜上，equals方法被覆寫過，則hashCode方法也必須被覆寫
  hashCode()的默認行為是對堆上的物件產生獨特值，如果沒有重寫hashCode()，則該class的兩個物件無論如何都不會相等（即使這兩個物件指向相同的資料），

==與equals的區別

1.== 是判斷兩個變數或實體是不是指向同一個記憶體空間 equals是判斷兩個變數或實體所指向的記憶體空間的值是不是相同
2.==是指對記憶體地址進行比較 equals()是對字串的內容進行比較
3.==指參考是否相同 equals()指的是值是否相同

Map

HashMap概述

HashMap是基于哈希表的Map介面的非同步實作，此實作提供所有可選的映射操作，并允許使用null值和null鍵，此類不保證映射的順序，特別是它不保證該順序恒久不變，

HashMap實作原理

基于hash演算法實作 ，當向HashMap中添加元素 ，利用key的hashcode重新hash奇偶算出當前物件的元素在陣列中的下標 存盤時如果hash值相同的key，如果key相同覆寫原值，不同，則存入鏈表 獲取則直接尋找下標，在判斷key是否相同找到對應值

什么是哈希？

Hash，一般翻譯為“散列”，也有直接音譯為“哈希”的，這就是把任意長度的輸入通過散列演算法，變換成固定長度的輸出，該輸出就是散列值（哈希值）；這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值，簡單的說就是一種將任意長度的訊息壓縮到某一固定長度的訊息摘要的函式，

什么是哈希沖突

當兩個不同的輸入值，根據同一散列函式計算出相同的散列值的現象

HashMap是使用了哪些方法來有效解決哈希沖突的：

1. 使用鏈地址法（使用散串列）來鏈接擁有相同hash值的資料；
2. 使用2次擾動函式（hash函式）來降低哈希沖突的概率，使得資料分布更平均；
3. 引入紅黑樹進一步降低遍歷的時間復雜度，使得遍歷更快；

能否使用任何類作為Map的key

可以，但是如果類重寫equals方法也需要重寫hashcode方法
類的所有實體需要遵循equals和hashcode的相關規則
如果一個類沒有使用equals不應該在hashcode中使用他

為什么HashMap中String、Integer這樣的包裝類適合作為key

都是final型保證key不可變不會存在獲取hash值不同的可能 內部已經重寫過equals和hashcode

如果使用Object作為key怎么辦

重寫hashcode和equals方法

HashMap為什么不直接使用hashcode處理后的哈希值直接作為table的下標？

hashcode回傳的整數型，范圍有些大，而HashMap的容量范圍在16，HashMap通常情況下取不到最大值

HashMap與Hashtable的區別

• HashMap：非執行緒安全，效率較Hashtable高，允許null存入，1.8后當鏈表長度大于8轉換為紅黑樹
• Hashtable：執行緒安全，效率較HashMap低，不允許null存入，陣列+鏈表

容易忽略的小知識

Array和ArrayList區別

• Array可以存盤基本資料型別和物件，固定大小
• ArrayList可以存盤物件，自動擴展

comparable與comparator的區別

• comparable：介面出自java.long，利用compareTo方法用來排序
• comparator：介面出自java.util，有一個compare方法排序.

Collections與Collection有什么區別

• java.util.Collection集合介面
• Collections則是集合類的一個工具類/幫助類

TreeMap和TreeSet在排序時如何比較元素？

• TreeSet要求存放物件所屬的類必須實作Comparable介面
• TreeMap要求存放的鍵值對映射鍵必須實作Comparable介面根據鍵進行排序

到這里集合基礎知識就結束啦，感謝大家的耐心觀看.
如有不足，歡迎指出，共同進步！

• 文章著作權歸作者所有，歡迎轉載