剖析面試最常見問題之Java基礎(chǔ)知識
說說List,Set,Map三者的區(qū)別券册？
- List(對付順序的好幫手)： List接口存儲一組不唯一（可以有多個元素引用相同的對象）垂涯，有序的對象
- Set(注重獨一無二的性質(zhì)): 不允許重復(fù)的集合耕赘。不會有多個元素引用相同的對象操骡。
- Map(用Key來搜索的專家): 使用鍵值對存儲册招。Map會維護與Key有關(guān)聯(lián)的值是掰。兩個Key可以引用相同的對象键痛，但Key不能重復(fù)絮短，典型的Key是String類型丁频，但也可以是任何對象。
Arraylist 與 LinkedList 區(qū)別?
1. 是否保證線程安全：
ArrayList和LinkedList都是不同步的，也就是不保證線程安全世澜；2. 底層數(shù)據(jù)結(jié)構(gòu)：
Arraylist底層使用的是Object數(shù)組寥裂；LinkedList底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表封恰，JDK1.7取消了循環(huán)诺舔。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別备畦，下面有介紹到６巍）3. 插入和刪除是否受元素位置的影響： ①
ArrayList采用數(shù)組存儲莉恼，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響俐银。 比如：執(zhí)行add(E e)方法的時候悉患，ArrayList會默認在將指定的元素追加到此列表的末尾售躁，這種情況時間復(fù)雜度就是O(1)陪捷。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復(fù)雜度就為 O(n-i)市袖。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。 ②LinkedList采用鏈表存儲撮执，所以插入抒钱，刪除元素時間復(fù)雜度不受元素位置的影響谋币，都是近似 O（1）而數(shù)組為近似 O（n）蕾额。4. 是否支持快速隨機訪問：
LinkedList不支持高效的隨機元素訪問诅蝶，而ArrayList支持秤涩】鹁欤快速隨機訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)匀谣。5. 內(nèi)存空間占用： ArrayList的空 間浪費主要體現(xiàn)在在list列表的結(jié)尾會預(yù)留一定的容量空間武翎，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）宝恶。
補充內(nèi)容:RandomAccess接口
public interface RandomAccess {
}
查看源碼我們發(fā)現(xiàn)實際上 RandomAccess 接口中什么都沒有定義垫毙。所以综芥，在我看來 RandomAccess 接口不過是一個標(biāo)識罷了膀藐。標(biāo)識什么额各？ 標(biāo)識實現(xiàn)這個接口的類具有隨機訪問功能臊泰。
在 binarySearch（）方法中缸逃，它要判斷傳入的list 是否 RamdomAccess 的實例，如果是昭殉，調(diào)用indexedBinarySearch（）方法挪丢，如果不是乾蓬，那么調(diào)用iteratorBinarySearch（）方法
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
ArrayList 實現(xiàn)了 RandomAccess 接口任内， 而 LinkedList 沒有實現(xiàn)死嗦。為什么呢越除？我覺得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)外盯！ArrayList 底層是數(shù)組，而 LinkedList 底層是鏈表门怪。數(shù)組天然支持隨機訪問肋殴，時間復(fù)雜度為 O（1）护锤，所以稱為快速隨機訪問烙懦。鏈表需要遍歷到特定位置才能訪問特定位置的元素氯析，時間復(fù)雜度為 O（n）掩缓，所以不支持快速隨機訪問你辣。舍哄，ArrayList 實現(xiàn)了 RandomAccess 接口表悬，就表明了他具有快速隨機訪問功能叉讥。 RandomAccess 接口只是標(biāo)識图仓，并不是說 ArrayList 實現(xiàn) RandomAccess 接口才具有快速隨機訪問功能的救崔！
下面再總結(jié)一下 list 的遍歷方式選擇：
- 實現(xiàn)了
RandomAccess接口的list六孵，優(yōu)先選擇普通 for 循環(huán) 颤难，其次 foreach, - 未實現(xiàn)
RandomAccess接口的list冠息，優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過iterator實現(xiàn)的,）逛艰，大size的數(shù)據(jù)散怖，千萬不要使用普通for循環(huán)
補充內(nèi)容:雙向鏈表和雙向循環(huán)鏈表
雙向鏈表： 包含兩個指針镇眷，一個prev指向前一個節(jié)點，一個next指向后一個節(jié)點。
雙向循環(huán)鏈表： 最后一個節(jié)點的 next 指向head硝桩，而 head 的prev指向最后一個節(jié)點，構(gòu)成一個環(huán)衙伶。
ArrayList 與 Vector 區(qū)別呢?為什么要用Arraylist取代Vector呢？
Vector類的所有方法都是同步的芬沉⊥枰荩可以由兩個線程安全地訪問一個Vector對象黄刚、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間憔维。
Arraylist不是同步的埋同，所以在不需要保證線程安全時時建議使用Arraylist咧栗。
說一說 ArrayList 的擴容機制吧
詳見筆主的這篇文章:通過源碼一步一步分析ArrayList 擴容機制
HashMap 和 Hashtable 的區(qū)別
-
線程是否安全： HashMap 是非線程安全的致板，HashTable 是線程安全的斟或；HashTable 內(nèi)部的方法基本都經(jīng)過
synchronized修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧＜丁）萝挤； - 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點根欧。另外怜珍，HashTable 基本被淘汰，不要在代碼中使用它凤粗；
- 對Null key 和Null value的支持： HashMap 中，null 可以作為鍵嫌拣，這樣的鍵只有一個柔袁，可以有一個或多個鍵所對應(yīng)的值為 null。异逐。但是在 HashTable 中 put 進的鍵值只要有一個 null捶索，直接拋出 NullPointerException。
-
初始容量大小和每次擴充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值应役，Hashtable 默認的初始大小為11情组，之后每次擴充，容量變?yōu)樵瓉淼?n+1箩祥。HashMap 默認的初始化大小為16院崇。之后每次擴充，容量變?yōu)樵瓉淼?倍袍祖。②創(chuàng)建時如果給定了容量初始值底瓣，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小（HashMap 中的
tableSizeFor()方法保證捐凭，下面給出了源代碼）拨扶。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方。 - 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化茁肠，當(dāng)鏈表長度大于閾值（默認為8）時患民，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間垦梆。Hashtable 沒有這樣的機制匹颤。
HasMap 中帶有初始容量的構(gòu)造函數(shù)：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
下面這個方法保證了 HashMap 總是使用2的冪作為哈希表的大小。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap 和 HashSet區(qū)別
如果你看過 HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實現(xiàn)的托猩。（HashSet 的源碼非常非常少印蓖，因為除了 clone()、writeObject()京腥、readObject()是 HashSet 自己不得不實現(xiàn)之外赦肃，其他方法都是直接調(diào)用 HashMap 中的方法。
| HashMap | HashSet |
|---|---|
| 實現(xiàn)了Map接口 | 實現(xiàn)Set接口 |
| 存儲鍵值對 | 僅存儲對象 |
調(diào)用 put（）向map中添加元素 |
調(diào)用 add（）方法向Set中添加元素 |
| HashMap使用鍵（Key）計算Hashcode | HashSet使用成員對象來計算hashcode值公浪，對于兩個對象來說hashcode可能相同他宛，所以equals()方法用來判斷對象的相等性， |
HashSet如何檢查重復(fù)
當(dāng)你把對象加入HashSet時欠气，HashSet會先計算對象的hashcode值來判斷對象加入的位置堕汞，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode晃琳，HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)。但是如果發(fā)現(xiàn)有相同hashcode值的對象琐鲁，這時會調(diào)用equals（）方法來檢查hashcode相等的對象是否真的相同卫旱。如果兩者相同，HashSet就不會讓加入操作成功围段。（摘自我的Java啟蒙書《Head fist java》第二版）
hashCode（）與equals（）的相關(guān)規(guī)定：
- 如果兩個對象相等顾翼，則hashcode一定也是相同的
- 兩個對象相等,對兩個equals方法返回true
- 兩個對象有相同的hashcode值，它們也不一定是相等的
- 綜上奈泪，equals方法被覆蓋過适贸，則hashCode方法也必須被覆蓋
- hashCode()的默認行為是對堆上的對象產(chǎn)生獨特值。如果沒有重寫hashCode()涝桅，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數(shù)據(jù)）拜姿。
==與equals的區(qū)別
- ==是判斷兩個變量或?qū)嵗遣皇侵赶蛲粋€內(nèi)存空間 equals是判斷兩個變量或?qū)嵗赶虻膬?nèi)存空間的值是不是相同
- ==是指對內(nèi)存地址進行比較 equals()是對字符串的內(nèi)容進行比較
- ==指引用是否相同 equals()指的是值是否相同
HashMap的底層實現(xiàn)
JDK1.8之前
JDK1.8 之前 HashMap 底層是 數(shù)組和鏈表 結(jié)合在一起使用也就是 鏈表散列。HashMap 通過 key 的 hashCode 經(jīng)過擾動函數(shù)處理過后得到 hash 值冯遂，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長度）蕊肥，如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同蛤肌，如果相同的話壁却，直接覆蓋批狱，不相同就通過拉鏈法解決沖突。
所謂擾動函數(shù)指的就是 HashMap 的 hash 方法展东。使用 hash 方法也就是擾動函數(shù)是為了防止一些實現(xiàn)比較差的 hashCode() 方法 換句話說使用擾動函數(shù)之后可以減少碰撞赔硫。
JDK 1.8 HashMap 的 hash 方法源碼:
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化，但是原理不變盐肃。
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無符號右移爪膊，忽略符號位，空位都以0補齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
對比一下 JDK1.7的 HashMap 的 hash 方法源碼.
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
相比于 JDK1.8 的 hash 方法 恼蓬，JDK 1.7 的 hash 方法的性能會稍差一點點惊完，因為畢竟擾動了 4 次。
所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合处硬。也就是說創(chuàng)建一個鏈表數(shù)組小槐，數(shù)組中每一格就是一個鏈表。若遇到哈希沖突荷辕，則將沖突的值加到鏈表中即可凿跳。
JDK1.8之后
相比于之前的版本， JDK1.8之后在解決哈希沖突時有了較大的變化疮方，當(dāng)鏈表長度大于閾值（默認為8）時控嗜，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間骡显。
TreeMap疆栏、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹。紅黑樹就是為了解決二叉查找樹的缺陷惫谤，因為二叉查找樹在某些情況下會退化成一個線性結(jié)構(gòu)壁顶。
推薦閱讀：
- 《Java 8系列之重新認識HashMap》 ：https://zhuanlan.zhihu.com/p/21673805
HashMap 的長度為什么是2的冪次方
為了能讓 HashMap 存取高效，盡量較少碰撞溜歪，也就是要盡量把數(shù)據(jù)分配均勻若专。我們上面也講到了過了，Hash 值的范圍值-2147483648到2147483647蝴猪，前后加起來大概40億的映射空間调衰，只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的自阱。但問題是一個40億長度的數(shù)組嚎莉，內(nèi)存是放不下的。所以這個散列值是不能直接拿來用的沛豌。用之前還要先做對數(shù)組的長度取模運算萝喘，得到的余數(shù)才能用來要存放的位置也就是對應(yīng)的數(shù)組下標(biāo)。這個數(shù)組下標(biāo)的計算方法是“ (n - 1) & hash”。（n代表數(shù)組長度）阁簸。這也就解釋了 HashMap 的長度為什么是2的冪次方爬早。
這個算法應(yīng)該如何設(shè)計呢？
我們首先可能會想到采用%取余的操作來實現(xiàn)启妹。但是筛严，重點來了：“取余(%)操作中如果除數(shù)是2的冪次則等價于與其除數(shù)減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）饶米〗翱校” 并且 采用二進制位操作 &，相對于%能夠提高運算效率檬输，這就解釋了 HashMap 的長度為什么是2的冪次方照瘾。
HashMap 多線程操作導(dǎo)致死循環(huán)問題
主要原因在于 并發(fā)下的Rehash 會造成元素之間會形成一個循環(huán)鏈表。不過丧慈，jdk 1.8 后解決了這個問題析命，但是還是不建議在多線程下使用 HashMap,因為多線程下使用 HashMap 還是會存在其他問題比如數(shù)據(jù)丟失。并發(fā)環(huán)境下推薦使用 ConcurrentHashMap 逃默。
詳情請查看：https://coolshell.cn/articles/9606.html
ConcurrentHashMap 和 Hashtable 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同鹃愤。
- 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣完域，數(shù)組+鏈表/紅黑二叉樹软吐。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體吟税，鏈表則是主要為了解決哈希沖突而存在的凹耙；
- 實現(xiàn)線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） 對整個桶數(shù)組進行了分割分段(Segment)肠仪，每一把鎖只鎖容器其中一部分數(shù)據(jù)使兔，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭藤韵，提高并發(fā)訪問率。 到了 JDK1.8 的時候已經(jīng)摒棄了Segment的概念熊经，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)泽艘，并發(fā)控制使用 synchronized 和 CAS 來操作。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化過且線程安全的 HashMap镐依，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)匹涮，但是已經(jīng)簡化了屬性，只是為了兼容舊版本槐壳；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全然低，效率非常低下。當(dāng)一個線程訪問同步方法時，其他線程也訪問同步方法雳攘，可能會進入阻塞或輪詢狀態(tài)带兜，如使用 put 添加元素，另一個線程不能使用 put 添加元素吨灭，也不能使用 get刚照，競爭會越來越激烈效率越低。
兩者的對比圖：
圖片來源：http://www.cnblogs.com/chengxiao/p/6842045.html
HashTable:
JDK1.7的ConcurrentHashMap：
JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹節(jié)點 Node: 鏈表節(jié)點）：
ConcurrentHashMap線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)
JDK1.7（上面有示意圖）
首先將數(shù)據(jù)分為一段一段的存儲喧兄，然后給每一段數(shù)據(jù)配一把鎖无畔，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)時，其他段的數(shù)據(jù)也能被其他線程訪問吠冤。
ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成浑彰。
Segment 實現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色拯辙。HashEntry 用于存儲鍵值對數(shù)據(jù)郭变。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組。Segment 的結(jié)構(gòu)和HashMap類似薄风，是一種數(shù)組和鏈表結(jié)構(gòu)饵较，一個 Segment 包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素遭赂，每個 Segment 守護著一個HashEntry數(shù)組里的元素循诉，當(dāng)對 HashEntry 數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得對應(yīng)的 Segment的鎖撇他。
JDK1.8 （上面有示意圖）
ConcurrentHashMap取消了Segment分段鎖茄猫，采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似困肩，數(shù)組+鏈表/紅黑二叉樹划纽。Java 8在鏈表長度超過一定閾值（8）時將鏈表（尋址時間復(fù)雜度為O(N)）轉(zhuǎn)換為紅黑樹（尋址時間復(fù)雜度為O(long(N))）
synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點，這樣只要hash不沖突锌畸，就不會產(chǎn)生并發(fā)勇劣，效率又提升N倍。
comparable 和 Comparator的區(qū)別
- comparable接口實際上是出自java.lang包 它有一個
compareTo(Object obj)方法用來排序 - comparator接口實際上是出自 java.util 包它有一個
compare(Object obj1, Object obj2)方法用來排序
一般我們需要對一個集合使用自定義排序時潭枣，我們就要重寫compareTo()方法或compare()方法比默，當(dāng)我們需要對某一個集合實現(xiàn)兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話盆犁，我們可以重寫compareTo()方法和使用自制的Comparator方法或者以兩個Comparator來實現(xiàn)歌名排序和歌星名排序命咐，第二種代表我們只能使用兩個參數(shù)版的 Collections.sort().
Comparator定制排序
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始數(shù)組:");
System.out.println(arrayList);
// void reverse(List list)：反轉(zhuǎn)
Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);
// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
System.out.println("定制排序后：");
System.out.println(arrayList);
Output:
原始數(shù)組:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]
重寫compareTo方法實現(xiàn)按年齡來排序
// person對象沒有實現(xiàn)Comparable接口，所以必須實現(xiàn)谐岁，這樣才不會出錯醋奠，才可以使treemap中的數(shù)據(jù)按順序排列
// 前面一個例子的String類已經(jīng)默認實現(xiàn)了Comparable接口榛臼，詳細可以查看String類的API文檔，另外其他
// 像Integer類等都已經(jīng)實現(xiàn)了Comparable接口窜司，所以不需要另外實現(xiàn)了
public class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
/**
* TODO重寫compareTo方法實現(xiàn)按年齡來排序
*/
@Override
public int compareTo(Person o) {
// TODO Auto-generated method stub
if (this.age > o.getAge()) {
return 1;
} else if (this.age < o.getAge()) {
return -1;
}
return age;
}
}
public static void main(String[] args) {
TreeMap<Person, String> pdata = new TreeMap<Person, String>();
pdata.put(new Person("張三", 30), "zhangsan");
pdata.put(new Person("李四", 20), "lisi");
pdata.put(new Person("王五", 10), "wangwu");
pdata.put(new Person("小紅", 5), "xiaohong");
// 得到key的值的同時得到key所對應(yīng)的值
Set<Person> keys = pdata.keySet();
for (Person key : keys) {
System.out.println(key.getAge() + "-" + key.getName());
}
}
Output：
5-小紅
10-王五
20-李四
30-張三
集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)
Collection
1. List
- Arraylist： Object數(shù)組
- Vector： Object數(shù)組
- LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表沛善，JDK1.7取消了循環(huán))
2. Set
- HashSet（無序，唯一）: 基于 HashMap 實現(xiàn)的例证，底層采用 HashMap 來保存元素
- LinkedHashSet： LinkedHashSet 繼承與 HashSet路呜，并且其內(nèi)部是通過 LinkedHashMap 來實現(xiàn)的。有點類似于我們之前說的LinkedHashMap 其內(nèi)部是基于 Hashmap 實現(xiàn)一樣织咧，不過還是有一點點區(qū)別的胀葱。
- TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹笙蒙。)
Map
- HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的抵屿，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）捅位。JDK1.8以后在解決哈希沖突時有了較大的變化轧葛，當(dāng)鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹艇搀，以減少搜索時間
- LinkedHashMap： LinkedHashMap 繼承自 HashMap尿扯，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外焰雕，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上衷笋，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序矩屁。同時通過對鏈表進行相應(yīng)的操作辟宗，實現(xiàn)了訪問順序相關(guān)邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》
- Hashtable： 數(shù)組+鏈表組成的吝秕，數(shù)組是 HashMap 的主體泊脐，鏈表則是主要為了解決哈希沖突而存在的
- TreeMap： 紅黑樹（自平衡的排序二叉樹）
如何選用集合?
主要根據(jù)集合的特點來選用，比如我們需要根據(jù)鍵值獲取到元素值時就選用Map接口下的集合烁峭，需要排序時選擇TreeMap,不需要排序時就選擇HashMap,需要保證線程安全就選用ConcurrentHashMap.當(dāng)我們只需要存放元素值時容客，就選擇實現(xiàn)Collection接口的集合，需要保證元素唯一時選擇實現(xiàn)Set接口的集合比如TreeSet或HashSet约郁，不需要就選擇實現(xiàn)List接口的比如ArrayList或LinkedList缩挑，然后再根據(jù)實現(xiàn)這些接口的集合的特點來選用。
