1秀撇、 常用數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

a、數(shù)組：順序存儲(chǔ)向族，隨機(jī)訪問(wèn) ?????鏈表：鏈表存儲(chǔ)呵燕，順序訪問(wèn)
b、棧件相，分為棧頂和棧底再扭，遵循先進(jìn)后出原則
c、隊(duì)列 夜矗，一個(gè)線性表泛范，像排隊(duì)一樣，受約束控制侯养，遵循先進(jìn)先出原則
d敦跌、樹(shù)：二叉樹(shù)、平衡二叉樹(shù)逛揩、大頂堆，小頂堆等
e麸俘、圖：最短路徑辩稽，關(guān)鍵路徑

2、 并發(fā)集合了解哪些从媚？

并發(fā)List
Vector和CopyOnWriteArrayList是兩個(gè)線程安全的List逞泄，Vector讀寫(xiě)操作都用了同步，相對(duì)來(lái)說(shuō)更適用于寫(xiě)多讀少的場(chǎng)合拜效，CopyOnWriteArrayList在寫(xiě)的時(shí)候會(huì)復(fù)制一個(gè)副本喷众，對(duì)副本寫(xiě)，寫(xiě)完用副本替換原值紧憾，讀的時(shí)候不需要同步到千，適用于寫(xiě)少讀多的場(chǎng)合。

并發(fā)Set
CopyOnWriteArraySet基于CopyOnWriteArrayList來(lái)實(shí)現(xiàn)的赴穗，只是在不允許存在重復(fù)的對(duì)象這個(gè)特性上遍歷處理了一下憔四。

并發(fā)Map
ConcurrentHashMap是專(zhuān)用于高并發(fā)的Map實(shí)現(xiàn)膀息，內(nèi)部實(shí)現(xiàn)進(jìn)行了鎖分離，get操作是無(wú)鎖的了赵。

并發(fā)的Queue
在并發(fā)隊(duì)列上JDK提供了兩套實(shí)現(xiàn)潜支，一個(gè)是以ConcurrentLinkedQueue為代表的高性能隊(duì)列，一個(gè)是以BlockingQueue接口為代表的阻塞隊(duì)列柿汛。ConcurrentLinkedQueue適用于高并發(fā)場(chǎng)景下的隊(duì)列冗酿，通過(guò)無(wú)鎖的方式實(shí)現(xiàn)，通常ConcurrentLinkedQueue的性能要優(yōu)于BlockingQueue络断。BlockingQueue的典型應(yīng)用場(chǎng)景是生產(chǎn)者-消費(fèi)者模式中已烤，如果生產(chǎn)快于消費(fèi)，生產(chǎn)隊(duì)列裝滿時(shí)會(huì)阻塞妓羊，等待消費(fèi)胯究。

并發(fā)的Dueue
Queue是一種雙端隊(duì)列，它允許在隊(duì)列的頭部和尾部進(jìn)行出隊(duì)和入隊(duì)的操作躁绸。Dueue實(shí)現(xiàn)類(lèi)有非線程安全的LinkedList裕循、ArrayDueue和線程安全的LinkedBlockingDueue。LinkedBlockingDueue沒(méi)有進(jìn)行讀寫(xiě)鎖的分離净刮，因此同一時(shí)間只能有一個(gè)線程對(duì)其操作剥哑，因此在高并發(fā)應(yīng)用中，它的性能要遠(yuǎn)遠(yuǎn)低于LinkedBlockingQueue淹父，更低于ConcurrentLinkedQueue株婴。

并發(fā)鎖重入鎖ReentrantLock
ReentrantLock是一種互斥鎖的實(shí)現(xiàn)，就是一次最多只能一個(gè)線程拿到鎖暑认；

讀寫(xiě)鎖ReadWriteLock
讀寫(xiě)鎖有讀取和寫(xiě)入兩種鎖困介，讀取鎖允許多個(gè)讀取的線程同時(shí)持有，而寫(xiě)入鎖只能有一個(gè)線程持有蘸际。

條件Condition
調(diào)用Condition對(duì)象的相關(guān)方法座哩，可以方便的掛起和喚醒線程。

3粮彤、 列舉java的集合以及集合之間的繼承關(guān)系

java 集合框架由兩個(gè)根接口Collection 和map構(gòu)成：

QQ截圖20180629100805.png

