比較JavaScript中的資料結構（陣列與物件）

作者：Vivek Bisht
譯者：前端小智
來源：blog
移動端閱讀：https://mp.weixin.qq.com/s/nbYsKonWtLNK95jMd4dY-A

點贊再看，微信搜索 【大遷世界】 關注這個沒有大廠背景，但有著一股向上積極心態人，本文 GitHub https://github.com/qq449245884/xiaozhi 上已經收錄，文章的已分類，也整理了很多我的檔案，和教程資料，

大家都說簡歷沒專案寫，我就幫大家找了一個專案，還附贈【搭建教程】，

在編程中，如果你想繼續深入，資料結構是我們必須要懂的一塊， 學習/理解資料結構的動機可能會有所不同，一方面可能是為了面試，一方面可能單單是為了提高自己的技能或者是專案需要，無論動機是什么，如果不知道什么是陣列結構及何時使用應用字們，那學資料結構是一項繁瑣且無趣的程序 😵

這篇文章討論了什么時候使用它們，在本文中，我們將學習陣列和物件，我們將嘗試通過使用Big O notation來理解何時選擇一種資料結構，

Big O notation 大零符號一般用于描述演算法的復雜程度，比如執行的時間或占用記憶體（磁盤）的空間等，特指最壞時的情形，

陣列

陣列是使用最廣泛的資料結構之一， 陣列中的資料以有序的方式進行結構化，即陣列中的第一個元素存盤在索引0中，第二個元素存盤在索引1中，依此類推， JavaScript為我們提供了一些內置的資料結構，陣列就是其中之一 👌

在JavaScript中，定義陣列最簡單的方法是：

let arr = []

上面的代碼行創建了一個動態陣列（長度未知），為了了解如何將陣列的元素存盤在記憶體中，我們來看一個示例：

let arr = ['John', 'Lily', 'William', 'Cindy']

在上面的示例中，我們創建一個包含一些人名的陣列， 記憶體中的名稱按以下方式存盤：

為了理解陣列是如何作業的，我們需要執行一些操作：

添加元素：

在JavaScript陣列中，我們有不同方式在陣列結尾，開關以及特定索引處添加元素，

在陣列的末尾添加一個元素：

JavaScript 中的陣列有一個默認屬性 length，它表示陣列的長度，除了length屬性外，JS還提供了 push() 方法， 使用這個方法，我們可以直接在最后添加一個元素，

arr.push('Jake')

那么這個命令的復雜度是多少呢?我們知道，在默認情況下，JS提供了length屬性，push()相當于使用以下命令:

arr[arr.length - 1] = 'Jake'

因為我們總是可以訪問陣列的長度屬性，所以無論陣列有多大，在末尾添加一個元素的復雜度總是O(1) 👏，

在陣列的開頭添加一個元素：

對于此操作，JavaScript提供了一個稱為unshift()的默認方法，此方法將元素添加到陣列的開頭，

let arr = ['John', 'Lily', 'William', 'Cindy']
arr.unshift('Robert')
console.log(arr) // [ 'Robert', 'John', 'Lily', 'William', 'Cindy' ]

unshift方法復雜度好像和push方法的復雜度一樣：O(1)，因為我們只是在前面添加一個元素， 事實并非如此，讓我們看一下使用unshift方法時會發生什么：

在上圖中，當我們使用unshift方法時，所有元素的索引應該增加1，這里我們的陣列個數比較少，看不出存在的問題，想象一下使用一個相當長的陣列，然后，使用unshift這樣的方法會導致延遲，因為我們必須移動陣列中每個元素的索引，因此，unshift操作的復雜度為O(n) 😋，

如果要處理較大長度的陣列，請明智地使用unshift方法，在特定索引處添加元素，我們可以 splice() 方法，它的語法如下：

splice(startingIndex, deleteCount, elementToBeInserted)

因為我們要添加一個元素，所以deleteCount將為0，例如， 我們想要在陣列索引為2的地方新加一個元素，可以這么用：

let arr = ['John', 'Lily', 'William', 'Cindy']
arr.splice(2, 0, 'Janice')
console.log(arr)
// [ 'John', 'Lily', 'Janice', 'William', 'Cindy' ]

