集合框架

1.1概念

集合框架包含三大塊內(nèi)容:對外的接口，接口的實現(xiàn)，和對集合運(yùn)算的算法

集合就是用于存儲對象的容器，集合的長度可變，不能存儲基礎(chǔ)類型的數(shù)據(jù)

1.2集合與數(shù)組的區(qū)別

數(shù)組：長度固定，沒辦法動態(tài)擴(kuò)容

集合存儲數(shù)據(jù)時沒有長度限制(最大值int的max-8)減8的原因:java對象除了存儲數(shù)據(jù)本身

之外還需要32bytes大小來存儲對象頭信息

Java對象在堆內(nèi)存中的存儲布局可以分為三部分：對象頭（object header），實例數(shù)據(jù)（Instance Data）和對齊填充（Padding）。

1.3集合基本架構(gòu)

集合類可以分為兩大類：一類是實現(xiàn)Collection接口；另一類是實現(xiàn)Map接口

Collection是一個基本的集合接口，可以容納一組集合元素

Map沒有繼承Collection接口，與Collection是并列關(guān)系。Map提供鍵(key)到值(value)的映射

一個Map中不能包含相同的鍵，每個鍵只能映射一個值

Collection接口下有兩個接口Set和List

List：有序重復(fù)

List下的實現(xiàn)類有Vector(過時)，ArrayList，LinkedList

Set:無序不重復(fù)，無法通過下標(biāo)訪問數(shù)據(jù)

查找慢，插入刪除快(底層結(jié)構(gòu)是哈希表和紅黑樹)

Set集合使用equals()和hashcode()去重

ArrayList和LinkedList區(qū)別：

實現(xiàn):

1.LinkedList:雙鏈表?

?ArrayList:動態(tài)數(shù)組

擴(kuò)容機(jī)制:

2.LinkedList:不存在擴(kuò)容

?ArrayList:動態(tài)數(shù)組存在擴(kuò)容說法，默認(rèn)的數(shù)組大小是10，在檢測是否需要擴(kuò)容后，如果擴(kuò)容，會擴(kuò)容為原來的???

?1.5倍大小。原理就是把老數(shù)組的元素存儲到新數(shù)組里面(每次擴(kuò)容會造成數(shù)據(jù)遷移,效率變低)

優(yōu)點(diǎn):

3.LinkedList:刪除插入效率高

?ArrayList:查找效率高

缺點(diǎn):

4.LinekdList:鏈表，在內(nèi)存中地址不是連續(xù)的，通過指針連接結(jié)點(diǎn)，如果要查找，必須遍歷整個鏈表，效率很低

??ArrayList:在內(nèi)存中是一塊連續(xù)的地址，如果進(jìn)行刪除插入操作，會使該位置前后的元素全部移動，代價很高；

安全角度:

5.LinkedList:非線程安全

?ArrayList:非線程安全

vector：線程安全

LinkedList和ArrayList的數(shù)據(jù)存儲都是有序的，而且元素是可以重復(fù)的。

兩者add都是將元素追加到現(xiàn)有集合元素的末尾。

List接口獨(dú)有的方法均與索引(index)有關(guān)，這是因為List接口代表的是列表類型，以線性方式存儲對象

ArrayList集合：（底層實現(xiàn)動態(tài)數(shù)組）

??1、默認(rèn)初始化容量10（底層先創(chuàng)建了一個長度為0的數(shù)組，當(dāng)添加第一個元素的時候，初始化容量10。）

??2、集合底層是一個Object[]數(shù)組。

??3、構(gòu)造方法：

????new ArrayList();

????new ArrayList(20);

??4、ArrayList集合的擴(kuò)容：

????增長到原容量的1.5倍。

????ArrayList集合底層是數(shù)組，怎么優(yōu)化？

??????盡可能少的擴(kuò)容。因為數(shù)組擴(kuò)容效率比較低，建議在使用ArrayList集合

??????的時候預(yù)估計元素的個數(shù)，給定一個初始化容量。

??5、數(shù)組優(yōu)點(diǎn)：

????檢索效率比較高。（每個元素占用空間大小相同，內(nèi)存地址是連續(xù)的，知道首元素內(nèi)存地址，

????然后知道下標(biāo)，通過數(shù)學(xué)表達(dá)式計算出元素的內(nèi)存地址，所以檢索效率最高。）

??6、數(shù)組缺點(diǎn)：

????隨機(jī)增刪元素效率比較低。

????另外數(shù)組無法存儲大數(shù)據(jù)量。（很難找到一塊非常巨大的連續(xù)的內(nèi)存空間。）

??7、向數(shù)組末尾添加元素，效率很高，不受影響。

??8、面試官經(jīng)常問的一個問題？

????這么多的集合中，你用哪個集合最多？

??????答：ArrayList集合。

??????因為往數(shù)組末尾添加元素，效率不受影響。

??????另外，我們檢索/查找某個元素的操作比較多。

??7、ArrayList集合是非線程安全的。（不是線程安全的集合。）

LinkedList集合:(底層實現(xiàn)，雙向鏈表，適合插入刪除)

特有的方法：

addFirst()//在頭部添加

addLast()//在尾部添加

getFirst()//得到頭部數(shù)據(jù)

getLast()//得到尾部數(shù)據(jù)