QQ截圖20180629100920.png

4闯两、 集合類(lèi)以及集合框架

如上圖褥伴，基本已經(jīng)涵蓋相應(yīng)的集合類(lèi)和框架內(nèi)容谅将，在工作中用得比較多得是ArrayList, LinkList,HashSet和HashMap .由于我們可能需要在多線程環(huán)境中對(duì)我們定義的數(shù)據(jù)進(jìn)行并發(fā)訪問(wèn)，所以我們必須確保我們當(dāng)前得數(shù)據(jù)是同步的或者我們?cè)谛枰{(diào)用的地方進(jìn)行加鎖重慢，但synchronized關(guān)鍵字和Lock類(lèi)等都增加了代碼復(fù)雜度而且容易出錯(cuò)饥臂，還有一種更為便捷的辦法就是我們直接使用線程安全的數(shù)據(jù)結(jié)構(gòu)或者用系統(tǒng)的Collections對(duì)其進(jìn)行包裝讓不安全的成為安全的，所以這里我們需要去了解上圖中的一些類(lèi)
????在List鏈表中似踱，ArrayList 和LinkList 都是線程不安全的隅熙；Vector是線程安全的，ArrayList和Vector類(lèi)的底層都是基于數(shù)組來(lái)儲(chǔ)存集合元素核芽，封裝了一個(gè)動(dòng)態(tài)的Object[]數(shù)組囚戚，是一種順序存儲(chǔ)的線性表；LinkedList是一個(gè)鏈?zhǔn)酱鎯?chǔ)的線性表轧简，本質(zhì)上是一個(gè)雙向鏈表驰坊，它不僅實(shí)現(xiàn)了List接口還實(shí)現(xiàn)了Dueue接口(雙端隊(duì)列，既具有隊(duì)列的特征哮独，也具有棧的特征)
????set集合代表不重復(fù)的集合拳芙；而queue是一種隊(duì)列

5、 容器類(lèi)介紹以及之間的區(qū)別（容器類(lèi)估計(jì)很多人沒(méi)聽(tīng)這個(gè)詞皮璧，Java容器主要可以劃分為4個(gè)部分：List列表舟扎、Set集合、Map映射悴务、工具類(lèi)（Iterator迭代器睹限、Enumeration枚舉類(lèi)、Arrays和Collections）讯檐，具體的可以看看這篇博文 Java容器類(lèi)）

ArrayList

ArrayList定義如下：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一個(gè)動(dòng)態(tài)數(shù)組羡疗，也是我們最常用的集合。它允許任何符合規(guī)則的元素插入甚至包括null裂垦。每一個(gè)ArrayList都有一個(gè)初始容量：

private static final int DEFAULT_CAPACITY = 10;

隨著容器中的元素不斷增加顺囊，容器的大小也會(huì)隨著增加。在每次向容器中增加元素的同時(shí)都會(huì)進(jìn)行容量檢查蕉拢，當(dāng)快溢出時(shí)，就會(huì)進(jìn)行擴(kuò)容操作诚亚。所以如果我們明確所插入元素的多少晕换，最好指定一個(gè)初始容量值，避免過(guò)多的進(jìn)行擴(kuò)容操作而浪費(fèi)時(shí)間站宗、效率闸准。
size、isEmpty梢灭、get夷家、set蒸其、iterator 和 listIterator 操作都以固定時(shí)間運(yùn)行。add 操作以分?jǐn)偟墓潭〞r(shí)間運(yùn)行库快，也就是說(shuō)摸袁，添加 n 個(gè)元素需要 O(n) 時(shí)間（由于要考慮到擴(kuò)容，所以這不只是添加元素會(huì)帶來(lái)分?jǐn)偣潭〞r(shí)間開(kāi)銷(xiāo)那樣簡(jiǎn)單）义屏。
ArrayList擅長(zhǎng)于隨機(jī)訪問(wèn)靠汁。同時(shí)ArrayList是非同步的。

LinkedList

LinkedList定義如下：

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

