一.為何編程語(yǔ)言的數(shù)組下標(biāo)從0開(kāi)始

1.從數(shù)組內(nèi)存存儲(chǔ)類(lèi)型來(lái)看，數(shù)組的下標(biāo)可以看作“偏移量”--offset；如果a為首地址，那么a[0] 就是偏移量為0的位置。
2.歷史原因：C 語(yǔ)言設(shè)計(jì)者用 0 開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)，之后的 Java等其它語(yǔ)言開(kāi)始使用，這樣節(jié)省了學(xué)習(xí)成本。
3 . 內(nèi)存地址計(jì)算方法：

• 一維數(shù)組：a[k]_address = base_address + k * type_size
• 二維數(shù)組：二維數(shù)組假設(shè)是mn， a[i][j]_address=base_address + (in+j)*type_size
• 三維數(shù)組：假設(shè)mnq， a[i][j][k]_address=base_address + (inq + jq + k)type_size

二.如何實(shí)現(xiàn)隨機(jī)訪(fǎng)問(wèn)

1.數(shù)組

• 一種線(xiàn)性表，每個(gè)線(xiàn)性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。
• 連續(xù)的內(nèi)存空間和相同的數(shù)據(jù)類(lèi)型。
• 這兩種限制同時(shí)賦予了數(shù)組一種特質(zhì)：隨機(jī)訪(fǎng)問(wèn)；但為了保衡數(shù)據(jù)的連續(xù)性，那么插入，刪除操作變得低效，需要對(duì)數(shù)據(jù)進(jìn)行搬運(yùn)行為。

2.數(shù)組如何實(shí)現(xiàn)下標(biāo)的隨機(jī)訪(fǎng)問(wèn)

• 計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，通過(guò)地址來(lái)訪(fǎng)問(wèn)內(nèi)存。計(jì)算機(jī)需要隨機(jī)訪(fǎng)問(wèn)數(shù)組中的某個(gè)元素時(shí)，它會(huì)首先通過(guò)下面的尋址方法尋找：
  a[k]_address = base_address + k * type_size

• 數(shù)組和鏈表的區(qū)別糾錯(cuò)
  數(shù)組是適合查找操作，但是查找的時(shí)間復(fù)雜度并不為 O(1).數(shù)組支持隨機(jī)訪(fǎng)問(wèn)，根據(jù)下標(biāo)的 隨機(jī)訪(fǎng)問(wèn)的時(shí)間復(fù)雜度為O(1).

三.一些別的思考

• 插入操作：
  如果數(shù)組中數(shù)據(jù)時(shí)無(wú)序的，而且只當(dāng)作一種存儲(chǔ)集合，為了避免大規(guī)模的數(shù)據(jù)搬運(yùn)，可以直接將第K位的數(shù)據(jù)搬運(yùn)到數(shù)組的最后。
• 刪除操作：
  不必追求數(shù)組中的數(shù)據(jù)的連續(xù)性，將多次刪除操作集中在一起，刪除的效率會(huì)提高。因?yàn)槊恳淮蝿h除后，都要重新搬運(yùn)數(shù)據(jù)（為了內(nèi)存的連續(xù)性）。
  我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬運(yùn)數(shù)據(jù)，而是做一個(gè)已刪除的標(biāo)記，等到存儲(chǔ)空間沒(méi)有更多的空間時(shí)，一次性刪除被標(biāo)記的數(shù)據(jù)。-----JVM的標(biāo)記清理垃圾回收算法的核心思想。
• 數(shù)組的下標(biāo)越界問(wèn)題。
  C語(yǔ)言中的數(shù)組下標(biāo)越界是一種未決行為，沒(méi)有規(guī)定下標(biāo)越界時(shí)編譯器應(yīng)該如何處理。因?yàn)樵L(fǎng)問(wèn)數(shù)組的本質(zhì)就是方位一段連續(xù)的內(nèi)存地址，只要數(shù)組通過(guò)計(jì)算偏移后得到的地址時(shí)可用的，就不會(huì)報(bào)錯(cuò)。
  JAVA中本身就會(huì)檢測(cè)下標(biāo)越界，拋出異常。

四.數(shù)組和容器

比如數(shù)組和ArrayList容器。

• 容器的優(yōu)勢(shì)
  將很多數(shù)組操作的細(xì)節(jié)隱藏起來(lái)。實(shí)現(xiàn)了動(dòng)態(tài)擴(kuò)容。
• 數(shù)組的優(yōu)勢(shì)
  容器無(wú)法存儲(chǔ)基礎(chǔ)類(lèi)型int等，只能包裝后Integer使用，浪費(fèi)了性能。更關(guān)注性能，一般用于底層開(kāi)發(fā)。

五.標(biāo)記清除垃圾回收算法

基本算法：

• 由標(biāo)記階段 和 清除階段構(gòu)成
• 標(biāo)記將所有的活動(dòng)的對(duì)象打上標(biāo)記。
• 清除即將將那些沒(méi)有標(biāo)記的對(duì)象進(jìn)行回收。

標(biāo)記與清除

• 遍歷GC,ROOT引用，遞歸標(biāo)記（設(shè)置對(duì)象頭中的標(biāo)志位）對(duì)象；
• 標(biāo)記時(shí)如果標(biāo)記位已被標(biāo)記已跳過(guò)
• 遍歷對(duì)象有深度優(yōu)先遍歷和廣度優(yōu)先遍歷，其搜索步驟一致，但是深度優(yōu)先的內(nèi)存使用量更小，因此一般使用深度優(yōu)先遍歷。
• 清除階段將再次遍歷堆，未標(biāo)記的對(duì)象加入到空閑表中，標(biāo)記的對(duì)象則出區(qū)標(biāo)記。

分配與合并

• 分配指mutator申請(qǐng)分塊時(shí)獲取內(nèi)存塊的過(guò)程。
• 分配即通過(guò)搜索空閑鏈表，找到一個(gè)大小合適的塊。分配測(cè)量有如下：First-fit，找到第一個(gè)大于要求大小的塊即返回；Best-fit，找到比要求大小大的最小塊；Worst-fit，找出最大的塊將其分割成要求大小塊和剩余的，一般不使用(容易產(chǎn)生碎片)。
• 對(duì)于內(nèi)存中連續(xù)的垃圾可以對(duì)其進(jìn)行合并，減少碎片。

優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)：
  1.算法實(shí)現(xiàn)簡(jiǎn)單。
  2.與保守式GC算法兼容(對(duì)象不能被移動(dòng))。
• 缺點(diǎn)
  1. 碎片化。
  2. 分配速度慢，每次分配需要遍歷空閑鏈表。
  3. 與寫(xiě)時(shí)復(fù)制(copy-on-write)沖突，因?yàn)樽鯣C時(shí)需要將對(duì)象頭進(jìn)行標(biāo)記，這將導(dǎo)致大量的數(shù)據(jù)發(fā)生復(fù)制
  4. STW(Stop-The-World)長(zhǎng)，兩個(gè)階段均要遍歷整個(gè)堆。