在看集合相關面試題之前，先好好看看下面這個集合的截圖，有助于對集合知識的理解與記憶： 說一下數據結構中的什么是數組？什么是鏈表？ 所謂數組，是相同數據類型的元素按一定順序排列的集合 數組：存儲區間是連續的，占用內存嚴重，故空間復雜的很大。但數組的二分查找時間復雜度小，為O(1)；數組的特點是：尋址容易，插入和刪除困難；

鏈表，鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。 鏈表:鏈表存儲區間離散，占用內存比較寬松，故空間復雜度很小，但時間復雜度很大，達O（N）。鏈表的特點是：尋址困難，插入和刪除容易。 說一下什么是哈希表 那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表。哈希表（(Hash table）既滿足了數據的查找方便，同時不占用太多的內容空間，使用也十分方便。 　　哈希表有多種不同的實現方法，我接下來解釋的是最常用的一種方法—— 拉鏈法，我們可以理解為“鏈表的數組” ，如圖： 　　 說一下ArrayList底層實現方式？ ①ArrayList通過數組實現，一旦我們實例化ArrayList無參數構造函數默認為數組初始化長度為10 ②add方法底層實現如果增加的元素個數超過了10個，那么ArrayList底層會新生成一個數組，長度為原數組的1.5倍+1，然后將原數組的內容復制到新數組當中，并且后續增加的內容都會放到新數組當中。當新數組無法容納增加的元素時，重復該過程。是一旦數組超出長度，就開始擴容數組。擴容數組調用的方法 Arrays.copyOf(objArr, objArr.length + 1); 說一下LinkedList底層實現方式？ LinkedList底層的數據結構是基于雙向循環鏈表的，且頭結點中不存放數據,如下： 既然是雙向鏈表，那么必定存在一種數據結構——我們可以稱之為節點，節點實例保存業務數據，前一個節點的位置信息和后一個節點位置信息，如下圖所示： 說一下HashMap底層實現方式？ HashMap是由數組+鏈表組成 put方法底層實現: 通過key的hash值%Entry[].length得到該存儲的下標位置，如果多個key的hash值%Entry[].length 值相同話就就會存儲到該鏈表的后面。 ArrayList 和 Vector 的區別 這兩個類都實現了 List 接口(List 接口繼承了Collection 接口),他們都是有序集合,即存儲在這兩個集合中的元素的位置都是有順序的,相當于一種動態的數組,我們以后可以按位置索引號取出某個元素,并且其中的數據是允許重復的, ArrayList 與 Vector 的區別,這主要包括兩個方面:. (1)同步性: Vector 是線程安全的,也就是說是它的方法之間是線程同步的,而 ArrayList 是線程序不安全的,它的方法之間是線程不同步的。如果只有一個線程會訪問到集合,那最好是使用 ArrayList,因為它不考慮線程安全,效率會高些;如果有多個線程會訪問到集合,那最好是使用 Vector,因為不需要我們自己再去考慮和編寫線程安全的代碼。 (2)數據增長: ArrayList 與 Vector 都有一個初始的容量大小,當存儲進它們里面的元素的個數超過了容量時,就需要增加 ArrayList 與 Vector 的存儲空間,每次要增加存儲空間時,不是只增加一個存儲單元,而是增加多個存儲單元,每次增加的存儲單元的個數在內存空間利用與程序效率之間要取得一定的平衡。Vector 默認增長為原來兩倍,而 ArrayList 的增長策略在文檔中沒有明確規定(從源代碼看到的是增長為原來的1.5倍)。 ArrayList 與 Vector 都可以設置初始的空間大小,Vector 還可以設置增長的空間大小,而 ArrayList 沒有提供設置增長空間的方法。 HashMap 和 Hashtable 的區別   總結： hashmap 線程不安全 允許有null的鍵和值 效率高一點、 方法不是Synchronize的要提供外同步 有containsvalue和containsKey方法 HashMap 是java1.2 引進的Map interface 的一個實現 HashMap是Hashtable的輕量級實現 hashtable 線程安全 不允許有null的鍵和值 效率稍低、 方法是是Synchronize的 有contains方法方法 、Hashtable 繼承于Dictionary 類 Hashtable 比HashMap 要舊   List 和Set、Map 區別? Java中的集合包括三大類，它們是Set、List和Map，它們都處于java.util包中，Set、List和Map都是接口，它們有各自的實現類。Set的實現類主要有HashSet和TreeSet，List的實現類主要有ArrayList，Map的實現類主要有HashMap和TreeMap。 　　Set中的對象不按特定方式排序，并且沒有重復對象。但它的有些實現類能對集合中的對象按特定方式排序，例如TreeSet類，它可以按照默認排序，也可以通過實現java.util.Comparator接口來自定義排序方式。 　　List中的對象按照索引位置排序，可以有重復對象，允許按照對象在集合中的索引位置檢索對象，如通過list.get(i)方式來獲得List集合中的元素。 　　Map中的每一個元素包含一個鍵對象和值對象，它們成對出現。鍵對象不能重復，值對象可以重復。 List、Map、Set 三個接口,存取元素時,各有什么特點? list：存儲： 有序的 可重復的 訪問：可以for循環，foreach循環，iterator迭代器 迭代。 set：存儲：無序的 不重復的 訪問：可以foreach循環，iterator迭代器 迭代 map：存儲：存儲的是一對一對的映射 ”key=value“，key值 是無序，不重復的。value值可重復 訪問：可以map中key值轉為為set存儲，然后迭代這個set，用map.get(key)獲取value 也可以 轉換為entry對象 用迭代器迭代 說出 ArrayList,Vector, LinkedList 的存儲性能和特性  ArrayList和Vector都是使用數組方式存儲數據，此數組元素數大于實際存儲的數據以便增加和插入元素，它們都允許直接按序號索引元素，但是插入元素要涉及數組元素移動等內存操作，所以索引數據快而插入數據慢，Vector由于使用了synchronized方法（線程安全），通常性能上較ArrayList差，而LinkedList使用雙向鏈表實現存儲，按序號索引數據需要進行前向或后向遍歷，但是插入數據時只需要記錄本項的前后項即可，所以插入速度較快。 去掉一個 Vector 集合中重復的元素 通過Vector.contains（）方法判斷是否包含該元素，如果沒有包含就添加到新的集合當中，適用于數據較小的情況下。 Collection 和 Collections 的區別。 Collection是集合類的上級接口，繼承于它的接口主要有Set和List。 Collections是針對集合類的一個幫助類，它提供了一系列靜態方法實現了對各種集合的排序，搜索和線程安全等操作。 Set 里的元素是不能重復的,那么用什么方法來區分重復與否呢?是用==還是equals()?它們有何區別? set里的元素是不能重復的，用iterator()方法來區分重復與否。 equals 方法（是String類從它的超類Object中繼承的）被用來檢測兩個對象是否相等，即兩個對象的內容是否相等。 ==用于比較引用和比較基本數據類型時具有不同的功能： 比較基本數據類型，如果兩個值相同，則結果為true 而在比較引用時，如果引用指向內存中的同一對象，結果為true HashMap面試題 HashMap的工作原理是近年來常見的Java面試題。幾乎每個Java程序員都知道HashMap，都知道哪里要用HashMap，知道Hashtable和HashMap之間的區別，那么為何這道面試題如此特殊呢？是因為這道題考察的深度很深。這題經常出現在高級或中高級面試中。投資銀行更喜歡問這個問題，甚至會要求你實現HashMap來考察你的編程能力。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復雜。讓我們開始探索的旅程吧！ 先來些簡單的問題 “你用過HashMap嗎？” “什么是HashMap？你為什么用到它？” 幾乎每個人都會回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值，而Hashtable則不能；HashMap是非synchronized;HashMap很快；以及HashMap儲存的是鍵值對等等。這顯示出你已經用過HashMap，而且對它相當的熟悉。但是面試官來個急轉直下，從此刻開始問出一些刁鉆的問題，關于HashMap的更多基礎的細節。面試官可能會問出下面的問題： “你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？” 你也許會回答“我沒有詳查標準的Java API，你可以看看Java源代碼或者Open JDK。”“我可以用Google找到答案。” 但一些面試者可能可以給出答案，“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。”這里關鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當的正確，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始，當面試官加入一些Java程序員每天要碰到的實際場景的時候，錯誤的答案頻現。下個問題可能是關于HashMap中的碰撞探測(collision detection)以及碰撞的解決方法： “當兩個對象的hashcode相同會發生什么？” 從這里開始，真正的困惑開始了，一些面試者會回答因為hashcode相同，所以兩個對象是相等的，HashMap將會拋出異常，或者不會存儲它們。然后面試官可能會提醒他們有equals()和hashCode()兩個方法，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續挺進，他們回答“因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。”這個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結，面試官會繼續問： “如果兩個鍵的hashcode相同，你如何獲取值對象？” 面試者會回答：當我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。 其中一些記得這個重要知識點的面試者會說，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。完美的答案！ 許多情況下，面試者會在這個環節中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現，而equals()方法僅僅在獲取值對象的時候才出現。一些優秀的開發者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。 如果你認為到這里已經完結了，那么聽到下面這個問題的時候，你會大吃一驚。“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。 如果你能夠回答這道問題，下面的問題來了：“你了解重新調整HashMap大小存在什么問題嗎？”你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產生條件競爭(race condition)。 當重新調整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那么就死循環了。這個時候，你可以質問面試官，為什么這么奇怪，要在多線程的環境下使用HashMap呢？：） 熱心的讀者貢獻了更多的關于HashMap的問題： 為什么String, Interger這樣的wrapper類適合作為鍵？ String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。 我們可以使用自定義的對象作為鍵嗎？ 這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。 我們可以使用CocurrentHashMap來代替Hashtable嗎？這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。看看這篇博客查看Hashtable和ConcurrentHashMap的區別。 我個人很喜歡這個問題，因為這個問題的深度和廣度，也不直接的涉及到不同的概念。讓我們再來看看這些問題設計哪些知識點： hashing的概念 HashMap中解決碰撞的方法 equals()和hashCode()的應用，以及它們在HashMap中的重要性 不可變對象的好處 HashMap多線程的條件競爭 重新調整HashMap的大小 總結 HashMap的工作原理 HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發生碰撞了，對象將會儲存在鏈表的下一個節點中。 HashMap在每個鏈表節點中儲存鍵值對對象。 當兩個不同的鍵對象的hashcode相同時會發生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。 因為HashMap的好處非常多，我曾經在電子商務的應用中使用HashMap作為緩存。因為金融領域非常多的運用Java，也出于性能的考慮，我們會經常用到HashMap和ConcurrentHashMap。你可以查看更多的關于HashMap的文章: 請講下Java里面的容器   分兩大類，Map和Collection。而Collection又有子接口List(數據存儲順序和插入順序是一樣的)、Set(里面的元素具有唯一性)   Map是存儲鍵值對的,里面的健不可以重復,但值可以重復 a. 對于List主要有ArrayList和LinkedList兩種實現。實現的數據結構不同，所以主要的區別也都是和數據結構相關的。 ArrayList基于數組，隨機訪問快，而對于中間元素的插入刪除效率比較低，而且需要考慮擴容問題。LinkedList，則 基于鏈表，和ArrayList提到的正相反，隨機訪問慢，但對于中間元素的插入和刪除更有效率。 Set也是一種Collection，和List比起來主要體現在元素唯一性。 請說下Iterator的作用  迭代器可以實現Collection接口的方法，可以一個一個地獲取集合中的元素 在遍歷集合時 可判斷是否有下一個元素 說下ArrayList和LinkedList的區別和聯系，并說明什么情況下用它們  區別:ArrayList用于對象的隨機訪問速度快,沒有順序 LinkedList實現機制是鏈表式的,和順序有關,速度比ArrayList慢 聯系:ArrayList和LinkedList都是List接口的實現類 當要快速獲取一個值時,用ArrayList,用于順序插入操作時,用LinkedList. 說下List，Set，Map三種集合各有什么特征 List集合中的元素可以重復, Set集合中的元素不可以重復 Map集合用鍵-值映射存放對象,Map容器中的鍵對象不能重復,值對象可以重復 HashSet和TreeSet有什么區別，什么時候用它們  區別:HashSet中的元素不能重復,沒有順序 TreeSet中的元素不能重復,但有順序 當集合中的元素需要排序時,用TreeSet 一般情況下用HashSet,因為不需要排序,速度比TreeSet快 什么是泛型，怎么使用的，有什么好處？ 答案  定義一個集合時，可以知道里面定義的是什么類型 使用:在集合類型后面加< 數據類型 > 使用泛型后,從集合中取得元素后就不用再用強轉  什么是for each循環，它可以循環那些數據類型 答案  也可以叫增強型循環，通過對象拿到集合里的值，因為擴展性比較強，建議多使用 可以用來循環集合和數組 比較下集合和數組的優缺點  集合是多個對象的容器,可以將不同數據類型的多個對象組織在一起 數組類型是有相同數據類型的數據集合,數組是很多語言都支持的底層數據結構,性能上是最高的 HashMap與LinkedHashMap,和TreeMap的區別。 共同點：HashMap,LinkedHashMap,TreeMap都屬于Map的實現類. 不同點: 1.HashMap里面存入的鍵值對在取出的時候是隨機的, 2.TreeMap取出來的是排序后的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。 3. LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實現. 在List里面怎么去掉重復的數？ 通過把List里面的數據放入HashSet可以去除重復 HashMap和ArrayList是不是都是線程不安全的？  ArrayList是線程不安全的；HashMap是線程不安全的；還有我們常見的一些JAVA集合都是線程不安全,這樣做是為了提高性能 在JDK5以后提供了線程安全的并發包java.util.concurrent并發包,譬如里面的類CopyOnWriteArrayList,CopyOnWriteArraySet,ConcurrentHashMap等 ArrayList集合加入1萬條數據，應該怎么提高效率 因為ArrayList的底層是數組實現,并且數組的默認值是10,如果插入10000條要不斷的擴容,耗費時間,所以我們調用ArrayList的指定容量的構造器方法ArrayList(int size) 就可以實現不擴容,就提高了性能