同樣實(shí)現(xiàn)List接口的LinkedList與ArrayList不同闽铐，ArrayList是一個(gè)動(dòng)態(tài)數(shù)組蝶怔，而LinkedList是一個(gè)雙向鏈表。所以它除了有ArrayList的基本操作方法外還額外提供了get兄墅，remove踢星，insert方法在LinkedList的首部或尾部。
由于實(shí)現(xiàn)的方式不同隙咸，LinkedList不能隨機(jī)訪問(wèn)沐悦，它所有的操作都是要按照雙重鏈表的需要執(zhí)行。在列表中索引的操作將從開(kāi)頭或結(jié)尾遍歷列表（從靠近指定索引的一端扎瓶，節(jié)約一半時(shí)間）所踊。這樣做的好處就是可以通過(guò)較低的代價(jià)在List中進(jìn)行插入和刪除操作。
與ArrayList一樣概荷，LinkedList也是非同步的秕岛。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)List，則必須自己實(shí)現(xiàn)訪問(wèn)同步误证。一種解決方法是在創(chuàng)建List時(shí)構(gòu)造一個(gè)同步的List：

List list = Collections.synchronizedList(new LinkedList(…));

Vector

Vector定義如下：

public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

與ArrayList相似继薛，但是Vector是同步的。所以說(shuō)Vector是線程安全的動(dòng)態(tài)數(shù)組愈捅。它的操作與ArrayList幾乎一樣遏考。

Stack

Stack定義如下：

public class Stack<E> extends Vector<E> {}

Stack繼承自Vector，實(shí)現(xiàn)一個(gè)后進(jìn)先出的堆棧蓝谨。Stack提供5個(gè)額外的方法使得Vector得以被當(dāng)作堆棧使用灌具。基本的push和pop方法譬巫，還有peek方法得到棧頂?shù)脑乜ч梗琫mpty方法測(cè)試堆棧是否為空，search方法檢測(cè)一個(gè)元素在堆棧中的位置芦昔。Stack剛創(chuàng)建后是空棧诱贿。

HashSet

HashSet定義如下：

public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

HashSet堪稱(chēng)查詢(xún)速度最快的集合，因?yàn)槠鋬?nèi)部是以HashCode來(lái)實(shí)現(xiàn)的。集合元素可以是null,但只能放入一個(gè)null珠十。它內(nèi)部元素的順序是由哈希碼來(lái)決定的料扰，所以它不保證set的迭代順序；特別是它不保證該順序恒久不變焙蹭。

TreeSet

TreeSet定義如下：

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet是二叉樹(shù)實(shí)現(xiàn)的晒杈，基于TreeMap，生成一個(gè)總是處于排序狀態(tài)的set壳嚎，內(nèi)部以TreeMap來(lái)實(shí)現(xiàn)桐智，不允許放入null值。它是使用元素的自然順序?qū)υ剡M(jìn)行排序烟馅，或者根據(jù)創(chuàng)建Set時(shí)提供的 Comparator 進(jìn)行排序说庭，具體取決于使用的構(gòu)造方法。

LinkedHashSet

LinkedHashSet定義如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable

LinkedHashSet集合同樣是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置郑趁，但是它同時(shí)使用鏈表維護(hù)元素的次序刊驴。這樣使得元素看起 來(lái)像是以插入順序保存的，也就是說(shuō)寡润，當(dāng)遍歷該集合時(shí)候捆憎，LinkedHashSet將會(huì)以元素的添加順序訪問(wèn)集合的元素。LinkedHashSet在迭代訪問(wèn)Set中的全部元素時(shí)梭纹，性能比HashSet好躲惰，但是插入時(shí)性能稍微遜色于HashSet。

EnumSet

EnumSet定義如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable

EnumSet中所有值都必須是指定枚舉類(lèi)型的值变抽，它的元素也是有序的础拨，以枚舉值在枚舉類(lèi)的定義順序來(lái)決定集合元素的順序。EnumSet集合不允許加入null元素绍载，否則會(huì)拋出NullPointerException異常诡宗。EnumSet類(lèi)沒(méi)有暴露任何構(gòu)造器來(lái)創(chuàng)建該類(lèi)的實(shí)例，程序應(yīng)該通過(guò)它提供的static方法來(lái)創(chuàng)建EnumSet對(duì)象

Map接口

Map與List击儡、Set接口不同塔沃，它是由一系列鍵值對(duì)組成的集合，提供了key到Value的映射阳谍。在Map中它保證了key與value之間的一一對(duì)應(yīng)關(guān)系蛀柴。也就是說(shuō)一個(gè)key對(duì)應(yīng)一個(gè)value，所以它不能存在相同的key值矫夯，當(dāng)然value值可以相同名扛。
實(shí)現(xiàn)map的集合有：HashMap、HashTable茧痒、TreeMap、WeakHashMap融蹂。

