1、Java的數據結構相關的類實現原理List接口 List是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數組下標）來訪問List中的元素，這類似于Java的數組。 和下面要提到的Set不同，List允許有相同的元素。 除了具有Collection接口必備的iterator()方法外，List還提供一個listIterator()方法，返回一個ListIterator接口，和標準的Iterator接口相比，ListIterator多了一些add()之類的方法，允許添加，刪除，設定元素，還能向前

2、或向后遍歷。 實現List接口的常用類有LinkedList，ArrayList，Vector和Stack。 LinkedListList 接口的鏈接列表實現。實現所有可選的列表操作，并且允許所有元素（包括 null）。除了實現 List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。此類實現 Deque 接口，為 add、poll&

3、#160;提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。注意，此實現不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須 保持外部同步。（結構修改指添加或刪除一個或多個元素的任何操作；僅設置元素的值不是結構修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在創建時完成這一操作，以防止對

4、列表進行意外的不同步訪問，如下所示：                    List list = Collections.synchronizedList(new LinkedList(.);此類的 iterator 和 listIterator 方法返回的迭代器是快速失敗 的：在迭代器創建之后，如果從結構上對列表進行修改，除非通過迭代器自身的remove

5、 或 add 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證?？焖偈〉鞅M最大努力拋出ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。ArrayList   Ar

6、rayList是List接口的可變數組的實現。實現了所有可選列表操作，并允許包括 null 在內的所有元素。除了實現 List 接口外，此類還提供一些方法來操作內部用來存儲列表的數組的大小。   每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來數據向新數組的重新拷貝，因此，如果可預知數據量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減

7、少遞增式再分配的數量。    注意，此實現不是同步的。如果多個線程同時訪問一個ArrayList實例，而其中至少一個線程從結構上修改了列表，那么它必須保持外部同步。HashMap    HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。HashMap也不例外。HashMap實際上是一個“鏈表的數組”的數據結構，每個元素存放鏈表頭結點的數組，即數組和鏈表的結合體。HashMap底層就是一個數組結構，數組中的每一

8、項又是一個鏈表。當新建一個HashMap的時候，就會初始化一個數組。當我們往HashMap中put元素的時候，先根據key的hashCode重新計算hash值，根據hash值得到這個元素在數組中的位置（即下標），如果數組該位置上已經存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數組該位置上沒有元素，就直接將該元素放到此數組中的該位置上。當系統決定存儲HashMap中的key-value對時，完全沒有考慮Entry中的value，僅僅只是根據key來計算并決定每個Entry的存儲位置。我們完全可以把 Map 集合中的&#

9、160;value 當成 key 的附屬，當系統決定了 key 的存儲位置之后，value 隨之保存在那里即可。在HashMap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置。如何計算這個位置就是hash算法。前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap里面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。歸納起來

10、簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，也會根據hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。Has

11、hSet HashSet實現Set接口，由哈希表（實際上是一個HashMap實例）支持。它不保證set 的迭代順序；特別是它不保證該順序恒久不變。此類允許使用null元素。HashSet實現Set接口，由哈希表（實際上是一個HashMap實例）支持。它不保證set 的迭代順序；特別是它不保證該順序恒久不變。此類允許使用null元素。HashSet中不允許有重復元素，這是因為HashSet是基于HashMap實現的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是統一的一個private static final Object PRE

12、SENT = new Object();。HashSet跟HashMap一樣，都是一個存放鏈表的數組。HashSet中add方法調用的是底層HashMap中的put()方法，而如果是在HashMap中調用put，首先會判斷key是否存在，如果key存在則修改value值，如果key不存在這插入這個key-value。而在set中，因為value值沒有用，也就不存在修改value值的說法，因此往HashSet中添加元素，首先判斷元素（也就是key）是否存在，如果不存在這插入，如果存在著不插入，這樣HashSet中就不存在重復值。HashMap是不是有序的HashSet 和Hashmap分別是Se

13、t接口和Map接口的實現類，運用哈希算法來存取元素，也就是它們中的對象不按特定方式排序； 有沒有有順序的Map實現類TreeMap和LinkedHashMapLinkedHashMapTreeMap?你覺得它們兩個哪個的有序實現比較好？LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只

14、和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。 TreeMap實現SortMap接口，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。TreeMap取出來的是排序后的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實現,它還可以按讀取順序來排列，像連接池中可以應用。你覺得還有沒有比它更好或者更高效的實現方式？?Java的虛擬機的

15、內容。這部分主要包括三部分，GC、類加載機制，以及內存。GC部分什么時候一個對象會被GC？1. 什么樣的對象是垃圾？一般來說，所有指向對象的引用都已失效，不可能再有程序能調用到這個對象，那么這個對象就成了垃圾，應該被回收。1.1 根據這個思路，很容易就能想到用引用計數的辦法來確定一個對象是否是垃圾。即每當多一個引用指向對象時，引用計數加一，每當少一個引用指向對象時，引用計數減一，引用計數減到零，對象就可以被回收了。1.2 然而引用計數有一個致命問題不好解決，就是循環引用的問題。比如說一個循環鏈表，他們循環引用者，引用計數永遠不會為零，但是實際上程序已經不能訪問他們了，他們應該被回收。1.3 所

16、以Java實際上是使用基于GC Roots的可達性分析，什么是GC Roots？所有類的靜態變量，每個線程調用棧上的本地變量。（實際上我們編程時也是要從這些地方開始訪問數據），所有這些對象，以及被這些對象所指向的對象，都是活的對象?；畹膶ο笏赶虻膶ο笠彩腔畹膶ο?。1.4 所以只要在GC的時刻，讓程序暫停運行，然后從GC Roots開始分析，最后沒有被標記為活對象的對象就是垃圾了。什么時候觸發GC1.當應用程序空閑時,即沒有應用線程在運行時,GC會被調用。因為GC在優先級最低的線程中進行,所以當應用忙時,GC線程就不會被調用,但以下條件除外。2.Java堆內存不足時,GC會被調用。當應用線程在

17、運行,并在運行過程中創建新對象,若這時內存空間不足,JVM就會強制地調用GC線程,以便回收內存用于新的分配。若GC一次之后仍不能滿足內存分配的要求,JVM會再進行兩次GC作進一步的嘗試,若仍無法滿足要求,則 JVM將報“out of memory”的錯誤,Java應用將停止。GC算法標記-清除算法 (Mark-Sweep)標記-清除算法將垃圾回收分為兩個階段：標記階段和清除階段。一種可行的實現是，在標記階段首先通過根節點，標記所有從根節點開始的較大對象。因此，未被標記的對象就是未被引用的垃圾對象。然后，在清除階段，清除所有未被標記的對象。該算法最大的問題是存在大量的空間碎片，因為回收后的空間是

18、不連續的。在對象的堆空間分配過程中，尤其是大對象的內存分配，不連續的內存空間的工作效率要低于連續的空間。復制算法 (Copying)將現有的內存空間分為兩快，每次只使用其中一塊，在垃圾回收時將正在使用的內存中的存活對象復制到未被使用的內存塊中，之后，清除正在使用的內存塊中的所有對象，交換兩個內存的角色，完成垃圾回收。如果系統中的垃圾對象很多，復制算法需要復制的存活對象數量并不會太大。因此在真正需要垃圾回收的時刻，復制算法的效率是很高的。又由于對象在垃圾回收過程中統一被復制到新的內存空間中，因此，可確保回收后的內存空間是沒有碎片的。該算法的缺點是將系統內存折半。Java 的新生代串行垃圾回收器中

19、使用了復制算法的思想。新生代分為 eden 空間、from 空間、to 空間 3 個部分。其中 from 空間和 to 空間可以視為用于復制的兩塊大小相同、地位相等，且可進行角色互換的空間塊。from 和 to 空間也稱為 survivor 空間，即幸存者空間，用于存放未被回收的對象。在垃圾回收時，eden 空間中的存活對象會被復制到未使用的 survivor 空間中 (假設是 to)，正在使用的 survivor 空間 (假設是 from) 中的年輕對象也會被復制到 to 空間中 (大對象，或者老年對象會直接進入老年帶，如果 to 空間已滿，則對象也會直接進入老年代)。此時，eden 空間和

20、 from 空間中的剩余對象就是垃圾對象，可以直接清空，to 空間則存放此次回收后的存活對象。這種改進的復制算法既保證了空間的連續性，又避免了大量的內存空間浪費。標記-壓縮算法 (Mark-Compact)復制算法的高效性是建立在存活對象少、垃圾對象多的前提下的。這種情況在年輕代經常發生，但是在老年代更常見的情況是大部分對象都是存活對象。如果依然使用復制算法，由于存活的對象較多，復制的成本也將很高。標記-壓縮算法是一種老年代的回收算法，它在標記-清除算法的基礎上做了一些優化。也首先需要從根節點開始對所有可達對象做一次標記，但之后，它并不簡單地清理未標記的對象，而是將所有的存活對象壓縮到內存的一

21、端。之后，清理邊界外所有的空間。這種方法既避免了碎片的產生，又不需要兩塊相同的內存空間，因此，其性價比比較高。分代 (Generational Collecting)根據垃圾回收對象的特性，不同階段最優的方式是使用合適的算法用于本階段的垃圾回收，分代算法即是基于這種思想，它將內存區間根據對象的特點分成幾塊，根據每塊內存區間的特點，使用不同的回收算法，以提高垃圾回收的效率。以 Hot Spot 虛擬機為例，它將所有的新建對象都放入稱為年輕代的內存區域，年輕代的特點是對象會很快回收，因此，在年輕代就選擇效率較高的復制算法。當一個對象經過幾次回收后依然存活，對象就會被放入稱為老生代的內存空間。在老生

22、代中，幾乎所有的對象都是經過幾次垃圾回收后依然得以幸存的。因此，可以認為這些對象在一段時期內，甚至在應用程序的整個生命周期中，將是常駐內存的。如果依然使用復制算法回收老生代，將需要復制大量對象。再加上老生代的回收性價比也要低于新生代，因此這種做法也是不可取的。根據分代的思想，可以對老年代的回收使用與新生代不同的標記-壓縮算法，以提高垃圾回收效率。GC策略Serial(串行GC)收集器Serial收集器是一個新生代收集器，單線程執行，使用復制算法。它在進行垃圾收集時，必須暫停其他所有的工作線程(用戶線程)。是Jvm client模式下默認的新生代收集器。對于限定單個CPU的環境來說，Serial

23、收集器由于沒有線程交互的開銷，專心做垃圾收集自然可以獲得最高的單線程收集效率。ParNew(并行GC)收集器ParNew收集器其實就是serial收集器的多線程版本，除了使用多條線程進行垃圾收集之外，其余行為與Serial收集器一樣。Parallel Scavenge(并行回收GC)收集器Parallel Scavenge收集器也是一個新生代收集器，它也是使用復制算法的收集器，又是并行多線程收集器。parallel Scavenge收集器的特點是它的關注點與其他收集器不同，CMS等收集器的關注點是盡可能地縮短垃圾收集時用戶線程的停頓時間，而parallel Scavenge收集器的目標則是達到

24、一個可控制的吞吐量。吞吐量= 程序運行時間/(程序運行時間 + 垃圾收集時間)，虛擬機總共運行了100分鐘。其中垃圾收集花掉1分鐘，那吞吐量就是99%。Serial Old(串行GC)收集器Serial Old是Serial收集器的老年代版本，它同樣使用一個單線程執行收集，使用“標記-整理”算法。主要使用在Client模式下的虛擬機。Parallel Old(并行GC)收集器Parallel Old是Parallel Scavenge收集器的老年代版本，使用多線程和“標記-整理”算法。CMS(并發GC)收集器CMS(Concurrent Mark Sweep)收集器是一種以獲取最短回收停頓時間

25、為目標的收集器。CMS收集器是基于“標記-清除”算法實現的，整個收集過程大致分為4個步驟：.初始標記(CMS initial mark).并發標記(CMS concurrenr mark).重新標記(CMS remark).并發清除(CMS concurrent sweep) 其中初始標記、重新標記這兩個步驟任然需要停頓其他用戶線程。初始標記僅僅只是標記出GC ROOTS能直接關聯到的對象，速度很快，并發標記階段是進行GC ROOTS 根搜索算法階段，會判定對象是否存活。而重新標記階段則是為了修正并發標記期間，因用戶程序繼續運行而導致標記產生變動的那一部分對象的標記記錄，這個階段的停頓時間會被

26、初始標記階段稍長，但比并發標記階段要短。 由于整個過程中耗時最長的并發標記和并發清除過程中，收集器線程都可以與用戶線程一起工作，所以整體來說，CMS收集器的內存回收過程是與用戶線程一起并發執行的。CMS收集器的優點：并發收集、低停頓，但是CMS還遠遠達不到完美，器主要有三個顯著缺點：CMS收集器對CPU資源非常敏感。在并發階段，雖然不會導致用戶線程停頓，但是會占用CPU資源而導致引用程序變慢，總吞吐量下降。CMS默認啟動的回收線程數是：(CPU數量+3) / 4。CMS收集器無法處理浮動垃圾，可能出現“Concurrent Mode Failure“，失敗后而導致另一次Full GC的產生。由

27、于CMS并發清理階段用戶線程還在運行，伴隨程序的運行自熱會有新的垃圾不斷產生，這一部分垃圾出現在標記過程之后，CMS無法在本次收集中處理它們，只好留待下一次GC時將其清理掉。這一部分垃圾稱為“浮動垃圾”。也是由于在垃圾收集階段用戶線程還需要運行，即需要預留足夠的內存空間給用戶線程使用，因此CMS收集器不能像其他收集器那樣等到老年代幾乎完全被填滿了再進行收集，需要預留一部分內存空間提供并發收集時的程序運作使用。在默認設置下，CMS收集器在老年代使用了68%的空間時就會被激活，也可以通過參數-XX:CMSInitiatingOccupancyFraction的值來提供觸發百分比，以降低內存回收次數

28、提高性能。要是CMS運行期間預留的內存無法滿足程序其他線程需要，就會出現“Concurrent Mode Failure”失敗，這時候虛擬機將啟動后備預案：臨時啟用Serial Old收集器來重新進行老年代的垃圾收集，這樣停頓時間就很長了。所以說參數-XX:CMSInitiatingOccupancyFraction設置的過高將會很容易導致“Concurrent Mode Failure”失敗，性能反而降低。最后一個缺點，CMS是基于“標記-清除”算法實現的收集器，使用“標記-清除”算法收集后，會產生大量碎片?？臻g碎片太多時，將會給對象分配帶來很多麻煩，比如說大對象，內存空間找不到連續的空間來

29、分配不得不提前觸發一次Full GC。為了解決這個問題，CMS收集器提供了一個-XX:UseCMSCompactAtFullCollection開關參數，用于在Full GC之后增加一個碎片整理過程，還可通過-XX:CMSFullGCBeforeCompaction參數設置執行多少次不壓縮的Full GC之后，跟著來一次碎片整理過程。G1收集器G1(Garbage First)收集器是JDK1.7提供的一個新收集器，G1收集器基于“標記-整理”算法實現，也就是說不會產生內存碎片。還有一個特點之前的收集器進行收集的范圍都是整個新生代或老年代，而G1將整個Java堆(包括新生代，老年代)。類加載機

30、制Java的類加載器都有哪些？（1）啟動類加載器（Bootstrap ClassLoader） 這個類加載器負責將存放在JAVA_HOME/lib下的，或者被-Xbootclasspath參數所指定的路徑中的，并且是虛擬機識別的類庫加載到虛擬機內存中。啟動類加載器無法被Java程序直接引用。（2）擴展類加載器（Extension ClassLoader）這個加載器負責加載JAVA_HOME/lib/ext目錄中的，或者被java.ext.dirs系統變量所指定的路徑中的所有類庫，開發者可以直接使用擴展類加載器（3）應用程序類加載器（Application ClassLoader）這個加載器是ClassLoader中getSystemClassLoader()方法的返回值，所以一般也稱它為系統類加載器。它負責加載用戶類路徑（Classpath）上所指定的類庫，可直接使用這個加載器，如果應用程序沒有自定義自己的類加載器，一般情況下這個就是程序中默認的類加載器類加載之間的父子關系是怎樣的？Bootstrap沒有父加載器，Extension類加載器的父加載器為Bootstrap，Application類加載器的父加載器為Extension。什么是雙親委派模型雙親委派模型要求除了頂層的啟動類加載器