Java知識面試題複習(六)集合容器概述

manor的大數據奮鬥之路 2021-08-15 21:37:00 阅读数:387

本文一共[544]字,预计阅读时长:1分钟~
java 集合 容器 概述

集合容器概述

什麼是集合

集合框架:用於存儲數據的容器。

集合框架是為錶示和操作集合而規定的一種統一的標准的體系結構。
任何集合框架都包含三大塊內容:對外的接口、接口的實現和對集合運算的算法。

接口:錶示集合的抽象數據類型。接口允許我們操作集合時不必關注具體實現,從而達到“多態”。在面向對象編程語言中,接口通常用來形成規範。

實現:集合接口的具體實現,是重用性很高的數據結構。

算法:在一個實現了某個集合框架中的接口的對象身上完成某種有用的計算的方法,例如查找、排序等。這些算法通常是多態的,因為相同的方法可以在同一個接口被多個類實現時有不同的錶現。事實上,算法是可複用的函數。
它减少了程序設計的辛勞。

集合框架通過提供有用的數據結構和算法使你能集中注意力於你的程序的重要部分上,而不是為了讓程序能正常運轉而將注意力於低層設計上。
通過這些在無關API之間的簡易的互用性,使你免除了為改編對象或轉換代碼以便聯合這些API而去寫大量的代碼。 它提高了程序速度和質量。

集合的特點

集合的特點主要有如下兩點:

對象封裝數據,對象多了也需要存儲。集合用於存儲對象。

對象的個數確定可以使用數組,對象的個數不確定的可以用集合。因為集合是可變長度的。

集合和數組的區別

數組是固定長度的;集合可變長度的。

數組可以存儲基本數據類型,也可以存儲引用數據類型;集合只能存儲引用數據類型。

數組存儲的元素必須是同一個數據類型;集合存儲的對象可以是不同數據類型。

數據結構:就是容器中存儲數據的方式。

對於集合容器,有很多種。因為每一個容器的自身特點不同,其實原理在於每個容器的內部數據結構不同。

集合容器在不斷向上抽取過程中,出現了集合體系。在使用一個體系的原則:參閱頂層內容。建立底層對象。

使用集合框架的好處

容量自增長;
提供了高性能的數據結構和算法,使編碼更輕松,提高了程序速度和質量;
允許不同 API 之間的互操作,API之間可以來回傳遞集合;
可以方便地擴展或改寫集合,提高代碼複用性和可操作性。
通過使用JDK自帶的集合類,可以降低代碼維護和學習新API成本。
常用的集合類有哪些?
Map接口和Collection接口是所有集合框架的父接口:

Collection接口的子接口包括:Set接口和List接口
Map接口的實現類主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
Set接口的實現類主要有:HashSet、TreeSet、LinkedHashSet等
List接口的實現類主要有:ArrayList、LinkedList、Stack以及Vector等

List,Set,Map三者的區別?List、Set、Map 是否繼承自 Collection 接口?List、Map、Set 三個接口存取元素時,各有什麼特點?

在這裏插入圖片描述

Java 容器分為 Collection 和 Map 兩大類,Collection集合的子接口有Set、List、Queue三種子接口。我們比較常用的是Set、List,Map接口不是collection的子接口。

Collection集合主要有List和Set兩大接口

List:一個有序(元素存入集合的順序和取出的順序一致)容器,元素可以重複,可以插入多個null元素,元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。
Set:一個無序(存入和取出順序有可能不一致)容器,不可以存儲重複元素,只允許存入一個null元素,必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。
Map是一個鍵值對集合,存儲鍵、值和之間的映射。 Key無序,唯一;value 不要求有序,允許重複。Map沒有繼承於Collection接口,從Map集合中檢索元素時,只要給出鍵對象,就會返回對應的值對象。

Map 的常用實現類:HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

集合框架底層數據結構

Collection

List
Arraylist: Object數組
Vector: Object數組
LinkedList: 雙向循環鏈錶
Set
HashSet(無序,唯一):基於 HashMap 實現的,底層采用 HashMap 來保存元素
LinkedHashSet: LinkedHashSet 繼承與 HashSet,並且其內部是通過 LinkedHashMap 來實現的。有點類似於我們之前說的LinkedHashMap 其內部是基於 Hashmap 實現一樣,不過還是有一點點區別的。
TreeSet(有序,唯一): 紅黑樹(自平衡的排序二叉樹。)
Map

