滴滴-測(cè)試開發(fā)面經(jīng)（二）

1、堆棧空間分配

棧（操作系統(tǒng)）：由操作系統(tǒng)自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。

堆（操作系統(tǒng)）：一般由程序員分配釋放， 若程序員不釋放，程序結(jié)束時(shí)可能由OS回收，分配方式倒是類似于鏈表。

2、堆棧緩存方式

棧使用的是一級(jí)緩存， 他們通常都是被調(diào)用時(shí)處于存儲(chǔ)空間中，調(diào)用完畢立即釋放。

堆則是存放在二級(jí)緩存中，生命周期由虛擬機(jī)的垃圾回收算法來決定（并不是一旦成為孤兒對(duì)象就能被回收）。所以調(diào)用這些對(duì)象的速度要相對(duì)來得低一些。

3、效率比較

棧由系統(tǒng)自動(dòng)分配，速度較快。但程序員是無(wú)法控制的。

堆是由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過用起來最方便。

4、存儲(chǔ)內(nèi)容

棧：在函數(shù)調(diào)用時(shí)，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的。

當(dāng)本次函數(shù)調(diào)用結(jié)束后，局部變量先出棧，然后是參數(shù)，最后棧頂指針指向函數(shù)的返回地址，也就是主函數(shù)中的下一條指令的地址，程序由該點(diǎn)繼續(xù)運(yùn)行。

堆：一般是在堆的頭部用一個(gè)字節(jié)存放堆的大小。堆中的具體內(nèi)容由程序員安排。

String 類中的屬性value為byte數(shù)組，被private，final修飾

由此可以知道String的三個(gè)不可變特性

①底層是數(shù)組，代表String類的長(zhǎng)度不可變；

②final修飾，代表數(shù)組地址不可變，內(nèi)存引用不可變；

③private修飾，表示屬性私有，數(shù)組中的內(nèi)容不能被修改，只能在本類中訪問；

String str=new String(“abc”);創(chuàng)建了幾個(gè)對(duì)象？

在類加載時(shí)“abc"將會(huì)在常量池中被創(chuàng)建，其次調(diào)用new時(shí)，JVM命令將會(huì)調(diào)用String的構(gòu)造函數(shù)。同時(shí)引用常量池中"abc"字符串，在堆內(nèi)存中創(chuàng)建一個(gè)String對(duì)象！

什么時(shí)候方法不能被重寫

①，父類中用final修飾方法，代表這個(gè)方法不能被覆蓋；

②，父類中用static修飾方法，這個(gè)方法屬于靜態(tài)方法，而重寫只適用于實(shí)例方法；

③，父類中private修飾方法，也不能 重寫，因?yàn)樗接凶宇惪床坏健?/span>

1、Integer是int的包裝類，int則是java的一種基本數(shù)據(jù)類型 

2、Integer變量必須實(shí)例化后才能使用，而int變量不需要 

3、Integer實(shí)際是對(duì)象的引用，當(dāng)new一個(gè)Integer時(shí)，實(shí)際上是生成一個(gè)指針指向此對(duì)象；而int則是直接存儲(chǔ)數(shù)據(jù)值 

4、Integer的默認(rèn)值是null，int的默認(rèn)值是0

延伸： 

關(guān)于Integer和int的比較 

1、由于Integer變量實(shí)際上是對(duì)一個(gè)Integer對(duì)象的引用，所以兩個(gè)通過new生成的Integer變量永遠(yuǎn)是不相等的（因?yàn)閚ew生成的是兩個(gè)對(duì)象，其內(nèi)存地址不同）。

Integer i = new Integer(100);

Integer j = new Integer(100);

System.out.print(i == j); //false

2、Integer變量和int變量比較時(shí)，只要兩個(gè)變量的值是向等的，則結(jié)果為true（因?yàn)榘b類Integer和基本數(shù)據(jù)類型int比較時(shí)，java會(huì)自動(dòng)拆包裝為int，然后進(jìn)行比較，實(shí)際上就變?yōu)閮蓚€(gè)int變量的比較）

Integer i = new Integer(100);

int j = 100；

System.out.print(i == j); //true

3、非new生成的Integer變量和new Integer()生成的變量比較時(shí)，結(jié)果為false。（因?yàn)?①當(dāng)變量值在-128~127之間時(shí)，非new生成的Integer變量指向的是java常量池中的對(duì)象，而new Integer()生成的變量指向堆中新建的對(duì)象，兩者在內(nèi)存中的地址不同；②當(dāng)變量值在-128~127之間時(shí)，非new生成Integer變量時(shí)，java API中最終會(huì)按照new Integer(i)進(jìn)行處理（參考下面第4條），最終兩個(gè)Interger的地址同樣是不相同的）

Integer i = new Integer(100);

Integer j = 100;

System.out.print(i == j); //false

4、對(duì)于兩個(gè)非new生成的Integer對(duì)象，進(jìn)行比較時(shí)，如果兩個(gè)變量的值在區(qū)間-128到127之間，則比較結(jié)果為true，如果兩個(gè)變量的值不在此區(qū)間，則比較結(jié)果為false

