二幅恋、容器
1.java 容器都有哪些？
主要有Collection和Map兩個(gè)接口泵肄。
Collection的子類有Set和List捆交。其中Set的實(shí)現(xiàn)類有HashSet、TreeSet腐巢。List的實(shí)現(xiàn)類有ArrayList品追、LinkedList、Vector冯丙。
Map的實(shí)現(xiàn)類有HashMap肉瓦、HashTable、TreeMap胃惜，HashMap的子類有LinkedHashMap泞莉。Map的子類有ConcurrentMap，ConcurrentMap的實(shí)現(xiàn)類是ConcurrentHashMap船殉。
2.Collection 和 Collections 有什么區(qū)別鲫趁？
Collection是集合接口，Collections是一個(gè)工具類利虫，里面提供了許多操作集合的方法挨厚。比如判空、排序等糠惫。
3.List疫剃、Set、Map 之間的區(qū)別是什么硼讽？
List和Set都是Collection的子類慌申，Map接口與Collection是同級的。
4.HashMap 和 Hashtable 有什么區(qū)別理郑？
1.HashMap類大致相當(dāng)于哈希表蹄溉，但它是非同步的，并且允許空值您炉。(HashMap允許空值作為鍵和值柒爵，而哈希表不允許空)。
2.主要之一HashMap與Hashtable的區(qū)別是HashMap是非同步的赚爵，而Hashtable是同步的棉胀，這意味著哈希表線程安全法瑟，可以在多個(gè)線程之間共享，但是HashMap如果沒有適當(dāng)?shù)耐窖渖荩筒荒茉诙鄠€(gè)線程之間共享霎挟。Java 5介紹ConcurrentHashMap它是Hashtable的另一種選擇，它提供了比Java中的Hashtable更好的可伸縮性麻掸。
3.HashMap和Hashtable之間的另一個(gè)顯著區(qū)別是酥夭，HashMap中的迭代器是失敗快速迭代器，而Hashtable的枚舉器不是脊奋，如果任何其他線程通過添加或刪除Iterator自己的remove()方法之外的任何元素在結(jié)構(gòu)上修改映射熬北，則拋出ConcurrentModificationException。但是這不是一種有保證的行為诚隙，JVM將盡最大努力來完成讶隐。這也是Java中枚舉和迭代器之間的一個(gè)重要區(qū)別。
- Hashtable和HashMap之間一個(gè)更顯著的區(qū)別是久又，由于線程安全性和同步性巫延，如果在單線程環(huán)境中使用，Hashtable比HashMap慢得多地消。因此炉峰，如果您不需要同步，并且HashMap僅由一個(gè)線程使用犯建，那么它的性能將優(yōu)于Java中的Hashtable讲冠。
- HashMap不能保證映射的順序在一段時(shí)間內(nèi)保持不變瓜客。
（Java迭代器分為快速失敗和安全失敗适瓦。快速失敗是指運(yùn)行中發(fā)生錯(cuò)誤谱仪，會(huì)立即停止操作玻熙，并暴露錯(cuò)誤。安全失敗是指發(fā)生錯(cuò)誤時(shí)不會(huì)停止運(yùn)行疯攒，因?yàn)樗窃诩系目寺ο蟮泥滤妫匀魏螌υ蠈ο蟮慕Y(jié)構(gòu)性修改都會(huì)被迭代器忽略，但是這類迭代器有一些缺點(diǎn)敬尺，其一是它不能保證你迭代時(shí)獲取的是最新數(shù)據(jù)枚尼，因?yàn)榈鲃?chuàng)建之后對集合的任何修改都不會(huì)在該迭代器中更新，還有一個(gè)缺點(diǎn)就是創(chuàng)建克隆對象在時(shí)間和內(nèi)存上都會(huì)增加一些負(fù)擔(dān)砂吞。ArrayList署恍，Vector，HashMap等集合返回的迭代器都是快速失敗類型的蜻直。ConcurrentHashMap返回的迭代器是安全失敗迭代器盯质。）
5.如何決定使用 HashMap 還是 TreeMap袁串？
TreeMap<K,V>的Key值是要求實(shí)現(xiàn)java.lang.Comparable，所以迭代的時(shí)候TreeMap默認(rèn)是按照Key值升序排序的呼巷；TreeMap的實(shí)現(xiàn)是基于紅黑樹結(jié)構(gòu)囱修。適用于按自然順序或自定義順序遍歷鍵（key）。
HashMap<K,V>的Key值實(shí)現(xiàn)散列hashCode()王悍，分布是散列的破镰、均勻的，不支持排序配名；數(shù)據(jù)結(jié)構(gòu)主要是桶(數(shù)組)啤咽，鏈表或紅黑樹。適用于在Map中插入渠脉、刪除和定位元素宇整。
如果你需要得到一個(gè)有序的結(jié)果時(shí)就應(yīng)該使用TreeMap（因?yàn)镠ashMap中元素的排列順序是不固定的）。除此之外芋膘，由于HashMap有更好的性能鳞青，所以大多不需要排序的時(shí)候我們會(huì)使用HashMap。
6.說一下HashMap的實(shí)現(xiàn)原理为朋？
JDK1.8之前的版本臂拓，HashMap是使用entry數(shù)組加鏈表的形式實(shí)現(xiàn)的。Map中的key和value以entry的形式习寸，保存在數(shù)組中胶惰。而在數(shù)組中的位置是由key的hashcode計(jì)算得到的。如果兩個(gè)key通過計(jì)算得出的hashcode相同了霞溪，發(fā)生了哈希沖突孵滞，hashmap使用鏈表解決沖突。將數(shù)組中的entry設(shè)置為新值的next鸯匹。比如A和B都hash后都映射到下標(biāo)i中坊饶，之前已經(jīng)有A了，當(dāng)map.put(B)時(shí)殴蓬，將B放到下標(biāo)i中匿级，A則為B的next，所以新值存放在數(shù)組中染厅，舊值在新值的鏈表上痘绎。
JDK1.8版本，采用entry數(shù)組+鏈表+紅黑樹的形式肖粮。當(dāng)同一個(gè)哈市值得節(jié)點(diǎn)數(shù)不小于8的時(shí)候孤页，將不再以單鏈表的形式存儲(chǔ)，而是改為紅黑樹尿赚。
1）介紹HashMap：
按照特性來說明一下：儲(chǔ)存的是鍵值對散庶，線程不安全蕉堰，非Synchronied，儲(chǔ)存的比較快悲龟，能夠接受null屋讶。
按照工作原理來敘述一下：Map的put（key，value）來儲(chǔ)存元素须教，通過get（key）來得到value值皿渗，通過hash算法來計(jì)算hascode值，用hashCode標(biāo)識Entry在bucket中存儲(chǔ)的位置轻腺，儲(chǔ)存結(jié)構(gòu)就算哈希表乐疆。
“2）你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎贬养？”
“HashMap是基于hashing的原理挤土，我們使用put(key, value)存儲(chǔ)對象到HashMap中，使用get(key)從HashMap中獲取對象误算。
當(dāng)我們給put()方法傳遞鍵和值時(shí)仰美，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲(chǔ)存Entry對象儿礼。
”這里關(guān)鍵點(diǎn)在于指出咖杂，HashMap是在bucket中儲(chǔ)存鍵對象和值對象，作為Map.Entry蚊夫。
這一點(diǎn)有助于理解獲取對象的邏輯诉字。如果你沒有意識到這一點(diǎn)，或者錯(cuò)誤的認(rèn)為僅僅只在bucket中存儲(chǔ)值的話知纷，你將不會(huì)回答如何從HashMap中獲取對象的邏輯壤圃。這個(gè)答案相當(dāng)?shù)恼_，也顯示出面試者確實(shí)知道hashing以及HashMap的工作原理屈扎。
3）提問：兩個(gè)hashcode相同的時(shí)候會(huì)發(fā)生說明埃唯？
hashcode相同撩匕，bucket的位置會(huì)相同鹰晨，也就是說會(huì)發(fā)生碰撞，哈希表中的結(jié)構(gòu)其實(shí)有鏈表（LinkedList）止毕，這種沖突通過將元素儲(chǔ)存到LinkedList中模蜡，解決碰撞。儲(chǔ)存順序是放在表頭扁凛。
4）如果兩個(gè)鍵的hashcode相同忍疾，如何獲取值對象？
如果兩個(gè)鍵的hashcode相同谨朝，即找到bucket位置之后卤妒，我們通過key.equals（）找到鏈表LinkedList中正確的節(jié)點(diǎn)甥绿，最終找到要找的值對象。
一些優(yōu)秀的開發(fā)者會(huì)指出使用不可變的则披、聲明作final的對象共缕，并且采用合適的equals()和hashCode()方法的話，將會(huì)減少碰撞的發(fā)生士复，提高效率图谷。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個(gè)獲取對象的速度阱洪，使用String便贵，Interger這樣的wrapper類作為鍵是非常好的選擇。
5）如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量冗荸？怎么辦承璃？
HashMap里面默認(rèn)的負(fù)載因子大小為0.75，也就是說蚌本，當(dāng)一個(gè)map填滿了75%的bucket時(shí)候绸硕，和其它集合類(如ArrayList等)一樣，將會(huì)創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組魂毁，來重新調(diào)整map的大小玻佩，并將原來的對象放入新的bucket數(shù)組中。這個(gè)過程叫作rehashing席楚，因?yàn)樗{(diào)用hash方法找到新的bucket位置咬崔。
6）重新調(diào)整HashMap大小的話會(huì)出現(xiàn)什么問題？
多線程情況下會(huì)出現(xiàn)競爭問題烦秩，因?yàn)槟阍谡{(diào)節(jié)的時(shí)候垮斯，LinkedList儲(chǔ)存是按照順序儲(chǔ)存，調(diào)節(jié)的時(shí)候回將原來最先儲(chǔ)存的元素（也就是最下面的）遍歷只祠，多線程就好試圖重新調(diào)整兜蠕，這個(gè)時(shí)候就會(huì)出現(xiàn)死循環(huán)。
當(dāng)多線程的情況下抛寝，可能產(chǎn)生條件競爭(race condition)熊杨。
當(dāng)重新調(diào)整HashMap大小的時(shí)候，確實(shí)存在條件競爭盗舰，因?yàn)槿绻麅蓚€(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了晶府，它們會(huì)同時(shí)試著調(diào)整大小。在調(diào)整大小的過程中钻趋，存儲(chǔ)在鏈表中的元素的次序會(huì)反過來川陆，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候，HashMap并不會(huì)將元素放在鏈表的尾部蛮位，而是放在頭部较沪，這是為了避免尾部遍歷(tail traversing)鳞绕。如果條件競爭發(fā)生了，那么就死循環(huán)了尸曼。
7）HashMap在并發(fā)執(zhí)行put操作猾昆，會(huì)引起死循環(huán)，為什么骡苞？
是因?yàn)槎嗑€程會(huì)導(dǎo)致hashmap的node鏈表形成環(huán)形鏈表垂蜗，一旦形成環(huán)形鏈表，node 的next節(jié)點(diǎn)永遠(yuǎn)不為空解幽，就會(huì)產(chǎn)生死循環(huán)獲取node贴见。從而導(dǎo)致CPU利用率接近100%。
8）為什么String, Interger這樣的wrapper類適合作為鍵躲株？
因?yàn)樗麄円话悴皇遣豢勺兊钠浚创a上面final，使用不可變類霜定，而且重寫了equals和hashcode方法档悠，避免了鍵值對改寫。提高HashMap性能望浩。
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了辖所，而且String最為常用。因?yàn)镾tring是不可變的磨德，也是final的缘回，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個(gè)特點(diǎn)典挑。不可變性是必要的酥宴，因?yàn)闉榱艘?jì)算hashCode()，就要防止鍵值改變您觉，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話拙寡，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優(yōu)點(diǎn)如線程安全琳水。如果你可以僅僅通過將某個(gè)field聲明成final就能保證hashCode是不變的肆糕，那么請這么做吧。因?yàn)楂@取對象的時(shí)候要用到equals()和hashCode()方法炫刷，那么鍵對象正確的重寫這兩個(gè)方法是非常重要的擎宝。如果兩個(gè)不相等的對象返回不同的hashcode的話郁妈，那么碰撞的幾率就會(huì)小些浑玛，這樣就能提高HashMap的性能。
9）使用CocurrentHashMap代替Hashtable噩咪？
可以顾彰，但是Hashtable提供的線程更加安全极阅。
Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好涨享，因?yàn)樗鼉H僅根據(jù)同步級別對map的一部分進(jìn)行上鎖筋搏。ConcurrentHashMap當(dāng)然可以代替HashTable，但是HashTable提供更強(qiáng)的線程安全性厕隧。
10）hashing的概念
散列法（Hashing）或哈希法是一種將字符組成的字符串轉(zhuǎn)換為固定長度（一般是更短長度）的數(shù)值或索引值的方法奔脐，稱為散列法，也叫哈希法吁讨。由于通過更短的哈希值比用原始值進(jìn)行數(shù)據(jù)庫搜索更快髓迎，這種方法一般用來在數(shù)據(jù)庫中建立索引并進(jìn)行搜索，同時(shí)還用在各種解密算法中建丧。
11）擴(kuò)展：為什么equals()方法要重寫排龄？
判斷兩個(gè)對象在邏輯上是否相等，如根據(jù)類的成員變量來判斷兩個(gè)類的實(shí)例是否相等翎朱，而繼承Object中的equals方法只能判斷兩個(gè)引用變量是否是同一個(gè)對象橄维。這樣我們往往需要重寫equals()方法。
我們向一個(gè)沒有重復(fù)對象的集合中添加元素時(shí)拴曲，集合中存放的往往是對象争舞，我們需要先判斷集合中是否存在已知對象，這樣就必須重寫equals方法澈灼。
7.說一下 HashSet 的實(shí)現(xiàn)原理兑障？
①是基于HashMap實(shí)現(xiàn)的，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個(gè)初始容量為16蕉汪，負(fù)載因子為0.75 的HashMap流译。封裝了一個(gè) HashMap 對象來存儲(chǔ)所有的集合元素，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來保存者疤，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT福澡，它是一個(gè)靜態(tài)的 Object 對象。
②當(dāng)我們試圖把某個(gè)類的對象當(dāng)成 HashMap的 key驹马，或試圖將這個(gè)類的對象放入 HashSet 中保存時(shí)革砸，重寫該類的equals(Object obj)方法和hashCode() 方法很重要，而且這兩個(gè)方法的返回值必須保持一致：當(dāng)該類的兩個(gè)的 hashCode() 返回值相同時(shí)糯累，它們通過 equals() 方法比較也應(yīng)該返回 true算利。通常來說，所有參與計(jì)算 hashCode() 返回值的關(guān)鍵屬性泳姐，都應(yīng)該用于作為 equals() 比較的標(biāo)準(zhǔn)效拭。
③HashSet的其他操作都是基于HashMap的。
8.ArrayList 和 LinkedList 的區(qū)別是什么？
? 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：
ArrayList 是動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)缎患，而 LinkedList 是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)慕的。
? 隨機(jī)訪問效率：
ArrayList 比 LinkedList 在隨機(jī)訪問的時(shí)候效率要高，
因?yàn)?LinkedList 是線性的數(shù)據(jù)存儲(chǔ)方式挤渔，所以需要移動(dòng)指針從前往后依次查找肮街。
? 增加和刪除效率：
在非首尾的增加和刪除操作，LinkedList 要比 ArrayList 效率要高判导，
因?yàn)?ArrayList 增刪操作要影響數(shù)組內(nèi)的其他數(shù)據(jù)的下標(biāo)嫉父。
? 綜合來說：
在需要頻繁讀取集合中的元素時(shí)，更推薦使用 ArrayList眼刃，
而在插入和刪除操作較多時(shí)熔号，更推薦使用 LinkedList。
9.如何實(shí)現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換鸟整？
數(shù)組轉(zhuǎn)List
public static void testArray2List() {
String[] strs = new String[] {"aaa", "bbb", "ccc"};
List<String> list = Arrays.asList(strs);
for (String s : list) {
System.out.println(s);
}
}
List轉(zhuǎn)數(shù)組
public static void testList2Array() {
List<String> list = Arrays.asList("aaa", "bbb", "ccc");
String[] array = list.toArray(new String[list.size()]);
for (String s : array) {
System.out.println(s);
}
}
10.ArrayList 和 Vector 的區(qū)別是什么引镊？
線程安全：Vector 使用了 Synchronized 來實(shí)現(xiàn)線程同步，是線程安全的篮条，而 ArrayList 是非線程安全的弟头。
性能：ArrayList 在性能方面要優(yōu)于 Vector。
擴(kuò)容：ArrayList 和 Vector 都會(huì)根據(jù)實(shí)際的需要?jiǎng)討B(tài)的調(diào)整容量涉茧，
只不過在 Vector 擴(kuò)容每次會(huì)增加 1 倍赴恨，而 ArrayList 只會(huì)增加 50%。