HashMap: JDK1.8之前HashMap由數組+鏈錶組成的,數組是HashMap的主體,鏈錶則是主要為了解决哈希沖突而存在的(“拉鏈法”解决沖突).JDK1.8以後在解决哈希沖突時有了較大的變化,當鏈錶長度大於閾值(默認為8)時,將鏈錶轉化為紅黑樹,以减少搜索時間
LinkedHashMap:LinkedHashMap 繼承自 HashMap,所以它的底層仍然是基於拉鏈式散列結構即由數組和鏈錶或紅黑樹組成。另外,LinkedHashMap 在上面結構的基礎上,增加了一條雙向鏈錶,使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈錶進行相應的操作,實現了訪問順序相關邏輯。
HashTable: 數組+鏈錶組成的,數組是 HashMap 的主體,鏈錶則是主要為了解决哈希沖突而存在的
TreeMap: 紅黑樹(自平衡的排序二叉樹)

哪些集合類是線程安全的?

vector:就比arraylist多了個同步化機制(線程安全),因為效率較低,現在已經不太建議使用。在web應用中,特別是前臺頁面,往往效率(頁面響應速度)是優先考慮的。
statck:堆棧類,先進後出。
hashtable:就比hashmap多了個線程安全。
enumeration:枚舉,相當於迭代器。
在這裏插入圖片描述

Java集合的快速失敗機制 “fail-fast”?

是java集合的一種錯誤檢測機制,當多個線程對集合進行結構上的改變的操作時,有可能會產生 fail-fast 機制。

例如:假設存在兩個線程(線程1、線程2),線程1通過Iterator在遍曆集合A中的元素,在某個時候線程2修改了集合A的結構(是結構上面的修改,而不是簡單的修改集合元素的內容),那麼這個時候程序就會拋出 ConcurrentModificationException 异常,從而產生fail-fast機制。

原因:迭代器在遍曆時直接訪問集合中的內容,並且在遍曆過程中使用一個 modCount 變量。集合在被遍曆期間如果內容發生變化,就會改變modCount的值。每當迭代器使用hashNext()/next()遍曆下一個元素之前,都會檢測modCount變量是否為expectedmodCount值,是的話就返回遍曆;否則拋出异常,終止遍曆。

解决辦法:

在遍曆過程中,所有涉及到改變modCount值得地方全部加上synchronized。

使用CopyOnWriteArrayList來替換ArrayList

怎麼確保一個集合不能被修改?
可以使用 Collections. unmodifiableCollection(Collection c) 方法來創建一個只讀集合,這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 异常。

示例代碼如下:

List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 運行時此行報錯
System. out. println(list. size());

Collection接口
List接口

迭代器 Iterator 是什麼?

Iterator 接口提供遍曆任何 Collection 的接口。我們可以從一個 Collection 中使用迭代器方法來獲取迭代器實例。迭代器取代了 Java 集合框架中的 Enumeration,迭代器允許調用者在迭代過程中移除元素。

Iterator 怎麼使用?有什麼特點?

Iterator 使用代碼如下:

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){

String obj = it. next();
System. out. println(obj);
}

Iterator 的特點是只能單向遍曆,但是更加安全,因為它可以確保,在當前遍曆的集合元素被更改的時候,就會拋出 ConcurrentModificationException 异常。

如何邊遍曆邊移除 Collection 中的元素?
邊遍曆邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法,如下:

Iterator<Integer> it = list.iterator();
while(it.hasNext()){

*// do something*
it.remove();
}

一種最常見的錯誤代碼如下:

for(Integer i : list){

list.remove(i)
}

運行以上錯誤代碼會報 ConcurrentModificationException 异常。這是因為當使用 foreach(for(Integer i : list)) 語句時,會自動生成一個iterator 來遍曆該 list,但同時該 list 正在被 Iterator.remove() 修改。Java 一般不允許一個線程在遍曆 Collection 時另一個線程修改它。

Iterator 和 ListIterator 有什麼區別?

Iterator 可以遍曆 Set 和 List 集合,而 ListIterator 只能遍曆 List。
Iterator 只能單向遍曆,而 ListIterator 可以雙向遍曆(向前/後遍曆)。
ListIterator 實現 Iterator 接口,然後添加了一些額外的功能,比如添加一個元素、替換一個元素、獲取前面或後面元素的索引比特置。
遍曆一個 List 有哪些不同的方式?每種方法的實現原理是什麼?Java 中 List 遍曆的最佳實踐是什麼?
遍曆方式有以下幾種:

for 循環遍曆,基於計數器。在集合外部維護一個計數器,然後依次讀取每一個比特置的元素,當讀取到最後一個元素後停止。

迭代器遍曆,Iterator。Iterator 是面向對象的一個設計模式,目的是屏蔽不同數據集合的特點,統一遍曆集合的接口。Java 在 Collections 中支持了 Iterator 模式。