HashMap

HashMap定義如下：

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)旺订，查找對(duì)象時(shí)通過(guò)哈希函數(shù)計(jì)算其位置弄企，它是為快速查詢(xún)而設(shè)計(jì)的，其內(nèi)部定義了一個(gè)hash表數(shù)組（Entry[] table）区拳，元素會(huì)通過(guò)哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引拘领，如果有沖突，則使用散列鏈表的形式將所有相同哈希地址的元素串起來(lái)樱调，可能通過(guò)查看HashMap.Entry的源碼它是一個(gè)單鏈表結(jié)構(gòu)约素。

HashTable

HashTable的定義如下：

public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable

也是以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，解決沖突時(shí)與HashMap也一樣也是采用了散列鏈表的形式笆凌。HashTable繼承Dictionary類(lèi)圣猎，實(shí)現(xiàn)Map接口。其中Dictionary類(lèi)是任何可將鍵映射到相應(yīng)值的類(lèi)（如 Hashtable）的抽象父類(lèi)乞而。每個(gè)鍵和每個(gè)值都是一個(gè)對(duì)象送悔。在任何一個(gè) Dictionary 對(duì)象中，每個(gè)鍵至多與一個(gè)值相關(guān)聯(lián)爪模。Map是”key-value鍵值對(duì)”接口欠啤。 HashTable采用”拉鏈法”實(shí)現(xiàn)哈希表不過(guò)性能比HashMap要低。

TreeMap

TreeMap的定義如下：

public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

有序散列表屋灌，實(shí)現(xiàn)SortedMap接口洁段，底層通過(guò)紅黑樹(shù)實(shí)現(xiàn)。

WeakHashMap

WeakHashMap的定義如下：

public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>

談WeakHashMap前先看一下Java中的引用（強(qiáng)度依次遞減）
強(qiáng)引用：普遍對(duì)象聲明的引用共郭，存在便不會(huì)GC
軟引用：有用但并非必須落塑，發(fā)生內(nèi)存溢出前龙考，二次回收
弱引用：只能生存到下次GC之前，無(wú)論是否內(nèi)存足夠
虛引用：唯一目的是在這個(gè)對(duì)象被GC時(shí)能收到一個(gè)系統(tǒng)通知
以弱鍵實(shí)現(xiàn)的基于哈希表的Map。在 WeakHashMap 中股囊，當(dāng)某個(gè)鍵不再正常使用時(shí)内狗，將自動(dòng)移除其條目偎行。更精確地說(shuō)妙真，對(duì)于一個(gè)給定的鍵锈候，其映射的存在并不阻止垃圾回收器對(duì)該鍵的丟棄获列，這就使該鍵成為可終止的鹏漆，被終止巩梢，然后被回收创泄。丟棄某個(gè)鍵時(shí)，其條目從映射中有效地移除且改，因此验烧，該類(lèi)的行為與其他的 Map 實(shí)現(xiàn)有所不同。null值和null鍵都被支持又跛。該類(lèi)具有與HashMap類(lèi)相似的性能特征,并具有相同的效能參數(shù)初始容量和加載因子。像大多數(shù)集合類(lèi)一樣若治，該類(lèi)是不同步的慨蓝。

Iterator

Iterator定義如下：

public interface Iterator<E> {}

Iterator是一個(gè)接口，它是集合的迭代器端幼。集合可以通過(guò)Iterator去遍歷集合中的元素礼烈。Iterator提供的API接口，包括：是否存在下一個(gè)元素婆跑、獲取下一個(gè)元素此熬、刪除當(dāng)前元素。
注意：Iterator遍歷Collection時(shí)滑进，是fail-fast機(jī)制的犀忱。即，當(dāng)某一個(gè)線程A通過(guò)iterator去遍歷某集合的過(guò)程中扶关，若該集合的內(nèi)容被其他線程所改變了阴汇；那么線程A訪問(wèn)集合時(shí)，就會(huì)拋出ConcurrentModificationException異常节槐，產(chǎn)生fail-fast事件搀庶。

6、 List,Set,Map的區(qū)別

