2. 基礎(chǔ)篇
2.1. 數(shù)組：從 0 開始編號
- 數(shù)組尋址用到偏移量蔚叨，a[0] 為偏移為 0 的首地址，a[k] 為偏移 k 個(gè) type_size 的位置，若從 1 開始編號，a[k]的位置變?yōu)槠?k-1豁跑，多了一次減法運(yùn)算
a[k]_address = base_address + k * type_size
數(shù)組作為非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)泻云，通過下標(biāo)隨機(jī)訪問數(shù)組元素又是其非惩模基礎(chǔ)的編程操作，效率的優(yōu)化就要盡可能做到極致宠纯。所以為了減少一次減法操作卸夕，數(shù)組選擇了從 0 開始編號，而不是從 1 開始
- 歷史原因婆瓜，Java快集、JavaScript 沿用 C 語言從 0 開始計(jì)數(shù)的習(xí)慣，降低程序員學(xué)習(xí)的成本
- Matlab 數(shù)組下標(biāo)從 1 開始
- Python 數(shù)組下標(biāo)從 0 開始勃救，但 -1 表示最后一行元素
數(shù)據(jù)結(jié)構(gòu)類型：
數(shù)組（Array）：
- 線性表數(shù)據(jù)結(jié)構(gòu)
- 連續(xù)的內(nèi)存空間
- 相同類型的數(shù)據(jù)
2 + 3 → 數(shù)組支持隨機(jī)訪問，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為O(1)
低效的插入與刪除：平均時(shí)間復(fù)雜度為 O(n)
插入操作：無序情況下治力，插入到第 k 個(gè)位置蒙秒，可把原來第 k 個(gè)位置的元素移動(dòng)到數(shù)組末尾，如此時(shí)間復(fù)雜度為O(1)
刪除操作：記錄元素已刪除宵统，當(dāng)數(shù)組滿后再真正執(zhí)行搬移數(shù)據(jù)的操作（批量刪除）
例：JVM 標(biāo)記清除垃圾回收算法晕讲，缺點(diǎn)：產(chǎn)生內(nèi)存碎片
很多時(shí)候我們并不是要去死記硬背某個(gè)數(shù)據(jù)結(jié)構(gòu)或者算法覆获，而是要學(xué)習(xí)它背后的思想和處理技巧，這些東西才是最有價(jià)值的瓢省。
數(shù)組越界問題：
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
若編譯器按照內(nèi)存地址遞減的方式分配內(nèi)存弄息，局部變量連續(xù)壓棧，arr[3] 越界訪問到變量 i勤婚，將其重置為 0
數(shù)組越界在 C 語言 中是一種未決行為摹量，但 Java 會做越界檢查
容器：封裝操作細(xì)節(jié)
- C++ STL 中的vector
- Java 中的 ArrayList
容器的優(yōu)勢：
- ArrayList封裝數(shù)組操作細(xì)節(jié)
- ArrayList支持動(dòng)態(tài)擴(kuò)容，缺點(diǎn)：耗時(shí)馒胆，建議指定數(shù)據(jù)大小
數(shù)組的不可替代之處：
- ArrayList無法存儲基本類型缨称，需封裝為類，造成性能消耗
- 數(shù)據(jù)大小已知且操作簡單的情況下祝迂，直接使用數(shù)組較為方便
- 多維數(shù)組的定義更直觀睦尽，容器套容器過于復(fù)雜，Object[][] array VS. ArrayList< ArrayList < object> > array
總結(jié)：
- 業(yè)務(wù)開發(fā)用容器型雳，損耗部分不影響整體
- 底層開發(fā)用數(shù)組当凡，優(yōu)化網(wǎng)絡(luò)框架的性能
引申：
for (int i = 0; i < n; i++)的寫法，比起for (int i = 0; i <= n - 1; i++)纠俭，能夠直接看出有 n - 0 = n 個(gè)數(shù)據(jù)沿量，更為直觀二維數(shù)組 a[m][n] 的內(nèi)存尋址公式
a[i][j]_address = base_address + (i * n + j) * type_size
- JVM 標(biāo)記清除算法：運(yùn)行在 JVM 上的 Java 程序，若堆內(nèi)存被耗盡柑晒，則 GC 線程被觸發(fā)并將程序暫停欧瘪，執(zhí)行標(biāo)記/清除，再讓程序恢復(fù)運(yùn)行
- 標(biāo)記：遍歷所有的 GC Roots匙赞，將所有 GC Roots 可達(dá)的對象標(biāo)記為存活
- 清除：遍歷堆中所有對象佛掖，將沒有標(biāo)記的對象清除
缺點(diǎn)：1.效率問題，標(biāo)記和清除過程效率不高涌庭；2.空間問題芥被，產(chǎn)生不連續(xù)的內(nèi)存空間碎片
