建站
咨詢
售后
建站咨詢
新聞中心
在編程中，如果你想繼續(xù)深入，數(shù)據(jù)結(jié)構(gòu)是我們必須要懂的一塊， 學(xué)習(xí)/理解數(shù)據(jù)結(jié)構(gòu)的動(dòng)機(jī)可能會(huì)有所不同，一方面可能是為了面試，一方面可能單單是為了提高自己的技能或者是項(xiàng)目需要。無論動(dòng)機(jī)是什么，如果不知道什么是數(shù)組結(jié)構(gòu)及何時(shí)使用應(yīng)用字們，那學(xué)數(shù)據(jù)結(jié)構(gòu)是一項(xiàng)繁瑣且無趣的過程
這篇文章討論了什么時(shí)候使用它們。在本文中，我們將學(xué)習(xí)數(shù)組和對(duì)象。我們將嘗試通過使用Big O notation來理解何時(shí)選擇一種數(shù)據(jù)結(jié)構(gòu)。
Big O notation 大零符號(hào)一般用于描述算法的復(fù)雜程度，比如執(zhí)行的時(shí)間或占用內(nèi)存(磁盤)的空間等，特指最壞時(shí)的情形。
數(shù)組
數(shù)組是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。數(shù)組中的數(shù)據(jù)以有序的方式進(jìn)行結(jié)構(gòu)化，即數(shù)組中的第一個(gè)元素存儲(chǔ)在索引0中，第二個(gè)元素存儲(chǔ)在索引1中，依此類推。JavaScript為我們提供了一些內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，數(shù)組就是其中之一
在JavaScript中，定義數(shù)組最簡(jiǎn)單的方法是：
- let arr = []
上面的代碼行創(chuàng)建了一個(gè)動(dòng)態(tài)數(shù)組(長(zhǎng)度未知)，為了了解如何將數(shù)組的元素存儲(chǔ)在內(nèi)存中，我們來看一個(gè)示例：
- let arr = ['John', 'Lily', 'William', 'Cindy']
在上面的示例中，我們創(chuàng)建一個(gè)包含一些人名的數(shù)組。內(nèi)存中的名稱按以下方式存儲(chǔ)：
為了理解數(shù)組是如何工作的，我們需要執(zhí)行一些操作：
添加元素：
在JavaScript數(shù)組中，我們有不同方式在數(shù)組結(jié)尾，開關(guān)以及特定索引處添加元素。
在數(shù)組的末尾添加一個(gè)元素：
JavaScript 中的數(shù)組有一個(gè)默認(rèn)屬性 length，它表示數(shù)組的長(zhǎng)度。除了length屬性外，JS還提供了 push() 方法。使用這個(gè)方法，我們可以直接在最后添加一個(gè)元素。
- arr.push('Jake')
那么這個(gè)命令的復(fù)雜度是多少呢?我們知道，在默認(rèn)情況下，JS提供了length屬性，push()相當(dāng)于使用以下命令:
- arr[arr.length - 1] = 'Jake'
因?yàn)槲覀兛偸强梢栽L問數(shù)組的長(zhǎng)度屬性，所以無論數(shù)組有多大，在末尾添加一個(gè)元素的復(fù)雜度總是O(1) 。
在數(shù)組的開頭添加一個(gè)元素：
對(duì)于此操作，JavaScript提供了一個(gè)稱為unshift()的默認(rèn)方法，此方法將元素添加到數(shù)組的開頭。
- let arr = ['John', 'Lily', 'William', 'Cindy']
- arr.unshift('Robert')
- console.log(arr) // [ 'Robert', 'John', 'Lily', 'William', 'Cindy' ]
unshift方法復(fù)雜度好像和push方法的復(fù)雜度一樣：O(1)，因?yàn)槲覀冎皇窃谇懊嫣砑右粋€(gè)元素。事實(shí)并非如此，讓我們看一下使用unshift方法時(shí)會(huì)發(fā)生什么：
在上圖中，當(dāng)我們使用unshift方法時(shí)，所有元素的索引應(yīng)該增加1。這里我們的數(shù)組個(gè)數(shù)比較少，看不出存在的問題。想象一下使用一個(gè)相當(dāng)長(zhǎng)的數(shù)組，然后，使用unshift這樣的方法會(huì)導(dǎo)致延遲，因?yàn)槲覀儽仨氁苿?dòng)數(shù)組中每個(gè)元素的索引。因此，unshift操作的復(fù)雜度為O(n) 。
如果要處理較大長(zhǎng)度的數(shù)組，請(qǐng)明智地使用unshift方法。在特定索引處添加元素，我們可以 splice() 方法，它的語法如下：
- splice(startingIndex, deleteCount, elementToBeInserted)
因?yàn)槲覀円砑右粋€(gè)元素，所以deleteCount將為0。例如， 我們想要在數(shù)組索引為2的地方新加一個(gè)元素，可以這么用：
- let arr = ['John', 'Lily', 'William', 'Cindy']
- arr.splice(2, 0, 'Janice')
- console.log(arr)
- // [ 'John', 'Lily', 'Janice', 'William', 'Cindy' ]
你覺得這個(gè)操作的復(fù)雜性是多少?在上面的操作中，我們?cè)谒饕?處添加了元素，因此，在索引2之后的所有后續(xù)元素都必須增加或移動(dòng)1(包括之前在索引2處的元素)。
可以觀察到，我們不是在移動(dòng)或遞增所有元素的索引，而是在索引2之后遞增元素的索引。這是否意味著該操作的復(fù)雜度為 `O(n/2)?不是 。根據(jù)Big O規(guī)則，常量可以從復(fù)雜性中刪除，而且，我們應(yīng)該考慮最壞的情況。因此，該操作的復(fù)雜度為O(n) 。
刪除元素：
就像添加元素一樣，刪除元素可以在不同的位置完成，在末尾、開始和特定索引處。
在數(shù)組的末尾刪除一個(gè)元素：
像 push( )一樣，JavaScript提供了一個(gè)默認(rèn)方法pop()，用于刪除/刪除數(shù)組末尾的元素。
- let arr = ['Janice', 'Gillian', 'Harvey', 'Tom']
- arr.pop()
- console.log(arr)
- // [ 'Janice', 'Gillian', 'Harvey' ]
- arr.pop()
- console.log(arr)
- // [ 'Janice', 'Gillian' ]
該操作的復(fù)雜度為O(1)。因?yàn)椋瑹o論數(shù)組有多大，刪除最后一個(gè)元素都不需要改變數(shù)組中任何元素的索引。
在數(shù)組的開頭刪除一個(gè)元素：
JavaScript 提供了一個(gè)默認(rèn)方法shift() 的默認(rèn)方法，此方法刪除數(shù)組的第一個(gè)元素。
- let arr = ['John', 'Lily','William','Cindy']
- arr.shift()
- console.log(arr) // ['Lily','William','Cindy']
- arr.shift()
- console.log(arr);// ['William','Cindy']
從上面我們很容易可以看出 shift()操作的復(fù)雜度為O(n) ，因?yàn)閯h除第一個(gè)元素后，我們必須將所有元素的索引移位或減量1。
在特定索引處刪除:
對(duì)于此操作，我們?cè)俅问褂胹plice()方法，不過這一次，我們只使用前兩個(gè)參數(shù)，因?yàn)槲覀儾淮蛩阍谠撍饕幪砑有略亍?/p>
- let arr = ['Apple', 'Orange', 'Pear', 'Banana','Watermelon']
- arr.splice(2,1)
- console.log(arr) // ['Apple', 'Orange', 'Banana','Watermelon']
與用splice添加元素操作類似，在此操作中，我們將遞減或移動(dòng)索引2之后的元素索引，所以復(fù)雜度是O(n)。
查找元素：
查找只是訪問數(shù)組的一個(gè)元素，我們可以通過使用方括號(hào)符號(hào)(例如: arr[4])來訪問數(shù)組的元素。
你認(rèn)為這個(gè)操作的復(fù)雜性是什么?我們通過一個(gè)例子來演示一下：
- let fruits = ['Apple', 'Orange', 'Pear']
前面我們已經(jīng)看到，數(shù)組的所有元素都按順序存儲(chǔ)，并且始終分組在一起。因此，如果執(zhí)行fruits[1]，它將告訴計(jì)算機(jī)找到名為fruits的數(shù)組并獲取第二個(gè)元素(數(shù)組從索引0開始)。
由于它們是按順序存儲(chǔ)的，因此計(jì)算機(jī)不必查看整個(gè)內(nèi)存即可找到該元素，因?yàn)樗性匕错樞蚍纸M在一起，因此它可以直接在fruits數(shù)組內(nèi)部查看。因此，數(shù)組中的查找操作的復(fù)雜度為 O(1)。
我們已經(jīng)完成了對(duì)數(shù)組的基本操作，我們先來小結(jié)一下什么時(shí)候可以使用數(shù)組：
當(dāng)你要執(zhí)行像push()(在末尾添加元素)和pop()(從末尾刪除元素)這樣的操作時(shí)，數(shù)組是合適的，因?yàn)檫@些操作的復(fù)雜度是O(1)。
除此之外，查找操作可以在數(shù)組中非常快地執(zhí)行。
使用數(shù)組時(shí)，執(zhí)行諸如在特定索引處或在開頭添加/刪除元素之類的操作可能會(huì)非常慢，因?yàn)樗鼈兊膹?fù)雜度為O(n)。
對(duì)象
像數(shù)組一樣，對(duì)象也是最常用的數(shù)據(jù)結(jié)構(gòu)之一。對(duì)象是一種哈希表，允許我們存儲(chǔ)鍵值對(duì)，而不是像在數(shù)組中看到的那樣將值存儲(chǔ)在編號(hào)索引處。
定義對(duì)象的最簡(jiǎn)單方法是：
- let obj1 = {}
事例：
- let student = {
- name: 'Vivek',
- age: 13,
- class: 8
- }
來看一下上面的對(duì)象是如何存儲(chǔ)在內(nèi)存中的：
可以看到，對(duì)象的鍵-值對(duì)是隨機(jī)存儲(chǔ)的，不像數(shù)組中所有元素都存儲(chǔ)在一起。這也是數(shù)組與對(duì)象的主要區(qū)別，在對(duì)象中，鍵-值對(duì)隨機(jī)存儲(chǔ)在內(nèi)存中。
我們還看到有一個(gè)哈希函數(shù)(hash function)。那么這個(gè)哈希函數(shù)做什么呢?哈希函數(shù)從對(duì)象中獲取每個(gè)鍵，并生成一個(gè)哈希值，然后將此哈希值轉(zhuǎn)換為地址空間，在該地址空間中存儲(chǔ)鍵值對(duì)。
例如，如果我們向?qū)W生對(duì)象添加以下鍵值對(duì)：
- student.rollNumber = 322
rollNumber鍵通過哈希函數(shù)，然后轉(zhuǎn)換為存儲(chǔ)鍵和值的地址空間?，F(xiàn)在我們已經(jīng)對(duì)對(duì)象如何存儲(chǔ)在內(nèi)存有了基本的了解，讓我們來執(zhí)行一些操作。
添加
對(duì)于對(duì)象，我們沒有單獨(dú)的方法將元素添加到前面或后面，因?yàn)樗械逆I-值對(duì)都是隨機(jī)存儲(chǔ)的。只有一個(gè)操作是向?qū)ο筇砑右粋€(gè)新的鍵值對(duì)。
事例：
- student.parentName = 'Narendra Singh Bisht'
從上圖中我們可以得出結(jié)論，這個(gè)操作的復(fù)雜性總是O(1)，因?yàn)槲覀儾恍枰淖內(nèi)魏嗡饕虿僮鲗?duì)象本身，我們可以直接添加一個(gè)鍵-值對(duì)，它被存儲(chǔ)在一個(gè)隨機(jī)的地址空間。
刪除
與添加元素一樣，對(duì)象的刪除操作非常簡(jiǎn)單，復(fù)雜度為O(1)。因?yàn)?，我們不必在刪除時(shí)更改或操作對(duì)象。
- delete student.parentName
查找
查找的復(fù)雜度O(1) ，因?yàn)樵谶@里，我們也只是借助鍵來訪問值。訪問對(duì)象中的值的一種方法：
- student.class
在對(duì)象中添加，刪除和查找的復(fù)雜度為O(1)???那么我們可以得出結(jié)論，我們應(yīng)該每次都使用對(duì)象而不是數(shù)組嗎?答案是不。盡管對(duì)象很棒，但是在使用對(duì)象時(shí)需要考慮一些小的情況，就是哈希碰撞(Hash Collisions)。在使用對(duì)象時(shí)，并非始終應(yīng)處理此情況，但了解該情況有助于我們更好地理解對(duì)象。
那么什么是哈希碰撞?
當(dāng)我們定義一個(gè)對(duì)象時(shí)，我們的計(jì)算機(jī)會(huì)在內(nèi)存中為該對(duì)象分配一些空間。我們需要記住，我們內(nèi)存中的空間是有限的，因此有可能兩個(gè)或更多鍵值對(duì)可能具有相同的地址空間，這種情況稱為哈希碰撞。為了更好地理解它，我們看一個(gè)例子：
假設(shè)為下面的對(duì)象分配了5塊空間
我們觀察到兩個(gè)鍵值對(duì)存儲(chǔ)在相同的地址空間中。怎么會(huì)這樣?當(dāng)哈希函數(shù)返回一個(gè)哈希值，該哈希值轉(zhuǎn)換為多個(gè)鍵的相同地址空間時(shí)，就會(huì)發(fā)生這種情況。因此，多個(gè) key 被映射到相同的地址空間。由于哈希碰撞，添加和訪問對(duì)象值的復(fù)雜度為O(n) ，因?yàn)橐L問特定值，我們可能必須遍歷各種鍵值對(duì)。
哈希碰撞并不是我們每次使用對(duì)象時(shí)都需要處理的東西。這只是一個(gè)特殊的情況，該情況也說明了對(duì)象不是完美的數(shù)據(jù)結(jié)構(gòu)。
除了*哈希碰撞，使用對(duì)象時(shí)還必須注意另一種情況。JS 為我們提供了一個(gè)內(nèi)置的keys()方法，用于遍歷對(duì)象的鍵。
我們可以將此方法應(yīng)用于任何對(duì)象，例如：object1.keys()。keys()方法遍歷對(duì)象并返回所有鍵。盡管此方法看起來很簡(jiǎn)單，但我們需要了解對(duì)象中的鍵值對(duì)是隨機(jī)存儲(chǔ)在內(nèi)存中的，因此，遍歷對(duì)象的過程變得較慢，這與遍歷按順序?qū)⑺鼈兎纸M在一起的數(shù)組不同。
總結(jié)一下，當(dāng)我們想執(zhí)行諸如添加，刪除和訪問元素之類的操作時(shí)，可以使用對(duì)象，但是在使用對(duì)象時(shí)，我們需要謹(jǐn)慎地遍歷對(duì)象，因?yàn)檫@可能很耗時(shí)。除了進(jìn)行遍歷外，我們還應(yīng)該理解，有時(shí)由于哈希碰撞，訪問對(duì)象操作的復(fù)雜度可能會(huì)變?yōu)镺(n)。
本文轉(zhuǎn)載自微信公眾號(hào)「大遷世界」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系大遷世界公眾號(hào)。
當(dāng)前標(biāo)題：比較JavaScript中的數(shù)據(jù)結(jié)構(gòu)（數(shù)組與對(duì)象）
鏈接URL：http://m.fisionsoft.com.cn/article/cdgjpcd.html
