【Java面試知識點】Java集合架構
對集合的了解
(Java集合類架構的基本接口有哪些?)
集合類接口指定了一組叫做元素的對象。集合類接口的每一種具體的實作類都可以選擇以它自己的方式對元素進行儲存和排序。有的集合類允許重複的鍵,有些不允許。
Java集合類提供了一套設計良好的支援對一組對象進行操作的接口和類。Java集合類裡面最基本的接口有:
Collection:代表一組對象,每一個對象都是它的子元素。
List:有順序的collection,并且可以包含重複元素。
Set:不包含重複元素的Collection。
Queue:隊列,可以實作先進進出。
Map:可以把鍵(key)映射到值(value)的對象,鍵不能重複。
為什麼集合類沒有實作Cloneable和Serializable接口?
克隆(cloning)或者是序列化(serialization)的語義和含義是跟具體的實作相關的。
是以,應該由集合類的具體實作來決定如何被克隆或者是序列化。
什麼是疊代器(Iterator)?
Iterator接口提供了很多對集合元素進行疊代的方法。每一個集合類都包含了可以傳回疊代器執行個體的
疊代方法。疊代器可以在疊代的過程中删除底層集合的元素,但是不可以直接調用集合的
remove(Object Obj)删除,可以通過疊代器的remove()方法删除(删除的是上一次,也即是最近一次next傳回的對象)。
Iterator詳解
Iterator接口提供周遊任何Collection的接口。
我們可以從一個Collection中使用疊代器方法來擷取疊代器執行個體。
疊代器取代了Java集合架構中的Enumeration。
疊代器允許調用者在疊代過程中移除元素。
它包含有三個方法:
hasNext
next
remove
Iterator和ListIterator的差別是什麼?
Iterator可用來周遊Set和List集合,但是ListIterator隻能用來周遊List。
Iterator對集合隻能是前向周遊,ListIterator既可以前向也可以後向。
ListIterator實作了Iterator接口,并包含其他的功能,比如:增加元素,替換元素,擷取前一個和後一個元素的索引,等等。
快速失敗(fail-fast)和安全失敗(fail-safe)的差別是什麼?
Iterator的安全失敗是基于對底層集合做拷貝,是以,它不受源集合上修改的影響。
java.util包下面的所有的集合類都是快速失敗的,而java.util.concurrent包下面的所有的類都是安全失敗的。
快速失敗的疊代器會抛出ConcurrentModificationException異常,而安全失敗的疊代器永遠不會抛出這樣的異常。
通過疊代器fail-fast屬性,你明白了什麼?
每次我們嘗試擷取下一個元素的時候,Iterator fail-fast屬性檢查目前集合結構裡的任何改動。如果發現任何改動,它抛出ConcurrentModificationException。
Collection中所有Iterator的實作都是按fail-fast來設計的(ConcurrentHashMap和CopyOnWriteArrayList這類并發集合類除外)。
在疊代一個集合的時候,如何避免ConcurrentModificationException?
在周遊一個集合的時候,我們可以使用并發集合類來避免ConcurrentModificationException,比如使用CopyOnWriteArrayList,而不是ArrayList。
為何Iterator接口沒有具體的實作?
Iterator接口定義了周遊集合的方法,但它的實作則是集合實作類的責任。每個能夠傳回用于周遊的Iterator的集合類都有它自己的Iterator實作内部類。
這就允許集合類去選擇疊代器是fail-fast還是fail-safe的。比如,ArrayList疊代器是fail-fast的,而CopyOnWriteArrayList疊代器是fail-safe的。
解釋HashMap的底層實作原理?【2017阿裡電話面試真題】
Java中的HashMap是以鍵值對(key-value)的形式存儲元素的。HashMap需要一個hash函數,它使用hashCode()和equals()方法來向集合/從集合添加和檢索元素。當調用put()方法的時候,HashMap會計算key的hash值,然後把鍵值對存儲在集合中合适的索引上。如果key已經存在了,value會被更新成新值。HashMap的一些重要的特性是它的容量(capacity),負載因子(load factor)和擴容極限(threshold resizing)。
更為詳細的内容請參考HashMap工作原理及實作的總結
對ConcurrentHashMap的了解
ConCurrentHashMap中的Segment是不是越多越好?為什麼?
HashSet和TreeSet有什麼差別?
HashSet是由一個hash表來實作的,是以,它的元素是無序的。add(),remove(),contains()方法的時間複雜度是O(1)。
另一方面,TreeSet是由一個樹形的結構來實作的,它裡面的元素是有序的。是以,add(),remove(),contains()方法的時間複雜度是O(logn)。
HashMap和TreeMap的差別
和 HashSet和TreeSet有什麼差別 答案相同。
HashMap和Hashtable有什麼差別?
HashMap和Hashtable都實作了Map接口,是以很多特性非常相似。
但是,他們有以下不同點:
(1)HashMap允許鍵和值是null,而Hashtable不允許鍵或者值是null。
(2)HashTable是同步的,而HashMap不是。是以HashMap适合單線程環境,HashTable适合多線程環境。
(3)在Java1.4中引入了LinkedHashMap,HashMap的一個子類,假如你想要周遊順序,你很容易從HashMap轉向LinkedHashMap,但是HashTable不是這樣的,它的順序是不可預知的。
(4)HashMap提供對key的Set進行周遊,是以它是fail-fast的,但HashTable提供對key的Enumeration進行周遊,它不支援fail-fast。
(5)HashTable被認為是個遺留的類,如果你尋求在疊代的時候修改Map,你應該使用CocurrentHashMap。
需要更加深入的了解和比較兩者的異同。
數組(Array)和清單(ArrayList)有什麼差別?什麼時候應該使用Array而不是ArrayList?
下面列出了Array和ArrayList的不同點:
- Array可以包含基本類型和對象類型,ArrayList隻能包含對象類型。
- Array大小是固定的,ArrayList的大小是動态變化的。
- ArrayList提供了更多的方法和特性,比如:addAll(),removeAll(),iterator()等等。
- 對于基本類型資料,集合使用自動裝箱來減少編碼工作量。但是,當處理固定大小的基本資料類型的時候,這種方式相對比較慢。
- 如果你要使用多元數組,使用[][]比List<List<>>更容易。
要清楚ArrayList的實作細節
ArrayList和Vector有何異同點?
ArrayList和Vector在很多時候都很類似。
(1)兩者都是基于索引的,内部由一個數組支援。
(2)兩者維護插入的順序,我們可以根據插入順序來擷取元素。
(3)ArrayList和Vector的疊代器實作都是fail-fast的。
(4)ArrayList和Vector兩者允許null值,也可以使用索引值對元素進行随機通路。
以下是ArrayList和Vector的不同點。
(1)Vector是同步的,而ArrayList不是。然而,如果你尋求在疊代的時候對清單進行改變,你應該使用CopyOnWriteArrayList。
(2)ArrayList比Vector快,它因為有同步,不會過載。
(3)ArrayList更加通用,因為我們可以使用Collections工具類輕易地擷取同步清單和隻讀清單。
如何權衡是使用無序的數組還是有序的數組
有序數組最大的好處在于查找的時間複雜度是O(log n),而無序數組是O(n)。
有序數組的缺點是插入操作的時間複雜度是O(n),因為值大的元素需要往後移動來給新元素騰位置。相反,無序數組的插入時間複雜度是常量O(1)。
在ArrayList和LinkedList的末尾添加元素,哪個更快?【2017阿裡電話面試題目】
(自己的見解,如有問題,還望大家指正。)
LinkedList操作會更快。
ArrayList會根據數組的首位址和長度計算新元素的位置,然後将元素存儲到計算出的位置上。
LinkedList包含有last指針,直接将last.next執行新元素,然後将新元素指派給last即可。
當然兩者都需要更新長度。
ArrayList與LinkedList的差別?
ArrayList和LinkedList都實作了List接口,他們有以下的不同點:
(1)ArrayList是由Array所支援的基于一個索引的資料結構,是以它提供對元素的随機通路,複雜度為O(1),但LinkedList存儲一系列的節點資料,每個節點都與前一個和下一個節點相連接配接。是以,盡管有使用索引擷取元素的方法,内部實作是從起始點開始周遊,周遊到索引的節點然後傳回元素,時間複雜度為O(n),比ArrayList要慢。
(2)與ArrayList相比,在LinkedList中插入、添加和删除一個元素會更快,因為在一個元素被插入到中間的時候,不會涉及改變數組的大小,或更新索引。
(3)LinkedList比ArrayList消耗更多的記憶體,因為LinkedList中的每個節點存儲了前後節點的引用。
哪些集合類提供對元素的随機通路?
ArrayList、HashMap、TreeMap和HashTable類提供對元素的随機通路。
什麼是Java優先級隊列(Priority Queue)?
PriorityQueue是基于堆排序算法實作的隊列。
PriorityQueue是一個基于優先級堆的無界隊列,它的元素是按照自然順序(natural order)排序的。在建立的時候,我們可以給它提供一個負責給元素排序的比較器。PriorityQueue不允許null值,因為他們沒有自然順序,或者說他們沒有任何的相關聯的比較器。最後,PriorityQueue不是線程安全的,入隊和出隊的時間複雜度是O(log(n))。
Stack和ArrayList的差別
Java集合中哪些是線程安全的?
并發集合類是什麼?
Java1.5并發包(java.util.concurrent)包含線程安全集合類,允許在疊代時修改集合。疊代器被設計為safe-fast的,會抛出ConcurrentModificationException。
一部分類為:
CopyOnWriteArrayList、
CopyOnWriteArraySet,
ConcurrentHashMap
BlockingQueue是什麼?
Java.util.concurrent.BlockingQueue是一個隊列,
在進行檢索或移除一個元素的時候,它會等待隊列變為非空;
當在添加一個元素時,它會等待隊列中的可用空間。
BlockingQueue接口是Java集合架構的一部分,主要用于實作生産者-消費者模式。
我們不需要擔心等待生産者有可用的空間,或消費者有可用的對象,因為它都在BlockingQueue的實作類中被處理了。
Java提供了集中BlockingQueue的實作,比如
ArrayBlockingQueue、
LinkedBlockingQueue、
PriorityBlockingQueue,、
SynchronousQueue等。
對equals和hashCode方法的了解
(hashCode()和equals()方法的重要性展現在什麼地方?)
Java中的HashMap使用hashCode()和equals()方法來确定鍵值對的索引,當根據鍵擷取值的時候也會用到這兩個方法。如果沒有正确的實作這兩個方法,兩個不同的鍵可能會有相同的hash值,是以,可能會被集合認為是相等的。而且,這兩個方法也用來發現重複元素。是以這兩個方法的實作對HashMap的精确性和正确性是至關重要的。
hashCode和equals這兩個方法都是Object裡面的方法。
hashCode的預設結果是System.identityHashCode(obj)的傳回值,可以了解 obj 在記憶體中獨一無二的位址,是對象的唯一辨別。當使用 == 比較兩個對象是否相等(應該是相同,是嚴格的相等,它們是否是同一個對象)時,比較的就是對象的獨一無二的位址。
hashCode()和equals()方法有何重要性?
HashMap使用Key對象的hashCode()和equals()方法去決定key-value對的索引。當我們試着從HashMap中擷取值的時候,這些方法也會被用到。如果這些方法沒有被正确地實作,在這種情況下,兩個不同Key也許會産生相同的hashCode()和equals()輸出,HashMap将會認為它們是相同的,然後覆寫它們,而非把它們存儲到不同的地方。同樣的,所有不允許存儲重複資料的集合類都使用hashCode()和equals()去查找重複,是以正确實作它們非常重要。
equals()和hashCode()的實作應該遵循以下規則:
(1)如果o1.equals(o2),那麼o1.hashCode() == o2.hashCode()總是為true的。
(2)如果o1.hashCode() == o2.hashCode(),并不意味着o1.equals(o2)會為true。
Comparable和Comparator接口是幹什麼的?列出它們的差別
java.lang.Comparable 和 java.util.Comparator 接口(注意,它們的泛型類型參數會傳遞給對應的比較函數)
Java提供了隻包含一個compareTo()方法的Comparable接口。
這個方法可以個給兩個對象排序。具體來說,它傳回負數,0,正數來表明已經存在的對象小于,等于,大于輸入對象。
Java提供了包含compare()和equals()兩個方法的Comparator接口。
compare()方法用來給兩個輸入參數排序,傳回負數,0,正數表明第一個參數是小于,等于,大于第二個參數。
equals()方法需要一個對象作為參數,它用來決定輸入參數是否和comparator相等。
隻有當輸入參數也是一個comparator并且輸入參數和目前comparator的排序結果是相同的時候,這個方法才傳回true。
Java集合類架構的最佳實踐有哪些?
根據應用的需要正确選擇要使用的集合的類型對性能非常重要,比如:假如元素的數量是固定的,而且能事先知道,我們就應該用Array而不是ArrayList。
有些集合類允許指定初始容量。是以,如果我們能估計出存儲的元素的數目,我們可以設定初始容量來避免重新計算hash值或者是擴容。
為了類型安全,可讀性和健壯性的原因總是要使用泛型。同時,使用泛型還可以避免運作時的ClassCastException。
使用JDK提供的不變類(immutable class)作為Map的鍵可以避免為我們自己的類實作hashCode()和equals()方法。
程式設計的時候接口優于實作。
底層的集合實際上是空的情況下,傳回長度是0的集合或者是數組,不要傳回null。
Enumeration接口和Iterator接口的差別有哪些?
Enumeration的速度是Iterator的兩倍,也使用更少的記憶體。
Enumeration是非常基礎的,也滿足了基礎的需要。
但是,與Enumeration相比,Iterator更加安全,因為當一個集合正在被周遊的時候,它會阻止其它線程去修改集合。
疊代器取代了Java集合架構中的Enumeration。疊代器允許調用者從集合中移除元素,而Enumeration不能做到。
為了使它的功能更加清晰,疊代器方法名已經經過改善。
a.hashCode() 有什麼用?與 a.equals(b) 有什麼關系
hashCode() 方法是相應對象整型的 hash 值。它常用于基于 hash 的集合類,如 Hashtable、HashMap、LinkedHashMap等等。它與 equals() 方法關系特别緊密。
根據 Java 規範,兩個使用 equal() 方法來判斷相等的對象,必須具有相同的 hash code。
poll() 方法和 remove() 方法的差別?
poll() 和 remove() 都是從隊列中取出一個元素,
poll() 在擷取元素失敗的時候會傳回空,
remove() 失敗的時候會抛出異常。
Java集合類架構的最佳實踐有哪些
(1)根據需要選擇正确的集合類型。比如,如果指定了大小,我們會選用Array而非ArrayList。如果我們想根據插入順序周遊一個Map,我們需要使用TreeMap。如果我們不想重複,我們應該使用Set。
(2)一些集合類允許指定初始容量,是以如果我們能夠估計到存儲元素的數量,我們可以使用它,就避免了重新哈希或大小調整。
(3)基于接口程式設計,而非基于實作程式設計,它允許我們後來輕易地改變實作。(程式設計的時候接口優于實作。)
(4)總是使用類型安全的泛型,避免在運作時出現ClassCastException。
(5)使用JDK提供的不可變類作為Map的key,可以避免自己實作hashCode()和equals()。
(6)盡可能使用Collections工具類,或者擷取隻讀、同步或空的集合,而非編寫自己的實作。它将會提供代碼重用性,它有着更好的穩定性和可維護性。
(7) 底層的集合實際上是空的情況下,傳回長度是0的集合或者是數組,不要傳回null。
用哪兩種方式來實作集合的排序
你可以使用有序集合,如 TreeSet 或 TreeMap,
你也可以使用有順序的的集合,如 list,然後通過 Collections.sort() 來排序。
在周遊 ArrayList 時移除一個元素
該問題的關鍵在于面試者使用的是 ArrayList 的 remove() 還是 Iterator 的 remove()方法。
使用Iterator的remove方法來實作在周遊的過程中移除元素,它不會出現 ConcurrentModificationException 異常。
我們能自己寫一個容器類,然後使用 for-each 循環碼
可以,你可以寫一個自己的容器類。如果你想使用 Java 中增強的循環來周遊,你隻需要實作 Iterable 接口。如果你實作 Collection 接口,預設就具有該屬性。
ArrayList 和 HashMap 的預設大小是多數?(答案)
在 Java 7 中,ArrayList 的預設大小是 10 個元素,HashMap 的預設大小是16個元素(必須是2的幂)。
這就是 Java 7 中 ArrayList 和 HashMap 類的代碼片段:
// from ArrayList.java JDK 1.7
private static final int DEFAULT_CAPACITY = ;
//from HashMap.java JDK 7
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
當容量不足時,各個容器會擴充多大呢?
我們如何對一組對象進行排序
如果我們需要對一個對象數組進行排序,我們可以使用Arrays.sort()方法。
如果我們需要排序一個對象清單,我們可以使用Collection.sort()方法。兩個類都有用于自然排序(使用Comparable)或基于标準的排序(使用Comparator)的重載方法sort()。Collections内部使用數組排序方法,所有它們兩者都有相同的性能,隻是Collections需要花時間将清單轉換為數組。
TreeSet和TreeMap。
PriorityQueue
如何從給定集合那裡建立一個synchronized的集合
我們可以使用Collections.synchronizedCollection(Collection c)根據指定集合來擷取一個synchronized(線程安全的)集合。
集合架構裡實作的通用算法有哪些?
Java集合架構提供常用的算法實作,比如排序和搜尋。Collections類包含這些方法實作。大部分算法是操作List的,但一部分對所有類型的集合都是可用的。部分算法有排序、搜尋、混編、最大最小值。
參考:
最近5年133個Java面試問題清單
40個Java集合面試問題和答案