## 1\. ArrayList和LinkedList區別 * ArrayList 和 LinkedList 可想從名字分析，它們一個是 Array (動態數組) 的數據結構，一個是 Link (鏈表) 的數據結構，此外，它們兩個都是對 List 接口的實現。前者是數組隊列，相當于動態數組；后者為雙向鏈表結構，也可當作堆棧、隊列、雙端隊列； * **當隨機訪問 List 時**（get和set操作），ArrayList 比 LinkedList的效率更高，因為 LinkedList 是線性的數據存儲方式，所以需要移動指針從前往后依次查找； * **當對數據進行增加和刪除的操作時**（add 和 remove 操作），LinkedList 比 ArrayList 的效率更高，因為 ArrayList 是數組，所以在其中進行增刪操作時，會對操作點之后所有數據的下標索引造成影響，需要進行數據的移動； * **從利用效率來看**，ArrayList 自由性較低，因為它需要手動的設置固定大小的容量，但是它的使用比較方便，只需要創建，然后添加數據，通過調用下標進行使用；而 LinkedList 自由性較高，能夠動態的隨數據量的變化而變化，但是它不便于使用； * ArrayList 主要空間開銷在于需要在 List 列表預留一定空間；而 LinkList 主要控件開銷在于需要存儲結點信息以及結點指針信息。 * **ArrayList、LinkedList 和 Vector如何選擇？** * 當對數據的主要操作為索引或只在集合的末端增加、刪除元素時，使用 ArrayList 或 Vector 效率比較高； * 當對數據的操作主要為制定位置的插入或刪除操作時，使用 LinkedList 效率比較高； * 當在多線程中使用容器時（即多個線程會同時訪問該容器），選用 Vector 較為安全； ## 2\. HashMap和HashTable區別，HashMap的key類型 * **Hash Map和HashTable的區別** * Hashtable 的方法是同步的，HashMap 非同步，所以在多線程場合要手動同步 * Hashtable 不允許 null 值 (key 和 value 都不可以)，HashMap 允許 null 值( key 和 value 都可以)。 * 兩者的遍歷方式大同小異，Hashtable 僅僅比 HashMap 多一個 elements 方法。 * Hashtable?和?HashMap?都能通過 values() 方法返回一個 Collection ，然后進行遍歷處理。 * 兩者也都可以通過 entrySet() 方法返回一個 Set ， 然后進行遍歷處理。 * HashTable 使用 Enumeration，HashMap 使用 Iterator。 * 哈希值的使用不同，Hashtable 直接使用對象的 hashCode。而 HashMap 重新計算hash值，而且用于代替求模。 * Hashtable 中 hash 數組默認大小是11，增加的方式是 old\*2+1。HashMap 中 hash 數組的默認大小是16，而且一定是 2 的指數。 * HashTable 基于 Dictionary 類，而 HashMap 基于 AbstractMap 類 * **HashMap中的key可以是任何對象或數據類型嗎** * 可以為null，但不能是可變對象，如果是可變對象的話，對象中的屬性改變，則對象 HashCode 也進行相應的改變，導致下次無法查找到已存在Map中的數據。 * 如果可變對象在 HashMap 中被用作鍵，那就要小心在改變對象狀態的時候，不要改變它的哈希值了。我們只需要保證成員變量的改變能保證該對象的哈希值不變即可。 * **HashTable是線程安全的么** * HashTable 是線程安全的，其實現是在對應的方法上添加了 synchronized 關鍵字進行修飾，由于在執行此方法的時候需要獲得對象鎖，則執行起來比較慢。所以現在如果為了保證線程安全的話，使用 CurrentHashMap。 ## 3\. HashMap和ConcurrentHashMap * **HashMap和Concurrent?HashMap區別？** * HashMa p是非線程安全的，CurrentHashMap 是線程安全的。 * ConcurrentHashMap 將整個 Hash 桶進行了分段 segment，也就是將這個大的數組分成了幾個小的片段segment，而且每個小的片段 segment 上面都有鎖存在，那么在插入元素的時候就需要先找到應該插入到哪一個片段 segment，然后再在這個片段上面進行插入，而且這里還需要獲取 segment 鎖。 * ConcurrentHashMap 讓鎖的粒度更精細一些，并發性能更好。 * **ConcurrentHashMap?線程安全嗎，?ConcurrentHashMap如何保證?線程安全？** * HashTable 容器在競爭激烈的并發環境下表現出效率低下的原因是所有訪問 HashTable 的線程都必須競爭同一把鎖，那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數據，那么當多線程訪問容器里不同數據段的數據時，線程間就不會存在鎖競爭，從而可以有效的提高并發訪問效率，這就是 ConcurrentHashMap 所使用的**分段鎖**，首先將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問。 * get 操作的高效之處在于整個 get 過程不需要加鎖，除非讀到的值是空的才會加鎖重讀。**get 方法里將要使用的共享變量都定義成 volatile**，如用于統計當前 Segement 大小的 count 字段和用于存儲值的 HashEntry 的 value。定義成 volatile 的變量，能夠在線程之間保持可見性，能夠被多線程同時讀，并且保證不會讀到過期的值，但是只能被單線程寫（有一種情況可以被多線程寫，就是寫入的值不依賴于原值），在 get 操作里只需要讀不需要寫共享變量 count 和 value，所以可以不用加鎖。 * put 方法首先定位到 Segment，然后在 Segment 里進行插入操作。 * 插入操作需要經歷兩個步驟：（1）判斷是否需要對 Segment 里的 HashEntry 數組進行擴容；（2）定位添加元素的位置然后放在HashEntry數組里。 ## 4\. Hashtable的原理 **Hashtable 使用鏈地址法進行元素存儲，通過一個實際的例子來演示一下插入元素的過程：** 假設我們現在 Hashtable 的容量為 5，已經存在了 (5,5)，(13,13)，(16,16)，(17,17)，(21,21) 這 5 個鍵值對，目前他們在 Hashtable 中的位置如下： [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable1.png) 現在，我們插入一個新的鍵值對，put(16,22)，假設 key=16 的索引為 1.但現在索引 1 的位置有兩個 Entry 了，所以程序會對鏈表進行迭代。迭代的過程中，發現其中有一個 Entry 的 key 和我們要插入的鍵值對的 key 相同，所以現在會做的工作就是將 newValue=22 替換 oldValue=16，然后返回 oldValue = 16. [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable2.png) 然后我們現在再插入一個，put(33,33)，key=33 的索引為 3，并且在鏈表中也不存在 key=33 的 Entry，所以將該節點插入鏈表的第一個位置。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable3.png) **Hashtable 與 HashMap 的簡單比較** 1. HashTable 基于 Dictionary 類，而 HashMap 是基于 AbstractMap。Dictionary 是任何可將鍵映射到相應值的類的抽象父類，而 AbstractMap 是基于 Map 接口的實現，它以最大限度地減少實現此接口所需的工作。 2. HashMap 的 key 和 value 都允許為 null，而 Hashtable 的 key 和 value 都不允許為 null。HashMap 遇到 key 為 null 的時候，調用 putForNullKey 方法進行處理，而對 value 沒有處理；Hashtable遇到 null，直接返回 NullPointerException。 3. **Hashtable 方法是同步，而HashMap則不是**。我們可以看一下源碼，Hashtable 中的幾乎所有的 public 的方法都是 synchronized 的，而有些方法也是在內部通過 synchronized 代碼塊來實現。所以有人一般都建議如果是涉及到多線程同步時采用 HashTable，沒有涉及就采用 HashMap，但是在 Collections 類中存在一個靜態方法：**synchronizedMap()**，該方法創建了一個線程安全的 Map 對象，并把它作為一個封裝的對象來返回。 **參考資料：** * [Hashtable 的實現原理 - Java 集合學習指南 - 極客學院Wiki](http://wiki.jikexueyuan.com/project/java-collection/hashtable.html) ## 5\. Hash沖突的解決辦法 * 鏈地址法 * 開放地址法（向后一位） * 線性探測 * 平方探測 * 二次哈希 * 再哈希法 ## 6\. 什么是迭代器 　　Java 集合框架的集合類，我們有時候稱之為容器。容器的種類有很多種，比如 ArrayList、LinkedList、HashSet...，每種容器都有自己的特點，ArrayList 底層維護的是一個數組；LinkedList 是鏈表結構的；HashSet 依賴的是哈希表，每種容器都有自己特有的數據結構。 　　因為容器的內部結構不同，很多時候可能不知道該怎樣去遍歷一個容器中的元素。所以為了使對容器內元素的操作更為簡單，Java 引入了迭代器模式！ 　　把訪問邏輯從不同類型的集合類中抽取出來，從而避免向外部暴露集合的內部結構。 　　**迭代器模式**：就是提供一種方法對一個容器對象中的各個元素進行訪問，而又不暴露該對象容器的內部細。 ~~~java public static void main(String[] args) { // 使用迭代器遍歷ArrayList集合 Iterator<String> listIt = list.iterator(); while(listIt.hasNext()){ System.out.println(listIt.hasNext()); } // 使用迭代器遍歷Set集合 Iterator<String> setIt = set.iterator(); while(setIt.hasNext()){ System.out.println(listIt.hasNext()); } // 使用迭代器遍歷LinkedList集合 Iterator<String> linkIt = linkList.iterator(); while(linkIt.hasNext()){ System.out.println(listIt.hasNext()); } } ~~~ 參考資料： * [深入理解Java中的迭代器 - Mr·Dragon - 博客園](https://www.cnblogs.com/zyuze/p/7726582.html) ## 7\. 構造相同hash的字符串進行攻擊，這種情況應該怎么處理？JDK7如何處理 **攻擊原理：** 　　當客戶端發送一個請求到服務器，如果該請求中帶有參數，服務器端會將 參數名-參數值 作為 key-value 保存在 HashMap 中。如果有人惡意構造請求，在請求中加入大量相同 hash 值的 String 參數名（key），那么在服務器端用于存儲這些 key-value 對的 HashMap 會被強行退化成鏈表，如圖： [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hash-to-badlink.png) 如果數據量足夠大，那么在查找，插入時會占用大量 CPU，達到拒絕服務攻擊的目的。 **怎么處理** 1. 限制 POST 和 GET 請求的參數個數 2. 限制 POST 請求的請求體大小 3. Web Application FireWall（WAF） **JDK7如何處理** HashMap 會動態的使用一個專門 TreeMap 實現來替換掉它。 ## 8\. Hashmap為什么大小是2的冪次 首先來看一下 hashmap 的 put 方法的源碼 ~~~java public V put(K key, V value) { if (key == null) return putForNullKey(value); //將空key的Entry加入到table[0]中 int hash = hash(key.hashCode()); //計算key.hashcode()的hash值，hash函數由hashmap自己實現 int i = indexFor(hash, table.length); //獲取將要存放的數組下標 /* * for中的代碼用于：當hash值相同且key相同的情況下，使用新值覆蓋舊值（其實就是修改功能） */ //注意：for循環在第一次執行時就會先判斷條件 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //hash值相同且key相同的情況下，使用新值覆蓋舊值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //e.recordAccess(this); return oldValue;//返回舊值 } } modCount++; addEntry(hash, key, value, i);//增加一個新的Entry到table[i] return null;//如果沒有與傳入的key相等的Entry，就返回null } ~~~ ~~~java /** * "按位與"來獲取數組下標 */ static int indexFor(int h, int length) { return h & (length - 1); } ~~~ **hashmap 始終將自己的桶保持在2n，這是為什么？indexFor這個方法解釋了這個問題** 大家都知道計算機里面位運算是基本運算，位運算的效率是遠遠高于取余 % 運算的 舉個例子：2n轉換成二進制就是 1+n 個 0，減 1 之后就是 0+n個1，如16 -> 10000，15 -> 01111 那么根據 & 位運算的規則，都為 1 (真)時，才為 1，那 0≤運算后的結果≤15，假設 h 15，運算后的結果就是最后四位二進制做 & 運算后的值，最終，就是 % 運算后的余數。 當容量一定是 2n時，h & (length - 1) == h % length