Integer i = 100;

Integer j = 100;

System.out.print(i == j); //true

Integer i = 128;

Integer j = 128;

System.out.print(i == j); //false

對(duì)于第4條的原因： 

java在編譯Integer i = 100 ;時(shí)，會(huì)翻譯成為Integer i = Integer.valueOf(100)；，而java API中對(duì)Integer類型的valueOf的定義如下：

public static Integer valueOf(int i){

    assert IntegerCache.high >= 127;

    if (i >= IntegerCache.low && i <= IntegerCache.high){

        return IntegerCache.cache[i + (-IntegerCache.low)];

    }

    return new Integer(i);

}

java對(duì)于-128到127之間的數(shù)，會(huì)進(jìn)行緩存，Integer i = 127時(shí)，會(huì)將127進(jìn)行緩存，下次再寫Integer j = 127時(shí)，就會(huì)直接從緩存中取，就不會(huì)new了。

數(shù)組

一、數(shù)組的特點(diǎn)

1.在內(nèi)存中，數(shù)組是一塊連續(xù)的區(qū)域

2.數(shù)組需要預(yù)留空間

在使用前需要提前申請(qǐng)所占內(nèi)存的大小，這樣不知道需要多大的空間，就預(yù)先申請(qǐng)可能會(huì)浪費(fèi)內(nèi)存空間，即數(shù)組空間利用率低

ps：數(shù)組的空間在編譯階段就需要進(jìn)行確定，所以需要提前給出數(shù)組空間的大?。ㄔ谶\(yùn)行階段是不允許改變的）

3.在數(shù)組起始位置處，插入數(shù)據(jù)和刪除數(shù)據(jù)效率低。

插入數(shù)據(jù)時(shí)，待插入位置的的元素和它后面的所有元素都需要向后搬移

刪除數(shù)據(jù)時(shí)，待刪除位置后面的所有元素都需要向前搬移

4.隨機(jī)訪問效率很高，時(shí)間復(fù)雜度可以達(dá)到O(1)

因?yàn)閿?shù)組的內(nèi)存是連續(xù)的，想要訪問那個(gè)元素，直接從數(shù)組的首地址處向后偏移就可以訪問到了

5.數(shù)組開辟的空間，在不夠使用的時(shí)候需要擴(kuò)容，擴(kuò)容的話，就會(huì)涉及到需要把舊數(shù)組中的所有元素向新數(shù)組中搬移

6.數(shù)組的空間是從棧分配的

二、數(shù)組的優(yōu)點(diǎn)

隨機(jī)訪問性強(qiáng)，查找速度快，時(shí)間復(fù)雜度為O(1)

三、數(shù)組的缺點(diǎn)

1.頭插和頭刪的效率低，時(shí)間復(fù)雜度為O(N)

2.空間利用率不高

3.內(nèi)存空間要求高，必須有足夠的連續(xù)的內(nèi)存空間

4.數(shù)組空間的大小固定，不能動(dòng)態(tài)拓展

鏈表

一、鏈表的特點(diǎn)

1.在內(nèi)存中，元素的空間可以在任意地方，空間是分散的，不需要連續(xù)

2.鏈表中的元素都會(huì)兩個(gè)屬性，一個(gè)是元素的值，另一個(gè)是指針，此指針標(biāo)記了下一個(gè)元素的地址

每一個(gè)數(shù)據(jù)都會(huì)保存下一個(gè)數(shù)據(jù)的內(nèi)存的地址，通過此地址可以找到下一個(gè)數(shù)據(jù)

3.查找數(shù)據(jù)時(shí)效率低,時(shí)間復(fù)雜度為O(N)

因?yàn)殒湵淼目臻g是分散的，所以不具有隨機(jī)訪問性，如要需要訪問某個(gè)位置的數(shù)據(jù)，需要從第一個(gè)數(shù)據(jù)開始找起，依次往后遍歷，直到找到待查詢的位置，故可能在查找某個(gè)元素時(shí)，時(shí)間復(fù)雜度達(dá)到O(N)

4.空間不需要提前指定大小，是動(dòng)態(tài)申請(qǐng)的，根據(jù)需求動(dòng)態(tài)的申請(qǐng)和刪除內(nèi)存空間，擴(kuò)展方便，故空間的利用率較高

5.任意位置插入元素和刪除元素效率較高，時(shí)間復(fù)雜度為O(1)

6.鏈表的空間是從堆中分配的

二、鏈表的優(yōu)點(diǎn)

1.任意位置插入元素和刪除元素的速度快，時(shí)間復(fù)雜度為O(1)

2.內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存

3.鏈表的空間大小不固定，可以動(dòng)態(tài)拓展

三、鏈表的缺點(diǎn)

隨機(jī)訪問效率低，時(shí)間復(fù)雜度為0(N)

綜上：

對(duì)于想要快速訪問數(shù)據(jù)，不經(jīng)常有插入和刪除元素的時(shí)候，選擇數(shù)組

對(duì)于需要經(jīng)常的插入和刪除元素，而對(duì)訪問元素時(shí)的效率沒有很高要求的話，選擇鏈表