java面試題29 牛客 以下關于集合類ArrayList、LinkedList、HashMap描述錯誤的是（）

A HashMap實現Map接口，它允許任何類型的鍵和值對象，并允許將null用作鍵或值 B ArrayList和LinkedList均實現了List接口 C 添加和刪除元素時，ArrayList的表現更佳 D ArrayList的訪問速度比LinkedList快

蒙蔽樹上蒙蔽果，蒙蔽樹下你和我，我們先看看三者之間的一點使用規則

一、LinkedHashMap

LinkedHashMap會將元素串起來，形成一個雙鏈表結構。可以看到，其結構在HashMap結構上增加了鏈表結構。數據結構為（數組 + 單鏈表 + 紅黑樹 + 雙鏈表），圖中的標號是結點插入的順序

在這里插入圖片描述
1. 類的繼承關系

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap繼承了HashMap，所以HashMap的一些方法或者屬性也會被繼承；同時也實現了Map結構（HashMap原理分析

2. 類的屬性，相比HashMap新增（由于繼承HashMap，所以HashMap中的非private方法和字段，都可以在LinkedHashMap直接中訪問）

// 鏈表頭結點 transient LinkedHashMap.Entry<K,V> head;// 鏈表尾結點 transient LinkedHashMap.Entry<K,V> tail;// 訪問順序（可以指定accessOrder的值，從而控制訪問順序） final boolean accessOrder;

二、ArrayList

在這里插入圖片描述

?

