線性結構
線性結構是一個有序資料元素的集合，資料之間的關系是1:1 的關系如：
平時常用的線性結構有陣列、線性表、堆疊、佇列 如，
什么是陣列
陣列是計算機分配一塊連續的記憶體空間，來存盤具有相同元素型別的資料，陣列具有隨機訪問的特點，這個特點有利有弊，比如可以根據陣列下標快速的訪問元素，但是要想在陣列中洗掉、插入一個資料，為了保證連續性，就需要做大量的資料移動，
特點
- 陣列是一種線性表結構，即就像資料排成一條線一樣的結構，每個線性表上的資料最多只有前和后
- 連續的記憶體空間和相同型別的資料
陣列如何實作隨機訪問
陣列在記憶體中地址是連續、以及相同的資料型別，所以我們只要知道記憶體首地址以及資料型別的大小，就能知道對應索引的元素地址，如一個長度為 10 的 int 型別的陣列 int[] a = new int[10]來舉例，在這個圖中，計算機給陣列 a[10]，分配了一塊連續記憶體空間 1000～1039，其中，記憶體塊的首地址為 base_address = 1000，
計算機會給每個記憶體單元分配一個地址，計算機通過地址來訪問記憶體中的資料，當計算機需要隨機訪問陣列中的某個元素時，它會首先通過下面的尋址公式，計算出該元素存盤的記憶體地址：
1 // 首地址 + 需要訪問的下標的偏移值 2 a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示陣列中每個元素的大小，舉的這個例子里，陣列中存盤的是 int 型別資料，所以 data_type_size 就為 4 個位元組，
因為陣列是連續存盤的，所以根據首地址和下標，通過尋址公式就能直接計算出對應的記憶體地址，找出資料，
1 // 訪問第三個元素的地址 2 a[3] = 1000 + (3 - 1) * 4 = 1008 - 1011
陣列的下標為什么要從0開始
根據上面陣列尋址公式，因為地址是連續、且資料型別是相同的，所以下標其實就是一個偏移值，如果用a來表示陣列的首地址，那么a[0]就是偏移為0的位置，也就是首地址，a[x]就是表示偏移x個type_size的位置所以計算 a[k]的記憶體地址只需要用這個公式：
1 a[x]_address = base_address + x * type_size
但是，如果陣列從 1 開始計數，那我們計算陣列元素 a[k]的記憶體地址就會變為：
1 a[x]_address = base_address + (k-1) * type_size
對比兩個公式，如果從 1 開始編號，每次隨機訪問陣列元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令，陣列作為非常基礎的資料結構，通過下標隨機訪問陣列元素又是其非常基礎的編程操作，效率的優化就要盡可能做到極致，所以為了減少一次減法操作，陣列選擇了從 0 開始編號，而不是從 1 開始，
javaScript 中的陣列
JavaScript 中的陣列有很多特性：存放不同型別元素、并且陣列長度可變，這與資料結構中定義的陣列結構或者C++、Java、C#等語言中的陣列不太一樣，那么JS陣列的這些特殊的特性底層是如何實作的呢？可以理解為V8中對陣列做了一層封裝，使其有兩種實作方式：快陣列和慢陣列，快陣列底層是連續記憶體，通過索引直接定位，慢陣列底層是哈希表，通過計算哈希值來定位，具體的可以看看這個《探究JS V8引擎下的“陣列”底層實作》
無論是慢陣列、快陣列被實作成了key、value物件的形式，so，檢查陣列型別是一個物件，
Object.prototype.toString([]) // "[object Object]"
參考：
《探究JS V8引擎下的“陣列”底層實作》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/277637.html
標籤：JavaScript
上一篇：CSS樣式中的各種居中方式