foreach 循環遍曆。foreach 內部也是采用了 Iterator 的方式實現,使用時不需要顯式聲明 Iterator 或計數器。優點是代碼簡潔,不易出錯;缺點是只能做簡單的遍曆,不能在遍曆過程中操作數據集合,例如删除、替換。

最佳實踐:Java Collections 框架中提供了一個 RandomAccess 接口,用來標記 List 實現是否支持 Random Access。

如果一個數據集合實現了該接口,就意味著它支持 Random Access,按比特置讀取元素的平均時間複雜度為 O(1),如ArrayList。
如果沒有實現該接口,錶示不支持 Random Access,如LinkedList。
推薦的做法就是,支持 Random Access 的列錶可用 for 循環遍曆,否則建議用 Iterator 或 foreach 遍曆。

說一下 ArrayList 的優缺點

ArrayList的優點如下:

ArrayList 底層以數組實現,是一種隨機訪問模式。ArrayList 實現了 RandomAccess 接口,因此查找的時候非常快。
ArrayList 在順序添加一個元素的時候非常方便。
ArrayList 的缺點如下:

删除元素的時候,需要做一次元素複制操作。如果要複制的元素很多,那麼就會比較耗費性能。
插入元素的時候,也需要做一次元素複制操作,缺點同上。
ArrayList 比較適合順序添加、隨機訪問的場景。

如何實現數組和 List 之間的轉換?
數組轉 List:使用 Arrays. asList(array) 進行轉換。
List 轉數組:使用 List 自帶的 toArray() 方法。
代碼示例:

// list to array
List<String> list = new ArrayList<String>();
list.add("123");
list.add("456");
list.toArray();
// array to list
String[] array = new String[]{
"123","456"};
Arrays.asList(array);

ArrayList 和 LinkedList 的區別是什麼?

數據結構實現:ArrayList 是動態數組的數據結構實現,而 LinkedList 是雙向鏈錶的數據結構實現。
隨機訪問效率:ArrayList 比 LinkedList 在隨機訪問的時候效率要高,因為 LinkedList 是線性的數據存儲方式,所以需要移動指針從前往後依次查找。
增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因為 ArrayList 增删操作要影響數組內的其他數據的下標。
內存空間占用:LinkedList 比 ArrayList 更占內存,因為 LinkedList 的節點除了存儲數據,還存儲了兩個引用,一個指向前一個元素,一個指向後一個元素。
線程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保證線程安全;
綜合來說,在需要頻繁讀取集合中的元素時,更推薦使用 ArrayList,而在插入和删除操作較多時,更推薦使用 LinkedList。

補充:數據結構基礎之雙向鏈錶

雙向鏈錶也叫雙鏈錶,是鏈錶的一種,它的每個數據結點中都有兩個指針,分別指向直接後繼和直接前驅。所以,從雙向鏈錶中的任意一個結點開始,都可以很方便地訪問它的前驅結點和後繼結點。

ArrayList 和 Vector 的區別是什麼?

這兩個類都實現了 List 接口(List 接口繼承了 Collection 接口),他們都是有序集合

線程安全:Vector 使用了 Synchronized 來實現線程同步,是線程安全的,而 ArrayList 是非線程安全的。
性能:ArrayList 在性能方面要優於 Vector。
擴容:ArrayList 和 Vector 都會根據實際的需要動態的調整容量,只不過在 Vector 擴容每次會增加 1 倍,而 ArrayList 只會增加 50%。
Vector類的所有方法都是同步的。可以由兩個線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。

Arraylist不是同步的,所以在不需要保證線程安全時時建議使用Arraylist。

插入數據時,ArrayList、LinkedList、Vector誰速度較快?闡述 ArrayList、Vector、LinkedList 的存儲性能和特性?

ArrayList、LinkedList、Vector 底層的實現都是使用數組方式存儲數據。數組元素數大於實際存儲的數據以便增加和插入元素,它們都允許直接按序號索引元素,但是插入元素要涉及數組元素移動等內存操作,所以索引數據快而插入數據慢。

Vector 中的方法由於加了 synchronized 修飾,因此 Vector 是線程安全容器,但性能上較ArrayList差。

LinkedList 使用雙向鏈錶實現存儲,按序號索引數據需要進行前向或後向遍曆,但插入數據時只需要記錄當前項的前後項即可,所以 LinkedList 插入速度較快。

多線程場景下如何使用 ArrayList?

ArrayList 不是線程安全的,如果遇到多線程場景,可以通過 Collections 的 synchronizedList 方法將其轉換成線程安全的容器後再使用。例如像下面這樣:

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++) {

System.out.println(synchronizedList.get(i));
}