1） 每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來數據向新數組的重新拷貝，因此，如果可預知數據量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數量2） transient Object[] elementData底層的數據結構就是數組，數組元素類型為Object類型，即可以存放所有類型數據。我們對ArrayList類的實例的所有的操作底層都是基于數組的3）ArrayList提供了三種方式的構造器，可以構造一個默認初始容量為10的空列表、構造一個指定初始容量的空列表以及構造一個包含指定collection的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的4）java 1.7之前ArrayList默認大小為10，但是1.8之后，默認是空，只有當add第一個元素時，才設置值默認值為105）ArrayList擴容時，正常情況下會擴容1.5倍（newCapacity = oldCapacity + (oldCapacity >> 1），特殊情況下（新擴展數組大小已經達到了最大值）則只取最大值6）indexOf是從頭開始查找與指定元素相等的元素，注意，是可以查找null元素的，意味著ArrayList中可以存放null元素的。與此函數對應的lastIndexOf，表示從尾部開始查找7）remove函數用戶移除指定下標的元素，此時會把指定下標到數組末尾的元素向前移動一個單位，并且會把數組最后一個元素設置為null，這樣是為了方便之后將整個數組不被使用時，會被GC，可以作為小的技巧使用

三、LinkedList

LinkedList底層使用的雙向鏈表結構，有一個頭結點和一個尾結點，雙向鏈表意味著我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷，并且可以針對頭部和尾部進行相應的操作
在這里插入圖片描述

1. 內部類（內部類Node就是實際的結點，用于存放實際元素的地方）

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

2. 類的屬性

LinkedList的屬性非常簡單，一個頭結點、一個尾結點、一個表示鏈表中實際元素個數的變量。注意，頭結點、尾結點都有transient關鍵字修飾，這也意味著在序列化時該域是不會序列化的?

3. 注意點

1）add函數用于向LinkedList中添加一個元素，并且添加到鏈表尾部?? ?

2）在調用remove移除結點時，會調用到unlink函數，將指定的結點從鏈表中斷開

3）LinkedList可以作為雙端隊列使用，這也是隊列結構在Java中一種實現，當需要使用隊列結構時，可以考慮LinkedList

四、HashSet和LinkedHashSet

1. HashSet底層是基于HashMap實現的，LinkedHashSet基于LinkedHashMap實現，所以HashSet、LinkedHashSet數據結構就是HashMap或者LinkedHashMap的數據結構

2. HashSet中由于只包含鍵，不包含值，由于在底層具體實現時，使用的HashMap或者是LinkedHashMap(可以指定構造函數來確定使用哪種結構)，我們知道HashMap是鍵值對存儲，所以為了適應HashMap存儲，HashSet增加了一個PRESENT類域（類所有），所有的鍵都有同一個值（PRESENT）

3. add、contains、remove函數都是基于HashMap或者LinkedHashMap做的操作

4. LinkedHashSet繼承自HashSet，也實現了一些接口，LinkedHashSet會調用HashSet的父類構造函數，讓其底層實現為LinkedHashMap，這樣就很好的實現了LinkedHashSet所需要的功能

一、ArrayList 和 LinkedList：

1、區別：

（1）ArrayList是基于動態數組的數據結構，查詢快，增刪慢，線程不安全。

LinkedList是基于鏈表的數據結構，查詢慢，增刪快。線程不安全。

（2）對ArrayList和LinkedList而言，在列表末尾增加一個元素所花的開銷都是固定的。

（3）對ArrayList而言，主要開銷是在內部數組中增加一項，指向所添加的元素，偶爾可能會導致對數組重新進行分配；而對LinkedList而言，這個開銷是統一的，分配一個內部Entry對象。
（4）在ArrayList的中間插入或刪除一個元素意味著這個列表中剩余的元素都會被移動；而在LinkedList的中間插入或刪除一個元素的開銷是固定的。
（5）LinkedList不支持高效的隨機元素訪問。
（6）ArrayList的空間浪費主要體現在在list列表的結尾預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗相當的空間。

2、ArrayList和LinkedList的時間復雜度：

（1）ArrayList 是線性表：
get() 直接讀取第幾個下標，復雜度 O(1)；
add(E) 添加元素，直接在后面添加，復雜度O（1）；
add(index, E) 添加元素，在第幾個元素后面插入，后面的元素需要向后移動，復雜度O（n）；
remove（）刪除元素，后面的元素需要逐個移動，復雜度O(n)。
（2）LinkedList 是鏈表的操作：
get() 獲取第幾個元素，依次遍歷，復雜度O(n)；
add(E) 添加到末尾，復雜度O(1)；
add(index, E) 添加第幾個元素后，需要先查找到第幾個元素，直接指針指向操作，復雜度O(n)；
remove（）刪除元素，直接指針指向操作，復雜度O(1)。

3、ArrayList為什么是線程不安全的？

（1）在 Items[Size] 的位置存放此元素；
（2）增大 Size 的值：
①在單線程運行的情況下，如果 Size = 0，添加一個元素后，此元素在位置 0，而且 Size=1；
②而如果是在多線程情況下，比如有兩個線程，線程 A 先將元素存放在位置 0。但是此時 CPU 調度線程A暫停，線程 B 得到運行的機會。線程B也向此 ArrayList 添加元素，因為此時 Size 仍然等于 0 （注意哦，我們假設的是添加一個元素是要兩個步驟哦，而線程A僅僅完成了步驟1），所以線程B也將元素存放在位置0。然后線程A和線程B都繼續運行，都增加 Size 的值。 那好，現在我們來看看 ArrayList 的情況，元素實際上只有一個，存放在位置 0，而 Size 卻等于 2。這就是“線程不安全”了。

4、ArrayList能否無限添加元素？會拋異常嗎？

使用ArrayList時，可以無限的往里添加元素，因為它底層是由數組實現的，使用無參構造方法時系統會默認提供默認參數10，而使用有參構造函數時我們會指定大小，當我們添加的元素個數大于數組的初始化長度時，ArrayList會自動為其擴容，擴容后的大小是int newCapacity = (oldCapacity * 3)/2 + 1;? （自動增加原來的50%）

HashMap介紹：

（1）HashMap是基于Map接口的非同步實現，結構可以看成數組+鏈表。

HashMap 是一個散列表，它存儲的內容是鍵值對映射，每一個鍵值對也叫做Entry（Entry的組成：Key、value、next），key和value都可以為null。HashMap中的映射不是有序的。

（2）HashMap 的實現不是同步的，這意味著它不是線程安全的，后執行的線程會覆蓋先執行線程的修改，在多線程環境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個線程安全的集合。

Collections.synchronizedMap()實現原理是：Collections定義了一個SynchronizedMap的內部類，這個類實現了Map接口，在調用方法時使用synchronized來保證線程同步,當然了實際上操作的還是我們傳入的HashMap實例，簡單的說就是Collections.synchronizedMap()方法幫我們在操作HashMap時自動添加了synchronized來實現線程同步。

（3）HashMap 的實例有兩個參數影響其性能：“初始容量” 和 “加載因子”。

??????? 容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量，容量必須是2的N次冪，這是為了提高計算機的執行效率。加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行 resize 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。（創建新表，將舊表映射到新表中）

??????? 通常，默認加載因子是 0.75, 這是在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本。在設置初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少 resize 操作次數。如果初始容量大于最大條目數除以加載因子，則不會發生 resize 操作。

（4）JDK8中HashMap的新特性:如果某個桶中的鏈表記錄過大的話（當前是TREEIFY_THRESHOLD = 8），就會把這個鏈動態變成紅黑二叉樹，使查詢最差復雜度由O(N)變成了O(logN)。

3、一些有關HashMap的問題：

（1）HashMap的get()、put()方法的工作原理？

??????? 我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存Entry對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。

（2）為什么String, Interger這樣的wrapper類適合作為HashMap鍵？

??????? 因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。
正確答案: C

我是歌謠，有什么不合理之處歡迎指出。喜歡敲代碼，偶爾刷刷題。

閱讀目錄（置頂)(長期更新計算機領域知識）

閱讀目錄（置頂)(長期更新計算機領域知識）

閱讀目錄（置頂)(長期科技領域知識）

歌謠帶你看java面試題

總結

以上是生活随笔為你收集整理的java面试题29 牛客 以下关于集合类ArrayList、LinkedList、HashMap描述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。