1铜异、List,Set都是繼承自Collection接口哥倔，Map則不是

2、List特點(diǎn)：元素有放入順序揍庄，元素可重復(fù) 咆蒿，Set特點(diǎn)：元素?zé)o放入順序，元素不可重復(fù)币绩，重復(fù)元素會(huì)覆蓋掉蜡秽，（注意：元素雖然無(wú)放入順序，但是元素在set中的位置是有該元素的HashCode決定的缆镣，其位置其實(shí)是固定的芽突，加入Set 的Object必須定義equals()方法 ，另外list支持for循環(huán)董瞻，也就是通過(guò)下標(biāo)來(lái)遍歷寞蚌，也可以用迭代器田巴，但是set只能用迭代，因?yàn)樗麩o(wú)序挟秤，無(wú)法用下標(biāo)來(lái)取得想要的值壹哺。）

3.Set和List對(duì)比：
Set：檢索元素效率低下，刪除和插入效率高艘刚，插入和刪除不會(huì)引起元素位置改變管宵。
List：和數(shù)組類(lèi)似，List可以動(dòng)態(tài)增長(zhǎng)攀甚，查找元素效率高箩朴，插入刪除元素效率低，因?yàn)闀?huì)引起其他元素位置改變秋度。

4.Map適合儲(chǔ)存鍵值對(duì)的數(shù)據(jù)

5.線程安全集合類(lèi)與非線程安全集合類(lèi)
LinkedList炸庞、ArrayList、HashSet是非線程安全的荚斯，Vector是線程安全的;
HashMap是非線程安全的埠居，HashTable是線程安全的;
StringBuilder是非線程安全的，StringBuffer是線程安全的事期。

7滥壕、 List和Map的實(shí)現(xiàn)方式以及存儲(chǔ)方式

list:是一個(gè)有序的集合可以包含重復(fù)的元素，提供了按索引訪問(wèn)的方式刑赶，采用數(shù)組或者鏈表的方式進(jìn)行儲(chǔ)存
map:包含了key-value對(duì)捏浊，map中key必須唯一，value可以重復(fù)撞叨。

8金踪、 HashMap的實(shí)現(xiàn)原理

hashmap原理涉及地址bucket、hashing牵敷、hashcode和equal胡岔、不可變鍵、hash碰撞枷餐、線程安全靶瘸、數(shù)組和鏈表共同儲(chǔ)存等內(nèi)容
http://www.reibang.com/p/8b372f3a195d/

9、 HashMap數(shù)據(jù)結(jié)構(gòu)毛肋？

http://www.reibang.com/p/8b372f3a195d/

10怨咪、 HashMap源碼理解

http://www.reibang.com/p/8b372f3a195d/

11、 HashMap如何put數(shù)據(jù)（從HashMap源碼角度講解）润匙？

1诗眨、對(duì)key的hashCode()做hash，然后再計(jì)算index;
2孕讳、如果沒(méi)碰撞直接放到bucket里匠楚；
3巍膘、如果碰撞了，以鏈表的形式儲(chǔ)存在buckets后芋簿；
4峡懈、如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹(shù)与斤；
5肪康、如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
6、如果bucket滿了(超過(guò)load factor*current capacity)幽告，就要resize梅鹦。

12、 HashMap怎么手寫(xiě)實(shí)現(xiàn)冗锁？

要手寫(xiě)hashMap，必須先理解其數(shù)據(jù)結(jié)構(gòu)：hashMap的數(shù)據(jù)是通過(guò)hash散列后存放到數(shù)組+單鏈表中的嗤栓，其內(nèi)部讀取采用的位運(yùn)算冻河，考慮到速度的原因。具體實(shí)現(xiàn)參考博客：
對(duì)HashMap的思考及手寫(xiě)實(shí)現(xiàn)

13茉帅、 ConcurrentHashMap的實(shí)現(xiàn)原理

jdk1.7版本原理：
ConcurrentHashMap采用 分段鎖的機(jī)制叨叙，實(shí)現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的存儲(chǔ)結(jié)構(gòu)堪澎。
其包含兩個(gè)核心靜態(tài)內(nèi)部類(lèi) Segment和HashEntry擂错。
1、Segment繼承ReentrantLock用來(lái)充當(dāng)鎖的角色樱蛤，每個(gè) Segment 對(duì)象守護(hù)每個(gè)散列映射表的若干個(gè)桶钮呀。
2、HashEntry 用來(lái)封裝映射表的鍵 / 值對(duì)昨凡；
3爽醋、每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來(lái)的鏈表。

