關(guān)于list,map,set的區(qū)別
首先他們都是集合，這里就先引申一下集合跟數(shù)組的區(qū)別懊昨，主要的區(qū)別還是在于數(shù)組是靜態(tài)的，類(lèi)型固定的嫉你。而集合是動(dòng)態(tài)的躏惋，存放的類(lèi)型可以不是一種。
接下來(lái)說(shuō)一下集合三者的區(qū)別
他們都是一個(gè)接口
list有三個(gè)實(shí)現(xiàn)類(lèi)距误，分別是：
LinkedList,基于鏈表實(shí)現(xiàn)，鏈表內(nèi)存是散列的准潭，增刪快，查找慢刑然；
ArrayList,基于數(shù)組實(shí)現(xiàn)，非線(xiàn)程安全沽讹，效率高武鲁，增刪慢，查找快挚瘟；
Vector，基于數(shù)組實(shí)現(xiàn)乘盖，線(xiàn)程安全憔涉，效率低，增刪慢穿扳，查找慢国旷；
下面來(lái)說(shuō)一下ArrayList怎么個(gè)線(xiàn)程不安全，閱讀ArrayList的add操作的源碼履羞，可知：
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
這里是因?yàn)閿U(kuò)充size跟加集合是兩步操作屡久，既然是兩步，有多個(gè)線(xiàn)程操作就會(huì)出現(xiàn)不同步被环，例如數(shù)據(jù)會(huì)被后一個(gè)線(xiàn)程覆蓋，或者出現(xiàn)越界
現(xiàn)在說(shuō)一下什么是鏈表丁鹉，顧名思義，就是鏈?zhǔn)降拇眨湵碇械拿恳粋€(gè)元素成為每一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)就包括了儲(chǔ)存數(shù)據(jù)元素的數(shù)據(jù)域跟儲(chǔ)存下一個(gè)節(jié)點(diǎn)的指針域
鏈表又分為單向鏈表谎亩，雙向鏈表宇姚，循環(huán)鏈表，雙向鏈表的有兩個(gè)鏈域分別是存儲(chǔ)了前驅(qū)結(jié)點(diǎn)地址的左鏈域跟存儲(chǔ)了后繼節(jié)點(diǎn)地址的右鏈域阱持。
關(guān)于鏈表的算法運(yùn)用可以參考約瑟夫問(wèn)題
cpu訪問(wèn)數(shù)據(jù)的順序--》寄存器--》緩存--》內(nèi)存--》外存
鏈表跟數(shù)組的對(duì)比魔熏，鏈表存儲(chǔ)是散列的，而數(shù)組是連續(xù)的內(nèi)存地址蒜绽，所以查找操作他們的時(shí)間復(fù)雜度都是O（n）,但是數(shù)組明顯是要快的，因?yàn)镃PU緩存會(huì)把一片連續(xù)的內(nèi)存空間讀入鼎姊，而緩存的速率要比內(nèi)存要快相赁，CPU取數(shù)據(jù)，處理數(shù)據(jù)裆赵，都要寄存在寄存器中處理跺嗽，緩存就是把內(nèi)存中提取出來(lái)的數(shù)據(jù)暫時(shí)保存页藻。但是插入跟刪除操作，由于鏈表是是不連續(xù)的內(nèi)存地址份帐，而數(shù)組是連續(xù)的內(nèi)存地址，其他結(jié)點(diǎn)都要同時(shí)向前或者向后移動(dòng)畜挨，鏈表則不需要。
這里再說(shuō)一下vector,因?yàn)樗麨榱藢?shí)現(xiàn)線(xiàn)程安全加了synchronize,所以查找就耗費(fèi)很多時(shí)間巴元，所以都比arraylist慢
下面再說(shuō)一下map
map.entrySet()會(huì)把map的所有鍵值對(duì)拿出來(lái)放到集合里面
然后我們就可以這樣遍歷map
for(Map.Entry<String,Object>entry:map.entrySet())
map主要有兩大實(shí)現(xiàn)類(lèi)：Hashmap跟TreeMap
實(shí)際中我們用得最多得就Hashmap
簡(jiǎn)單說(shuō)下HashMap的實(shí)現(xiàn)原理：
首先有一個(gè)每個(gè)元素都是鏈表（可能表述不準(zhǔn)確）的數(shù)組，當(dāng)添加一個(gè)元素（key-value）時(shí)呕缭，就首先計(jì)算元素key的hash值修己，以此確定插入數(shù)組中的位置，但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了片仿，這時(shí)就添加到同一hash值的元素的后面尤辱，他們?cè)跀?shù)組的同一位置，但是形成了鏈表啥刻，同一各鏈表上的Hash值是相同的，所以說(shuō)數(shù)組存放的是鏈表娄涩。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)時(shí)映跟，鏈表就轉(zhuǎn)換為紅黑樹(shù)，這樣大大提高了查找的效率球恤。
這里講一下如何提高h(yuǎn)ashmap的性能荸镊，通常構(gòu)建HashMap的時(shí)候都會(huì)初始化數(shù)組，最消耗性能的時(shí)候也就是擴(kuò)容數(shù)組的時(shí)候躬存，如果我們能一開(kāi)始大概估算到插入數(shù)據(jù)的量，然后可以自定義初始化數(shù)組長(zhǎng)度
現(xiàn)在來(lái)講一下什么叫紅黑樹(shù)