為什麼 ArrayList 的 elementData 加上 transient 修飾?
ArrayList 中的數組定義如下:

private transient Object[] elementData;

再看一下 ArrayList 的定義:

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到 ArrayList 實現了 Serializable 接口,這意味著 ArrayList 支持序列化。transient 的作用是說不希望 elementData 數組被序列化,重寫了 writeObject 實現:

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{

*// Write out element count, and any hidden stuff*
int expectedModCount = modCount;
s.defaultWriteObject();
*// Write out array length*
s.writeInt(elementData.length);
*// Write out all elements in the proper order.*
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {

throw new ConcurrentModificationException();
}

每次序列化時,先調用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然後遍曆 elementData,只序列化已存入的元素,這樣既加快了序列化的速度,又减小了序列化之後的文件大小。

List 和 Set 的區別

List , Set 都是繼承自Collection 接口

List 特點:一個有序(元素存入集合的順序和取出的順序一致)容器,元素可以重複,可以插入多個null元素,元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。

Set 特點:一個無序(存入和取出順序有可能不一致)容器,不可以存儲重複元素,只允許存入一個null元素,必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。

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

Set和List對比

Set:檢索元素效率低下,删除和插入效率高,插入和删除不會引起元素比特置改變。
List:和數組類似,List可以動態增長,查找元素效率高,插入删除元素效率低,因為會引起其他元素比特置改變

Set接口

說一下 HashSet 的實現原理?

HashSet 是基於 HashMap 實現的,HashSet的值存放於HashMap的key上,HashMap的value統一為PRESENT,因此 HashSet 的實現比較簡單,相關 HashSet 的操作,基本上都是直接調用底層 HashMap 的相關方法來完成,HashSet 不允許重複的值。

HashSet如何檢查重複?HashSet是如何保證數據不可重複的?

向HashSet 中add ()元素時,判斷元素是否存在的依據,不僅要比較hash值,同時還要結合equles 方法比較。
HashSet 中的add ()方法會使用HashMap 的put()方法。

HashMap 的 key 是唯一的,由源碼可以看出 HashSet 添加進去的值就是作為HashMap 的key,並且在HashMap中如果K/V相同時,會用新的V覆蓋掉舊的V,然後返回舊的V。所以不會重複( HashMap 比較key是否相等是先比較hashcode 再比較equals )。

以下是HashSet 部分源碼:

private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public HashSet() {

map = new HashMap<>();
}
public boolean add(E e) {

// 調用HashMap的put方法,PRESENT是一個至始至終都相同的虛值
return map.put(e, PRESENT)==null;
}

hashCode()與equals()的相關規定:

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

==與equals的區別

==是判斷兩個變量或實例是不是指向同一個內存空間 equals是判斷兩個變量或實例所指向的內存空間的值是不是相同
==是指對內存地址進行比較 equals()是對字符串的內容進行比較3.==指引用是否相同 equals()指的是值是否相同

HashSet與HashMap的區別

HashMap HashSet
實現了Map接口 實現Set接口
存儲鍵值對 僅存儲對象
調用put()向map中添加元素 調用add()方法向Set中添加元素
HashMap使用鍵(Key)計算Hashcode HashSet使用成員對象來計算hashcode值,對於兩個對象來說hashcode可能相同,所以equals()方法用來判斷對象的相等性,如果兩個對象不同的話,那麼返回false
HashMap相對於HashSet較快,因為它是使用唯一的鍵獲取對象 HashSet較HashMap來說比較慢
Queue

BlockingQueue是什麼?

Java.util.concurrent.BlockingQueue是一個隊列,在進行檢索或移除一個元素的時候,它會等待隊列變為非空;當在添加一個元素時,它會等待隊列中的可用空間。BlockingQueue接口是Java集合框架的一部分,主要用於實現生產者-消費者模式。我們不需要擔心等待生產者有可用的空間,或消費者有可用的對象,因為它都在BlockingQueue的實現類中被處理了。Java提供了集中BlockingQueue的實現,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什麼區別?

相同點:都是返回第一個元素,並在隊列中删除返回的對象。
不同點:如果沒有元素 poll()會返回 null,而 remove()會直接拋出 NoSuchElementException 异常。
代碼示例:

Queue<String> queue = new LinkedList<String>();
queue. offer("string"); // add
System. out. println(queue. poll());
System. out. println(queue. remove());
System. out. println(queue. size());

原文鏈接:https://blog.csdn.net/ThinkWon/article/details/104588551

版权声明:本文为[manor的大數據奮鬥之路]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815213646789e.html