你覺得這個操作的復雜性是多少?在上面的操作中，我們在索引2處添加了元素，因此，在索引2之后的所有后續元素都必須增加或移動1(包括之前在索引2處的元素)，

可以觀察到，我們不是在移動或遞增所有元素的索引，而是在索引2之后遞增元素的索引，這是否意味著該操作的復雜度為 `O(n/2)？ 不是 😮， 根據Big O規則，常量可以從復雜性中洗掉，而且，我們應該考慮最壞的情況， 因此，該操作的復雜度為O(n) 😳，

洗掉元素：

就像添加元素一樣，洗掉元素可以在不同的位置完成，在末尾、開始和特定索引處，

在陣列的末尾洗掉一個元素：

像 push( )一樣，JavaScript提供了一個默認方法pop()，用于洗掉/洗掉陣列末尾的元素，

let arr = ['Janice', 'Gillian', 'Harvey', 'Tom']
arr.pop()
console.log(arr)
// [ 'Janice', 'Gillian', 'Harvey' ]

arr.pop()
console.log(arr)
// [ 'Janice', 'Gillian' ]

該操作的復雜度為O(1)，因為，無論陣列有多大，洗掉最后一個元素都不需要改變陣列中任何元素的索引，

在陣列的開頭洗掉一個元素：

JavaScript 提供了一個默認方法shift() 的默認方法，此方法洗掉陣列的第一個元素，

let arr = ['John', 'Lily','William','Cindy']
arr.shift()
console.log(arr) // ['Lily','William','Cindy']
arr.shift()
console.log(arr);// ['William','Cindy'] 

從上面我們很容易可以看出 shift()操作的復雜度為O(n) ，因為洗掉第一個元素后，我們必須將所有元素的索引移位或減量1，

在特定索引處洗掉:

對于此操作，我們再次使用splice()方法，不過這一次，我們只使用前兩個引數，因為我們不打算在該索引處添加新元素，

let arr = ['Apple', 'Orange', 'Pear', 'Banana','Watermelon']
arr.splice(2,1)
console.log(arr) // ['Apple', 'Orange', 'Banana','Watermelon']

與用splice添加元素操作類似，在此操作中，我們將遞級訓移動索引2之后的元素索引，所以復雜度是O(n)，

查找元素：

查找只是訪問陣列的一個元素，我們可以通過使用方括號符號(例如: arr[4])來訪問陣列的元素，

你認為這個操作的復雜性是什么？ 我們通過一個例子來演示一下：

let fruits = ['Apple', 'Orange', 'Pear']

前面我們已經看到，陣列的所有元素都按順序存盤，并且始終分組在一起， 因此，如果執行fruits1，它將告訴計算機找到名為fruits的陣列并獲取第二個元素（陣列從索引0開始），

由于它們是按順序存盤的，因此計算機不必查看整個記憶體即可找到該元素，因為所有元素按順序分組在一起，因此它可以直接在fruits陣列內部查看， 因此，陣列中的查找操作的復雜度為 O(1)，

我們已經完成了對陣列的基本操作，我們先來小結一下什么時候可以使用陣列：

當你要執行像push()(在末尾添加元素)和pop()(從末尾洗掉元素)這樣的操作時，陣列是合適的，因為這些操作的復雜度是O(1)，

除此之外，查找操作可以在陣列中非常快地執行，

使用陣列時，執行諸如在特定索引處或在開頭添加/洗掉元素之類的操作可能會非常慢，因為它們的復雜度為O(n)，

物件

像陣列一樣，物件也是最常用的資料結構之一， 物件是一種哈希表，允許我們存盤鍵值對，而不是像在陣列中看到的那樣將值存盤在編號索引處，

定義物件的最簡單方法是：

let obj1 = {}

事例：

let student = {
    name: 'Vivek',
    age: 13,
    class: 8
}

來看一下上面的物件是如何存盤在記憶體中的：

可以看到，物件的鍵-值對是隨機存盤的，不像陣列中所有元素都存盤在一起，這也是陣列與物件的主要區別，在物件中，鍵-值對隨機存盤在記憶體中，

我們還看到有一個哈希函式(hash function)， 那么這個哈希函式做什么呢？ 哈希函式從物件中獲取每個鍵，并生成一個哈希值，然后將此哈希值轉換為地址空間，在該地址空間中存盤鍵值對，

例如，如果我們向學生物件添加以下鍵值對：

student.rollNumber = 322

rollNumber鍵通過哈希函式，然后轉換為存盤鍵和值的地址空間，現在我們已經對物件如何存盤在記憶體有了基本的了解，讓我們來執行一些操作，

添加

對于物件，我們沒有單獨的方法將元素添加到前面或后面，因為所有的鍵-值對都是隨機存盤的，只有一個操作是向物件添加一個新的鍵值對，

事例：

student.parentName = 'Narendra Singh Bisht'

從上圖中我們可以得出結論，這個操作的復雜性總是O(1)，因為我們不需要改變任何索引或操作物件本身，我們可以直接添加一個鍵-值對，它被存盤在一個隨機的地址空間，

洗掉

與添加元素一樣，物件的洗掉操作非常簡單，復雜度為O(1)，因為，我們不必在洗掉時更改或操作物件，

delete student.parentName

查找

查找的復雜度O(1) ，因為在這里，我們也只是借助鍵來訪問值，訪問物件中的值的一種方法：

student.class

在物件中添加，洗掉和查找的復雜度為O(1)???那么我們可以得出結論，我們應該每次都使用物件而不是陣列嗎？ 答案是不， 盡管物件很棒，但是在使用物件時需要考慮一些小的情況，就是哈希碰撞(Hash Collisions)， 在使用物件時，并非始終應處理此情況，但了解該情況有助于我們更好地理解物件，

那么什么是哈希碰撞?

當我們定義一個物件時，我們的計算機會在記憶體中為該物件分配一些空間， 我們需要記住，我們記憶體中的空間是有限的，因此有可能兩個或更多鍵值對可能具有相同的地址空間，這種情況稱為哈希碰撞， 為了更好地理解它，我們看一個例子：

假設為下面的物件分配了5塊空間

我們觀察到兩個鍵值對存盤在相同的地址空間中， 怎么會這樣？當哈希函式回傳一個哈希值，該哈希值轉換為多個鍵的相同地址空間時，就會發生這種情況， 因此，多個 key 被映射到相同的地址空間， 由于哈希碰撞，添加和訪問物件值的復雜度為O(n) ，因為要訪問特定值，我們可能必須遍歷各種鍵值對，

哈希碰撞并不是我們每次使用物件時都需要處理的東西， 這只是一個特殊的情況，該情況也說明了物件不是完美的資料結構，

除了*哈希碰撞，使用物件時還必須注意另一種情況， JS 為我們提供了一個內置的keys()方法，用于遍歷物件的鍵，

我們可以將此方法應用于任何物件，例如：object1.keys()， keys()方法遍歷物件并回傳所有鍵， 盡管此方法看起來很簡單，但我們需要了解物件中的鍵值對是隨機存盤在記憶體中的，因此，遍歷物件的程序變得較慢，這與遍歷按順序將它們分組在一起的陣列不同，

總結一下，當我們想執行諸如添加，洗掉和訪問元素之類的操作時，可以使用物件，但是在使用物件時，我們需要謹慎地遍歷物件，因為這可能很耗時， 除了進行遍歷外，我們還應該理解，有時由于哈希碰撞，訪問物件操作的復雜度可能會變為O(n)，

代碼部署后可能存在的BUG沒法實時知道，事后為了解決這些BUG，花了大量的時間進行log 除錯，這邊順便給大家推薦一個好用的BUG監控工具 Fundebug，

原文：https://blog.soshace.com/comparing-data-structures-in-javascript-arrays-vs-objects/

交流

文章每周持續更新，可以微信搜索 【大遷世界 】 第一時間閱讀，回復 【福利】 有多份前端視頻等著你，本文 GitHub https://github.com/qq449245884/xiaozhi 已經收錄，歡迎Star，