分段鎖圖解.png

jdk1.8版本原理：
利用CAS+Synchronized來(lái)保證并發(fā)更新的安全便脊，底層采用數(shù)組+鏈表+紅黑樹(shù)的存儲(chǔ)結(jié)構(gòu)蚂四。

jdk1.8版本結(jié)構(gòu).png

14、 ArrayMap哪痰、SparseArray和HashMap的對(duì)比

ArrayMap及SparseArray是android的系統(tǒng)API遂赠，是專(zhuān)門(mén)為移動(dòng)設(shè)備而定制的。用于在一定情況下取代HashMap而達(dá)到節(jié)省內(nèi)存的目的晌杰。
hashMap 采用數(shù)組加單鏈表結(jié)構(gòu)前面說(shuō)過(guò)跷睦，采用hash進(jìn)行散列速度還是很快的;
ArrayMap 采用兩個(gè)數(shù)組進(jìn)行儲(chǔ)存，采用二分查找進(jìn)行數(shù)據(jù)操作乎莉；
SparseArray 采用固定key類(lèi)型方式進(jìn)行儲(chǔ)存送讲，即key只能為int類(lèi)型奸笤，直接進(jìn)行對(duì)比int數(shù)值，所以沒(méi)有拆箱和裝箱的操作哼鬓，效率上會(huì)有一定的提升监右，查找算法也是采用的二分查找；
1.在數(shù)據(jù)量小的時(shí)候一般認(rèn)為1000以下异希，當(dāng)你的key為int的時(shí)候健盒，使用SparseArray確實(shí)是一個(gè)很不錯(cuò)的選擇枢纠，內(nèi)存大概能節(jié)省30%疹蛉，相比用HashMap碴卧，因?yàn)樗黭ey值不需要裝箱利职，所以時(shí)間性能平均來(lái)看也優(yōu)于HashMap,建議使用菱属！
2.ArrayMap相對(duì)于SparseArray描焰，特點(diǎn)就是key值類(lèi)型不受限单山，任何情況下都可以取代HashMap,但是通過(guò)研究和測(cè)試發(fā)現(xiàn)逸爵，ArrayMap的內(nèi)存節(jié)省并不明顯授药，也就在10%左右士嚎，但是時(shí)間性能確是最差的，當(dāng)然了悔叽，1000以?xún)?nèi)的數(shù)據(jù)量也無(wú)所謂了莱衩，加上它只有在API>=19才可以使用
詳情參考HashMap，ArrayMap娇澎，SparseArray源碼分析及性能對(duì)比

15笨蚁、 HashTable實(shí)現(xiàn)原理

16、 TreeMap具體實(shí)現(xiàn)

17趟庄、 HashMap和HashTable的區(qū)別

18括细、 HashMap與HashSet的區(qū)別

19、 HashSet與HashMap怎么判斷集合元素重復(fù)岔激？

20勒极、 集合Set實(shí)現(xiàn)Hash怎么防止碰撞

21、 ArrayList和LinkedList的區(qū)別虑鼎，以及應(yīng)用場(chǎng)景

22辱匿、 數(shù)組和鏈表的區(qū)別

23、 二叉樹(shù)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的具體實(shí)現(xiàn)

24炫彩、 堆的結(jié)構(gòu)

25匾七、 堆和樹(shù)的區(qū)別

26、 堆和棧在內(nèi)存中的區(qū)別是什么(解答提示：可以從數(shù)據(jù)結(jié)構(gòu)方面以及實(shí)際實(shí)現(xiàn)方面兩個(gè)方面去回答)江兢？

27昨忆、 什么是深拷貝和淺拷貝

28、 手寫(xiě)鏈表逆序代碼

29杉允、 講一下對(duì)樹(shù)邑贴，B+樹(shù)的理解

30席里、 講一下對(duì)圖的理解

31、 判斷單鏈表成環(huán)與否拢驾？

32奖磁、 鏈表翻轉(zhuǎn)（即：翻轉(zhuǎn)一個(gè)單項(xiàng)鏈表）

33、 合并多個(gè)單有序鏈表（假設(shè)都是遞增的）