編者按：本文轉載自眾成翻譯，譯者 sea_ljf
當開發程序時，我們（通常）需要在內存中存儲數據。根據操作數據方式的不同，可能會選擇不同的數據結構。有很多常用的數據結構，如：Array、Map、Set、List、Tree、Graph 等等。（然而）為程序選取合適的數據結構可能並不容易。因此，希望這篇文章能幫助你了解（不同數據結構的）表現，以求在工作中合理地使用它們。
本文主要聚焦於線性的數據結構，如：Array、Set、List、Sets、Stacks、Queues 等等。
本篇是以下教程的一部分（譯者註：如果大家覺得還不錯，我會翻譯整個系列的文章）:
初學者應該了解的數據結構與算法（DSA）
算法的時間複雜性與大 O 符號
每個程式設計師應該知道的八種時間複雜度
初學者應該了解的數據結構：Array、HashMap 與 List 👈 即本文
初學者應該了解的數據結構： Graph
初學者應該了解的數據結構：Tree (敬請期待)
附錄 I：遞歸算法分析
（操作）數據結構的時間複雜度下表是本文所討論內容的概括。
* = 運行時分攤
數據結構插入訪問查找刪除備註ArrayO(n)O(1)O(n)O(n)插入最後位置複雜度為O(1)。(Hash)MapO(1)*O(1)*O(1)*O(1)*重新計算哈希會影響插入時間。MapO(log(n))-O(log(n))O(log(n))通過二叉搜索樹實現Set（使用 HashMap）O(1）*-O(1)*O(1)*由 HashMap 實現Set (使用 List)O(n)-O(n)]O(n)通過 List 實現Set (使用二叉搜索樹)O(log(n))-O(log(n))O(log(n))通過二叉搜索樹實現Linked List (單向)O(n)-O(n)O(n)在起始位置添加或刪除元素，複雜度為O(1)Linked List (雙向）O(n)-O(n)O(n)在起始或結尾添加或刪除元素，複雜度為O(1)。然而在其他位置是O(n)。Stack (由 Array 實現)O(1)--O(1)]插入與刪除都遵循與後進先出（LIFO）Queue (簡單地由 Array 實現)O(n)--O(1)插入（Array.shift）操作的複雜度是 O(n)Queue (由 Array 實現，但進行了改進)O(1)*--O(1)插入操作的最差情況複雜度是 O(n)。然而分攤後是 O(1)Queue (由 List 實現)O(1)--O(1)使用雙向鍊表注意： 二叉搜索樹 與其他樹結構、圖結構，將在另一篇文章中討論。
原始數據類型原始數據類型是構成數據結構最基礎的元素。下面列舉出一些原始原始數據類型：
整數，如：1, 2, 3, …
字符，如：a, b, "1", "*"
布爾值， true 與 false.
浮點數 ，如：3.14159, 1483e-2.
Array數組可由零個或多個元素組成。由於數組易於使用且檢索性能優越，它是最常用的數據結構之一。
你可以將數組想像成一個抽屜，可以將數據存到匣子中。
數組就像是將東西存到匣子中的抽屜
當你想查找某個元素時，你可以直接打開對應編號的匣子（時間複雜度為 O(1)）。然而，如果你忘記了匣子裡存著什麼，就必須逐個打開所有的匣子（時間複雜度為 O(n)），直到找到所需的東西。數組也是如此。
根據程式語言的不同，數組存在一些差異。對於 JavaScript 和 Ruby 等動態語言而言，數組可以包含不同的數據類型：數字，字符串，對象甚至函數。而在 Java 、 C 、C ++ 之類的強類型語言中，你必須在使用數組之前，定好它的長度與數據類型。JavaScript 會在需要時自動增加數組的長度。
Array 的內置方法根據編程序言的不同，數組（方法）的實現稍有不同。
比如在 JavaScript 中，我們可以使用 unshift 與 push 添加元素到數組的頭或尾，同時也可以使用 shift 與 pop 刪除數組的首個或最後一個元素。讓我們來定義一些本文用到的數組常用方法。
常用的 JS 數組內置函數
函數複雜度描述array.push(element1[, …[, elementN]])O(1)將一個或多個元素添加到數組的末尾array.pop()O(1)移除數組末尾的元素array.shift()O(n)移除數組開頭的元素array.unshift(element1[, …[, elementN]])O(n)將一個或多個元素添加到數組的開頭array.slice([beginning[, end]])O(n)返回淺拷貝原數組從 beginning 到 end（不包括 end）部分組成的新數組array.splice(start[, deleteCount[, item1[,…]]])O(n)改變 (插入或刪除) 數組向數組插入元素將元素插入到數組有很多方式。你可以將新數據添加到數組末尾，也可以添加到數組開頭。
先看看如何添加到末尾：
function insertToTail(array, element) {
array.push(element);
return array;
}
const array = [1, 2, 3];
console.log(insertToTail(array, 4));
根據規範，push 操作只是將一個新元素添加到數組的末尾。因此，
Array.push 的時間複雜度度是 O(1)。
現在看看如添加到開頭：
function insertToHead(array, element) {
array.unshift(element);
return array;
}
const array = [1, 2, 3];
console.log(insertToHead(array, 0));
你覺得添加元素到數組開頭的函數，時間複雜度是什麼呢？看起來和上面（push）差不多，除了調用的方法是 unshift 而不是 push。但這有個問題，unshift 是通過將數組的每一項移到下一項，騰出首項的空間來容納新添加的元素。所以它是遍歷了一次數組的。
Array.unshift 的時間複雜度度是 O(n)。
訪問數組中的元素如果你知道待查找元素在數組中的索引，那你可以通過以下方法直接訪問該元素：
function access(array, index) {
return array[index];
}
const array = [1, 'word', 3.14, { a: 1 }];
access(array, 0);
access(array, 3);
正如上面你所看到的的代碼一樣，訪問數組中的元素耗時是恆定的：
訪問數組中元素的時間複雜度是 O(1)。
注意：通過索引修改數組的值所花費的時間也是恆定的。
在數組中查找元素如果你想查找某個元素但不知道對應的索引時，那只能通過遍歷數組的每個元素，直到找到為止。
function search(array, element) {
for (let index = 0;
index < array.length;
index++) {
if (element === array[index]) {
return index;
}
}
}
const array = [1, 'word', 3.14, { a: 1 }];
console.log(search(array, 'word'));
console.log(search(array, 3.14));
鑑於使用了 for 循環，那麼：
在數組中查找元素的時間複雜度是 O(n)
在數組中刪除元素你覺得從數組中刪除元素的時間複雜度是什麼呢？
先一起思考下這兩種情況：
從數組的末尾刪除元素所需時間是恆定的，也就是 O(1)。
然而，無論是從數組的開頭或是中間位置刪除元素，你都需要調整（刪除元素後面的）元素位置。因此複雜度為 O(n)。
說多無謂，看代碼好了：
function remove(array, element) {
const index = search(array, element);
array.splice(index, 1);
return array;
}
const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1));
我們使用了上面定義的 search 函數來查找元素的的索引，複雜度為 O(n)。然後使用JS 內置的 splice 方法，它的複雜度也是 O(n)。那（刪除函數）總的時間複雜度不是 O(2n) 嗎?記住，（對於時間複雜度而言，）我們並不關心常量。
對於上面列舉的兩種情況，考慮最壞的情況：
在數組中刪除某項元素的時間複雜度是 O(n)。
數組方法的時間複雜度在下表中，小結了數組（方法）的時間複雜度：
數組方法的時間複雜度
操作方法最壞情況訪問 (Array.[])O(1)添加新元素至開頭 (Array.unshift)O(n)添加新元素至末尾 (Array.push)O(1)查找 (通過值而非索引)O(n)刪除 (Array.splice)O(n)HashMapsHashMap有很多名字，如 HashTable、HashMap、Map、Dictionary、Associative Array 等。概念上它們都是一致的，實現上稍有不同。
哈希表是一種將鍵 映射到 值的數據結構。
回想一下關於抽屜的比喻，現在匣子有了標籤，不再是按數字順序了。
HashMap 也和抽屜一樣存儲東西，通過不同標識來區分不同匣子。
此例中，如果你要找一個玩具，你不需要依次打開第一個、第二個和第三個匣子來查看玩具是否在內。直接代開被標識為「玩具」的匣子即可。這是一個巨大的進步，查找元素的時間複雜度從 O(n) 降為 O(1) 了。
數字是數組的索引，而標識則作為 HashMap 存儲數據的鍵。HashMap 內部通過 哈希函數 將鍵（也就是標識）轉化為索引。
至少有兩種方式可以實現 hashmap：
數組：通過哈希函數將鍵映射為數組的索引。（查找）最差情況： O(n)，平均： O(1)。
二叉搜索樹: 使用自平衡二叉搜索樹查找值（另外的文章會詳細介紹）。 （查找）最差情況： O(log n)，平均：O(log n)。
我們會介紹樹與二叉搜索樹，現在先不用擔心太多。實現 Map 最常用的方式是使用 數組與哈希轉換函數。讓我們（通過數組）來實現它吧
通過數組實現 HashMap
正如上圖所示，每個鍵都被轉換為一個 hash code。由於數組的大小是有限的（如此例中是10），（如發生衝突，）我們必須使用模函數找到對應的桶（譯者註：桶指的是數組的項），再循環遍歷該桶（來尋找待查詢的值）。每個桶內，我們存儲的是一組組的鍵值對，如果桶內存儲了多個鍵值對，將採用集合來存儲它們。
我們將講述 HashMap 的組成，讓我們先從哈希函數開始吧。
哈希函數實現 HashMap 的第一步是寫出一個哈希函數。這個函數會將鍵映射為對應（索引的）值。
完美的哈希函數 是為每一個不同的鍵映射為不同的索引。
藉助理想的哈希函數，可以實現訪問與查找在恆定時間內完成。然而，完美的哈希函數在實踐中是難以實現的。你很可能會碰到兩個不同的鍵被映射為同一索引的情況，也就是 衝突。
當使用類似數組之類的數據結構作為 HashMap 的實現時，衝突是難以避免的。因此，解決衝突的其中一種方式是在同一個桶中存儲多個值。當我們試圖訪問某個鍵對應的值時，如果在對應的桶中發現多組鍵值對，則需要遍歷它們（以尋找該鍵對應的值），時間複雜度為 O(n)。然而，在大多數（HashMap）的實現中， HashMap 會動態調整數組的長度以免衝突發生過多。因此我們可以說分攤後的查找時間為 O(1)。本文中我們將通過一個例子，講述分攤的含義。
HashMap 的簡單實現一個簡單（但糟糕）的哈希函數可以是這樣的：
class NaiveHashMap {
constructor(initialCapacity = 2) {
this.buckets = new Array(initialCapacity);
}
set(key, value) {
const index = this.getIndex(key);
this.buckets[index] = value;
}
get(key) {
const index = this.getIndex(key);
return this.buckets[index];
}
hash(key) {
return key.toString().length;
}
getIndex(key) {
const indexHash = this.hash(key);
const index = indexHash % this.buckets.length;
return index;
}
}
完整代碼
我們直接使用桶而不是抽屜與匣子，相信你能明白喻義的意思 :)
HashMap 的初始容量（譯者註：容量指的是用於存儲數據的數組長度，即桶的數量）是2（兩個桶）。當我們往裡面存儲多個元素時，通過求餘 % 計算出該鍵應存入桶的編號（，並將數據存入該桶中）。
留意代碼的第18行（即 return key.toString().length;）。之後我們會對此進行一點討論。現在先讓我們使用一下這個新的 HashMap 吧。
const assert = require('assert');
const hashMap = new NaiveHashMap();
hashMap.set('cat', 2);
hashMap.set('rat', 7);
hashMap.set('dog', 1);
hashMap.set('art', 8);
console.log(hashMap.buckets);
bucket #0: <1 empty item>,
bucket #1: 8
*/
assert.equal(hashMap.get('art'), 8);
assert.equal(hashMap.get('cat'), 8);
assert.equal(hashMap.get('rat'), 8);
assert.equal(hashMap.get('dog'), 8);
這個 HashMap 允許我們通過 set 方法設置一組鍵值對，通過往 get 方法傳入一個鍵來獲取對應的值。其中的關鍵是哈希函數，當我們存入多組鍵值時，看看這 HashMap 的表現。
你能說出這個簡單實現的 HashMap 存在的問題嗎？
1) Hash function 轉換出太多相同的索引。如：
hash('cat')
hash('dog')
這會產生非常多的衝突。
2) 完全不處理衝突的情況。cat 與 dog 會重寫彼此在 HashMap 中的值（它們均在桶 #1 中）。
3 數組長度。 即使我們有一個更好的哈希函數，由於數組的長度是2，少於存入元素的數量，還是會產生很多衝突。我們希望 HashMap 的初始容量大於我們存入數據的數量。
改進哈希函數HashMap 的主要目標是將數組查找與訪問的時間複雜度，從 O(n) 降至 O(1)。
為此，我們需要：
一個合適的哈希函數，儘可能地減少衝突。
一個長度足夠大的數組用於保存數據。
讓我們重新設計哈希函數，不再採用字符串的長度為 hash code，取而代之是使用字符串中每個字符的ascii 碼的總和為 hash code。
hash(key) {
let hashValue = 0;
const stringKey = key.toString();
for (let index = 0; index < stringKey.length; index++) {
const charCode = stringKey.charCodeAt(index);
hashValue += charCode;
}
return hashValue;
}
再試一次：
hash('cat')
hash('dog')
這函數比之前的要好！這是因為相同長度的單詞由不一樣的字母組成，因而 ascii 碼的總和不一樣。
然而，仍然有問題！單詞 rat 與 art 轉換後都是327，產生衝突了！ 💥
可以通過根據字符位置左移它的 ascii 碼來解決：
hash(key) {
let hashValue = 0;
const stringKey = `${key}`;
for (let index = 0; index < stringKey.length; index++) {
const charCode = stringKey.charCodeAt(index);
hashValue += charCode << (index * 8);
}
return hashValue;
}
現在繼續試驗，下面列舉出了十六進位的數字，這樣可以方便我們觀察位移。
hash('rat');
hash('art');
然而，以下兩種類型有何不同呢？
hash(1);
hash('1');
hash('1,2,3');
hash([1,2,3]);
hash('undefined')
hash(undefined)
天啊，仍然有問題！！不同的數據類型不應該返回相同的 hash code！
該如何解決呢？
其中一種方式是在哈希函數中，將數據的類型作為轉換 hash code 的一部分。
hash(key) {
let hashValue = 0;
const stringTypeKey = `${key}${typeof key}`;
for (let index = 0; index < stringTypeKey.length; index++) {
const charCode = stringTypeKey.charCodeAt(index);
hashValue += charCode << (index * 8);
}
return hashValue;
}
讓我們讓我們再試一次：
console.log(hash(1));
console.log(hash('1'));
console.log(hash('1,2,3'));
console.log(hash([1,2,3]));
console.log(hash('undefined'));
console.log(hash(undefined));
Yay!!! 🎉 我們終於有了更好的哈希函數！
同時，我們可以改變 HashMap 的原始容量以減少衝突，讓我們在下一節中優化 HashMap。
更完善的 HashMap 實現通過優化好的哈希函數，HashMap 可以表現得更好。
儘管衝突仍可能發生，但通過一些方式可以很好地處理它們。
對於我們的 HashMap，希望有以下改進：
更完善 HashMap 實現完整代碼
class DecentHashMap {
constructor(initialCapacity = 2) {
this.buckets = new Array(initialCapacity);
this.collisions = 0;
}
set(key, value) {
const bucketIndex = this.getIndex(key);
if(this.buckets[bucketIndex]) {
this.buckets[bucketIndex].push({key, value});
if(this.buckets[bucketIndex].length > 1) { this.collisions++; }
} else {
this.buckets[bucketIndex] = [{key, value}];
}
return this;
}
get(key) {
const bucketIndex = this.getIndex(key);
for (let arrayIndex = 0; arrayIndex < this.buckets[bucketIndex].length; arrayIndex++) {
const entry = this.buckets[bucketIndex][arrayIndex];
if(entry.key === key) {
return entry.value
}
}
}
hash(key) {
let hashValue = 0;
const stringTypeKey = `${key}${typeof key}`;
for (let index = 0; index < stringTypeKey.length; index++) {
const charCode = stringTypeKey.charCodeAt(index);
hashValue += charCode << (index * 8);
}
return hashValue;
}
getIndex(key) {
const indexHash = this.hash(key);
const index = indexHash % this.buckets.length;
return index;
}
}
看看這個 HashMap 表現如何：
const assert = require('assert');
const hashMap = new DecentHashMap();
hashMap.set('cat', 2);
hashMap.set('rat', 7);
hashMap.set('dog', 1);
hashMap.set('art', 8);
console.log('collisions: ', hashMap.collisions);
console.log(hashMap.buckets);
bucket #0: [ { key: 'cat', value: 2 }, { key: 'art', value: 8 } ]
bucket #1: [ { key: 'rat', value: 7 }, { key: 'dog', value: 1 } ]
*/
assert.equal(hashMap.get('art'), 8);
assert.equal(hashMap.get('cat'), 2);
assert.equal(hashMap.get('rat'), 7);
assert.equal(hashMap.get('dog'), 1);
完善後的 HashMap 很好地完成了工作，但仍然有一些問題。使用改良後的哈希函數不容易產生重複的值，這非常好。然而，在桶#0與桶#1中都有兩個值。這是為什麼呢？？
由於 HashMap 的容量是2，儘管算出來的 hash code 是不一樣的，當求餘後算出所需放進桶的編號時，結果不是桶#0就是桶#1。
hash('cat') => 3789411390; bucketIndex => 3789411390 % 2 = 0
hash('art') => 3789415740; bucketIndex => 3789415740 % 2 = 0
hash('dog') => 3788563007; bucketIndex => 3788563007 % 2 = 1
hash('rat') => 3789411405; bucketIndex => 3789411405 % 2 = 1
很自然地想到，可以通過增加 HashMap 的原始容量來解決這個問題，但原始容量應該是多少呢？先來看看容量是如何影響 HashMap 的表現的。
如果初始容量是1，那麼所有的鍵值對都會被存入同一個桶，即桶#0。查找操作並不比純粹用數組存儲數據的時間複雜度簡單，它們都是 O(n)。
而假設將初始容量定為10：
const hashMapSize10 = new DecentHashMap(10);
hashMapSize10.set('cat', 2);
hashMapSize10.set('rat', 7);
hashMapSize10.set('dog', 1);
hashMapSize10.set('art', 8);
console.log('collisions: ', hashMapSize10.collisions);
console.log('hashMapSize10\n', hashMapSize10.buckets);
bucket#0: [ { key: 'cat', value: 2 }, { key: 'art', value: 8 } ],
<4 empty items>,
bucket#5: [ { key: 'rat', value: 7 } ],
<1 empty item>,
bucket#7: [ { key: 'dog', value: 1 } ],
<2 empty items>
*/
換個角度看：
正如你所看到的，通過增加 HashMap 的容量，能有效減少衝突次數。
那換個更大的試試怎樣，比如 💯:
const hashMapSize100 = new DecentHashMap(100);
hashMapSize100.set('cat', 2);
hashMapSize100.set('rat', 7);
hashMapSize100.set('dog', 1);
hashMapSize100.set('art', 8);
console.log('collisions: ', hashMapSize100.collisions);
console.log('hashMapSize100\n', hashMapSize100.buckets);
<5 empty items>,
bucket#5: [ { key: 'rat', value: 7 } ],
<1 empty item>,
bucket#7: [ { key: 'dog', value: 1 } ],
<32 empty items>,
bucket#41: [ { key: 'art', value: 8 } ],
<49 empty items>,
bucket#90: [ { key: 'cat', value: 2 } ],
<9 empty items>
*/
Yay! 🎊 沒有衝突！
通過增加初始容量，可以很好的減少衝突，但會消耗更多的內存，而且很可能許多桶都沒被使用。
如果我們的 HashMap 能根據需要自動調整容量，這不是更好嗎？這就是所謂的rehash（重新計算哈希值），我們將在下一節將實現它！
優化HashMap 的實現如果 HashMap 的容量足夠大，那就不會產生任何衝突，因此查找操作的時間複雜度為 O(1)。然而，我們怎麼知道容量多大才是足夠呢，100？1000？還是一百萬？
（從開始就）分配大量的內存（去建立數組）是不合理的。因此，我們能做的是根據裝載因子動態地調整容量。這操作被稱為 rehash。
裝載因子是用于衡量一個 HashMap 滿的程度，可以通過存儲鍵值對的數量除以 HashMap 的容量得到它。
根據這思路，我們將實現最終版的 HashMap：
最佳的 HasnMap 實現
class HashMap {
constructor(initialCapacity = 16, loadFactor = 0.75) {
this.buckets = new Array(initialCapacity);
this.loadFactor = loadFactor;
this.size = 0;
this.collisions = 0;
this.keys = [];
}
hash(key) {
let hashValue = 0;
const stringTypeKey = `${key}${typeof key}`;
for (let index = 0; index < stringTypeKey.length; index++) {
const charCode = stringTypeKey.charCodeAt(index);
hashValue += charCode << (index * 8);
}
return hashValue;
}
_getBucketIndex(key) {
const hashValue = this.hash(key);
const bucketIndex = hashValue % this.buckets.length;
return bucketIndex;
}
set(key, value) {
const {bucketIndex, entryIndex} = this._getIndexes(key);
if(entryIndex === undefined) {
const keyIndex = this.keys.push({content: key}) - 1;
this.buckets[bucketIndex] = this.buckets[bucketIndex] || [];
this.buckets[bucketIndex].push({key, value, keyIndex});
this.size++;
if(this.buckets[bucketIndex].length > 1) { this.collisions++; }
} else {
this.buckets[bucketIndex][entryIndex].value = value;
}
if(this.loadFactor > 0 && this.getLoadFactor() > this.loadFactor) {
this.rehash(this.buckets.length * 2);
}
return this;
}
get(key) {
const {bucketIndex, entryIndex} = this._getIndexes(key);
if(entryIndex === undefined) {
return;
}
return this.buckets[bucketIndex][entryIndex].value;
}
has(key) {
return !!this.get(key);
}
_getIndexes(key) {
const bucketIndex = this._getBucketIndex(key);
const values = this.buckets[bucketIndex] || [];
for (let entryIndex = 0; entryIndex < values.length; entryIndex++) {
const entry = values[entryIndex];
if(entry.key === key) {
return {bucketIndex, entryIndex};
}
}
return {bucketIndex};
}
delete(key) {
const {bucketIndex, entryIndex, keyIndex} = this._getIndexes(key);
if(entryIndex === undefined) {
return false;
}
this.buckets[bucketIndex].splice(entryIndex, 1);
delete this.keys[keyIndex];
this.size--;
return true;
}
rehash(newCapacity) {
const newMap = new HashMap(newCapacity);
this.keys.forEach(key => {
if(key) {
newMap.set(key.content, this.get(key.content));
}
});
this.buckets = newMap.buckets;
this.collisions = newMap.collisions;
this.keys = newMap.keys;
}
getLoadFactor() {
return this.size / this.buckets.length;
}
}
完整代碼（譯者註：其實 has 方法有問題，只是不影響閱讀。）
注意第99行至第114行（即 rehash 函數），那裡是 rehash 魔法發生的地方。我們創造了一個新的 HashMap，它擁有原來 HashMap兩倍的容量。
測試一下上面的新實現吧：
const assert = require('assert');
const hashMap = new HashMap();
assert.equal(hashMap.getLoadFactor(), 0);
hashMap.set('songs', 2);
hashMap.set('pets', 7);
hashMap.set('tests', 1);
hashMap.set('art', 8);
assert.equal(hashMap.getLoadFactor(), 4/16);
hashMap.set('Pineapple', 'Pen Pineapple Apple Pen');
hashMap.set('Despacito', 'Luis Fonsi');
hashMap.set('Bailando', 'Enrique Iglesias');
hashMap.set('Dura', 'Daddy Yankee');
hashMap.set('Lean On', 'Major Lazer');
hashMap.set('Hello', 'Adele');
hashMap.set('All About That Bass', 'Meghan Trainor');
hashMap.set('This Is What You Came For', 'Calvin Harris ');
assert.equal(hashMap.collisions, 2);
assert.equal(hashMap.getLoadFactor(), 0.75);
assert.equal(hashMap.buckets.length, 16);
hashMap.set('Wake Me Up', 'Avicii');
assert.equal(hashMap.collisions, 0);
assert.equal(hashMap.getLoadFactor(), 0.40625);
assert.equal(hashMap.buckets.length, 32);
注意，在 HashMap 存儲了12項之後，裝載因子將超過0.75，因而觸發 rehash，HashMap 容量加倍（從16到32）。同時，我們也能看到衝突從2降低為0。
這版本實現的 HashMap 能以很低的時間複雜度進行常見的操作，如：插入、查找、刪除、編輯等。
小結一下，HashMap 的性能取決於：
哈希函數能根據不同的鍵輸出不同的值。
HashMap 容量的大小。
我們終於處理好了各種問題 🔨。有了不錯的哈希函數，可以根據不同輸入返回不同輸出。同時，我們也有 rehash 函數根據需要動態地調整 HashMap的容量。這實在太好了！
HashMap 中插入元素的時間複雜度往一個 HashMap 插入元素需要兩樣東西：一個鍵與一個值。可以使用上文開發優化後的 HashMap 或內置的對象進行操作：
function insert(object, key, value) {
object[key] = value;
return object;
}
const hash = {};
console.log(insert(hash, 'word', 1));
在新版的 JavaScript 中，你可以使用 Map。
function insertMap(map, key, value) {
map.set(key, value);
return map;
}
const map = new Map();
console.log(insertMap(map, 'word', 1));
注意。我們將使用 Map 而不是普通的對象，這是由於 Map 的鍵可以是任何東西而對象的鍵只能是字符串或者數字。此外，Map 可以保持插入的順序。
進一步說，Map.set 只是將元素插入到數組（如上文 DecentHashMap.set 所示），類似於 Array.push，因此可以說：
往 HashMap 中插入元素，時間複雜度是 O(1)。如果需要 rehash，那麼複雜度則是 O(n)。
rehash 能將衝突可能性降至最低。rehash 操作時間複雜度是 O(n) ，但不是每次插入操作都要執行，僅在需要時執行。
HashMap 中查找或訪問元素的時間複雜度這是 HashMap.get 方法，我們通過往裡面傳遞一個鍵來獲取對應的值。讓我們回顧一下 DecentHashMap.get 的實現：
get（key）{
const hashIndex = this .getIndex（key）;
const values = this .array [hashIndex];
for（let index = 0 ; index <values.length; index ++）{
const entry = values [index];
if（entry.key === key）{
返回 entry.value
}
}
}
如果並未發生衝突，那麼 values 只會有一個值，訪問的時間複雜度是 O(1)。但我們也知道，衝突總是會發生的。如果 HashMap 的初始容量太小或哈希函數設計糟糕，那麼大多數元素訪問的時間複雜度是 O(n)。
HashMap 訪問操作的時間複雜度平均是 O(1)，最壞情況是 O(n) 。
進階提示：另一個（將訪問操作的）時間複雜度從 O(n) 降至 O(log n) 的方法是使用 二叉搜索樹 而不是數組進行底層存儲。事實上，當存儲的元素超過8 個時， Java HashMap 的底層實現會從數組轉為樹。
HashMap 中修改或刪除元素的時間複雜度修改(HashMap.set)或刪除（HashMap.delete）鍵值對，分攤後的時間複雜度是 O(1)。如果衝突很多，可能面對的就是最壞情況，複雜度為 O(n)。然而伴隨著 rehash 操作，可以大大減少最壞情況的發生的機率。
HashMap 修改或刪除操作的時間複雜度平均是 O(1) ，最壞情況是 O(n)。
HashMap 方法的時間複雜度在下表中，小結了 HashMap（方法）的時間複雜度：
HashMap 方法的時間複雜度
操作方法最壞情況平均備註訪問或查找 (HashMap.get)O(n)O(1)O(n) 是衝突極多的極端情況插入或修改 (HashMap.set)O(n)O(1)O(n) 只發生在裝載因子超過0.75，觸發 rehash 時刪除 (HashMap.delete)O(n)O(1)O(n) 是衝突極多的極端情況Sets集合跟數組非常相像。它們的區別是集合中的元素是唯一的。
我們該如何實現一個集合呢（也就是沒有重複項的數組）？可以使用數組實現，在插入新元素前先檢查該元素是否存在。但檢查是否存在的時間複雜度是 O(n)。能對此進行優化嗎？之前開發的 Map （插入操作）分攤後時間複雜度度才 O(1)！
Set 的實現可以使用 JavaScript 內置的 Set。然而通過自己實現它，可以更直觀地了解它的時間複雜度。我們將使用上文優化後帶有 rehash 功能的 HashMap 來實現它。
const HashMap = require('../hash-maps/hash-map');
class MySet {
constructor() {
this.hashMap = new HashMap();
}
add(value) {
this.hashMap.set(value);
}
has(value) {
return this.hashMap.has(value);
}
get size() {
return this.hashMap.size;
}
delete(value) {
return this.hashMap.delete(value);
}
entries() {
return this.hashMap.keys.reduce((acc, key) => {
if(key !== undefined) {
acc.push(key.content);
}
return acc
}, []);
}
}
（譯者註：由於 HashMap 的 has 方法有問題，導致 Set 的 has 方法也有問題）
我們使用 HashMap.set 為集合不重複地添加元素。我們將待存儲的值作為 HashMap的鍵，由於哈希函數會將鍵映射為唯一的索引，因而起到排重的效果。
檢查一個元素是否已存在於集合中，可以使用 hashMap.has 方法，它的時間複雜度平均是 O(1)。集合中絕大多數的方法分攤後時間複雜度為 O(1)，除了 entries 方法，它的事件複雜度是 O(n)。
注意：使用 JavaScript 內置的集合時，它的 Set.has 方法時間複雜度是 O(n)。這是由於它的使用了 List 作為內部實現，需要檢查每一個元素。你可以在這查閱相關的細節。
下面有些例子，說明如何使用這個集合：
const assert = require('assert');
const set = new MySet();
set.add('one');
set.add('uno');
set.add('one');
assert.equal(set.has('one'), true);
assert.equal(set.has('dos'), false);
assert.equal(set.size, 2);
assert.equal(set.delete('one'), true);
assert.equal(set.delete('one'), false);
assert.equal(set.has('one'), false);
assert.equal(set.size, 1);
這個例子中，MySet 與 JavaScript 中內置的 Set 均可作為容器。
Set 方法的時間複雜度根據 HashMap 實現的的 Set，可以小結出的時間複雜度如下（與 HashMap 非常相似）：
Set 方法的時間複雜度
操作方法最壞情況平均備註訪問或查找 (Set.has)O(n)O(1)O(n) 是衝突極多的極端情況插入或修改 (Set.add)O(n)O(1)O(n) 只發生在裝載因子超過0.75，觸發 rehash 時刪除 (Set.delete)O(n)O(1)O(n)是衝突極多的極端情況)Linked Lists鍊表是一種一個節點連結到下一個節點的數據結構。
鍊表是（本文）第一種不用數組（作為底層）實現的數據結構。我們使用節點來實現，節點存儲了一個元素，並指向下一個節點（若沒有下一個節點，則為空）。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
當每個節點都指向它的下了一個節點時，我們就擁有了一條由若干節點組成鏈條，即單向鍊表。
Singly Linked Lists對於單向鍊表而言，我們只需關心每個節點都有指向下一個節點的引用。
從首個節點或稱之為根節點開始構建（單向鍊表）。
class LinkedList {
constructor() {
this.root = null;
}
}
每個鍊表都有四個基礎操作：
addLast：將一個元素添加至鍊表尾部。
removeLast：刪除鍊表的最後一個元素。
addFirst：將一個元素添加到鍊表的首部。
removeFirst：刪除鍊表的首個元素。
向鍊表末尾添加與刪除一個元素
（對添加操作而言，）有兩種情況。1）如果鍊表根節點不存在，那麼將新節點設置為鍊表的根節點。2）若存在根節點，則必須不斷查詢下一個節點，直到鍊表的末尾，並將新節點添加到最後。
addLast(value) {
const node = new Node(value);
if(this.root) {
let currentNode = this.root;
while(currentNode && currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
} else {
this.root = node;
}
}
上述代碼的時間複雜度是多少呢？如果是作為根節點添加進鍊表，時間複雜度是 O(1)，然而尋找最後一個節點的時間複雜度是 O(n).。
刪除末尾的節點與上述代碼相差無幾。
removeLast() {
let current = this.root;
let target;
if(current && current.next) {
while(current && current.next && current.next.next) {
current = current.next;
}
target = current.next;
current.next = null;
} else {
this.root = null;
target = current;
}
if(target) {
return target.value;
}
}
時間複雜度也是 O(n)。這是由於我們必須依次往下，直到找到倒數第二個節點，並將它 next 的引用指向 null。
向鍊表開頭添加與刪除一個元素
往鍊表開頭添加一個元素（的代碼）如下所示：
addFirst(value) {
const node = new Node(value);
node.next = this.first;
this.first = node;
}
向鍊表的開頭進行增刪操作，所耗費的時間是恆定的，因為我們持有根元素的引用：
removeFirst(value) {
const target = this.first;
this.first = target ? target.next : null;
return target.value;
}
（譯者註：作者原文 removeFirst 的代碼放錯了，上述代碼是譯者實現的）
如你所見，對鍊表的開頭進行增刪操作，時間複雜度永遠是 O(1)。
從鍊表的任意位置刪除元素
刪除鍊表首尾的元素，可以使用 removeFirst 或 removeLast。然而，如若移除的節點在鍊表的中間，則需要將待刪除節點的前一個節點指向待刪除節點的下一個節點，從而從鍊表中刪除該節點：
remove(index = 0) {
if(index === 0) {
return this.removeFirst();
}
let current;
let target = this.first;
for (let i = 0; target; i++, current = target, target = target.next) {
if(i === index) {
if(!target.next) {
return this.removeLast();
}
current.next = target.next;
this.size--;
return target.value;
}
}
}
（譯者註：原文實現有點問題，譯者稍作了點修改。removeLast 的調用其實浪費了性能，但可讀性上增加了，因而此處未作修改。）
注意， index 是從0開始的：0是第一個節點，1是第二個，如此類推。
在鍊表任意一處刪除節點，時間複雜度為 O(n).
在鍊表中查找元素
在鍊表中查找一個元素與刪除元素的代碼差不多：
contains(value) {
for (let current = this.first, index = 0; current; index++, current = current.next) {
if(current.value === value) {
return index;
}
}
}
這個方法查找鍊表中第一個與給定值相等的節點（的索引）。
在鍊表中查找一個元素，時間複雜度是 O(n)
單向鍊表操作方法的時間複雜度在下表中，小結了單向鍊表（方法）的時間複雜度：
操作方法時間複雜度注釋addFirstO(1)將元素插入到鍊表的開頭addLastO(n)將元素插入到鍊表的末尾addO(n)將元素插入到鍊表的任意地方removeFirstO(1)刪除鍊表的首個元素removeLastO(n)刪除鍊表最後一個元素removeO(n)刪除鍊表中任意一個元素containsO(n)在鍊表中查找任意元素注意，當我們增刪鍊表的最後一個元素時，該操作的時間複雜度是 O(n)…
但只要持有最後一個節點的引用，可以從原來的 O(n)，降至與增刪首個元素一致，變為 O(1)！
我們將在下一節實現這功能！
Doubly Linked Lists當我們有一串節點，每一個都有指向下一個節點的引用，也就是擁有了一個單向鍊表。而當一串節點，每一個既有指向下一個節點的引用，也有指向上一個節點的引用時，這串節點就是雙向鍊表。
雙向鍊表的節點有兩個引用（分別指向前一個和後一個節點），因此需要保持追蹤首個與最後一個節點。
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}
class LinkedList {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
}
（雙向鍊表的完整代碼）
添加或刪除鍊表的首個元素
由於持有首個節點的引用，因而添加或刪除首個元素的操作是十分簡單的：
addFirst(value) {
const node = new Node(value);
node.next = this.first;
if(this.first) {
this.first.previous = node;
} else {
this.last = node;
}
this.first = node;
this.size++;
return node;
}
（LinkedList.prototype.addFirst 的完整代碼
注意，我們需要十分謹慎地更新節點的 previous 引用、雙向鍊表的 size 與雙向鍊表最後一個節點的引用。
removeFirst() {
const first = this.first;
if(first) {
this.first = first.next;
if(this.first) {
this.first.previous = null;
}
this.size--;
return first.value;
} else {
this.last = null;
}
}
（LinkedList.prototype.removeFirst 的完整代碼
時間複雜度是什麼呢？
無論是單向鍊表還是雙向鍊表，添加與刪除首個節點的操作耗費時間都是恆定的，時間複雜度為 O(1)。
添加或刪除鍊表的最後一個元素
從雙向鍊表的末尾添加或刪除一個元素稍有點麻煩。當你查詢單向鍊表（操作的時間複雜度）時，這兩個操作都是 O(n)，這是由於需要遍歷整條鍊表，直至找到最後一個元素。然而，雙向鍊表持有最後一個節點的引用：
addLast(value) {
const node = new Node(value);
if(this.first) {
node.previous = this.last;
this.last.next = node;
this.last = node;
} else {
this.first = node;
this.last = node;
}
this.size++;
return node;
}
（LinkedList.prototype.addLast 的完整代碼）
同樣，我們需要小心地更新引用與處理一些特殊情況，如鍊表中只有一個元素時。
removeLast() {
let current = this.first;
let target;
if(current && current.next) {
target = this.last;
current = target.previous;
this.last = current;
current.next = null;
} else {
this.first = null;
this.last = null;
target = current;
}
if(target) {
this.size--;
return target.value;
}
}
（LinkedList.prototype.removeLast 的完整代碼）
使用了雙向鍊表，我們不再需要遍歷整個鍊表直至找到倒數第二個元素。可以直接使用 this.last.previous 來找到它，時間複雜度是 O(1)。
下文將介紹隊列相關的知識，本文中隊列是使用兩個數組實現的。可以改為使用雙向鍊表實現隊列，因為（雙向鍊表）添加首個元素與刪除最後一個元素時間複雜度都是 O(1)。
添加一個元素至鍊表任意一處
藉助 addFirst 與 addLast，可以實現將一個元素添加到鍊表任意一處，實現如下：
add(value, index = 0) {
if(index === 0) {
return this.addFirst(value);
}
for (let current = this.first, i = 0; i <= this.size; i++, current = (current && current.next)) {
if(i === index) {
if(i === this.size) {
return this.addLast(value);
}
const newNode = new Node(value);
newNode.previous = current.previous;
newNode.next = current;
current.previous.next = newNode;
if(current.next) { current.next.previous = newNode; }
this.size++;
return newNode;
}
}
}
（LinkedList.prototype.add 的完整代碼）
如果添加元素的位置是在鍊表中間，我們就必須更新該元素前後節點的 next 與 previous 引用。
添加一個元素至鍊表任意一處的時間複雜度是 O(n).
雙向鍊表方法的時間複雜度雙向鍊表每個方法的時間複雜度如下表：
操作方法時間複雜度注釋addFirstO(1)將元素插入到鍊表的開頭addLastO(1)將元素插入到鍊表的末尾addO(n)將元素插入到鍊表的任意地方removeFirstO(1)刪除鍊表的首個元素removeLastO(1)刪除鍊表最後一個元素removeO(n)刪除鍊表中任意一個元素containsO(n)在鍊表中查找任意元素與單向鍊表相比，有了很大的改進（譯者註：其實看場景，不要盲目認為雙向鍊表一定比單向鍊表強）！（addLast 與 removeLast）操作時間複雜度從 O(n) 降至 O(1) ，這是由於：
添加對前一個節點的引用。
持有鍊表最後一個節點的引用。
刪除首個或最後一個節點可以在恆定時間內完成，然而刪除中間的節點時間複雜度仍然是 O(n)。
Stacks棧是一種越後被添加的元素，越先被彈出的數據結構。也就是後進先出（LIFO）.
讓我們從零開始實現一個棧！
class Stack {
constructor() {
this.input = [];
}
push(element) {
this.input.push(element);
return this;
}
pop() {
return this.input.pop();
}
}
正如你看到的，如果使用內置的 Array.push 與 Array.pop 實現一個棧，那是十分簡單的。兩個方法的時間複雜度都是 O(1)。
下面來看看棧的具體使用：
const stack = new Stack();
stack.push('a');
stack.push('b');
stack.push('c');
stack.pop();
stack.pop();
stack.pop();
最先被加入進去的元素 a 直到最後才被彈出。棧也可以通過鍊表來實現，對應方法的時間複雜度是一樣的。
這就是棧的全部內容啦！
Queues隊列是一種越先被添加的元素，越先被出列的數據結構。也就是先進先出（FIFO）。就如現實中排成一條隊的人們一樣，先排隊的先被服務（也就是出列）。
可以通過數組來實現一個隊列，代碼與棧的實現相類似。
通過數組實現隊列通過 Array.push 與 Array.shift 可以實現一個簡單（譯者註：即不是最優的實現方式）的隊列：
class Queue {
constructor() {
this.input = [];
}
add(element) {
this.input.push(element);
}
remove() {
return this.input.shift();
}
}
Queue.add 與 Queue.remove 的時間複雜度是什麼呢？
試想一下，如果只用 Array.push 與 Array.pop 能實現一個隊列嗎？
class Queue {
constructor() {
this.input = [];
this.output = [];
}
add(element) {
this.input.push(element);
}
remove() {
if(!this.output.length) {
while(this.input.length) {
this.output.push(this.input.pop());
}
}
return this.output.pop();
}
}
現在，我們使用兩個而不是一個數組來實現一個隊列。
const queue = new Queue();
queue.add('a');
queue.add('b');
queue.remove()
queue.add('c');
queue.remove()
queue.remove()
當我們第一次執行出列操作時，output 數組是空的，因此將 input 數組的內容反向添加到 output 中，此時 output 的值是 ['b', 'a']。然後再從 output 中彈出元素。正如你所看到的，通過這個技巧實現的隊列，元素輸出的順序也是先進先出（FIFO）的。
那時間複雜度是什麼呢？
如果 output 數組已經有元素了，那麼出列操作就是恆定的 O(1)。而當 output 需要被填充（即裡面沒有元素）時，時間複雜度變為 O(n)。output 被填充後，出列操作耗時再次變為恆定。因此分攤後是 O(1)。
也可以通過鍊表來實現隊列，相關操作耗時也是恆定的。下一節將帶來具體的實現。
通過雙向鍊表實現隊列如果希望隊列有最好的性能，就需要通過雙向鍊表而不是數組來實現（譯者註：並非數組實現就完全不好，空間上雙向鍊表就不佔優勢，還是具體問題具體分析）。
const LinkedList = require('../linked-lists/linked-list');
class Queue {
constructor() {
this.input = new LinkedList();
}
add(element) {
this.input.addFirst(element);
}
remove() {
return this.input.removeLast();
}
get size() {
return this.input.size;
}
}
通過雙向鍊表實現的隊列，我們持有（雙向鍊表中）首個與最後一個節點的引用，因此入列與出列的時間複雜度都是 O(1)。這就是為遇到的問題選擇合適數據結構的重要性 💪。
總結我們討論了大部分線性的數據結構。可以看出，根據實現方法的不同，相同的數據結構也會有不同的時間複雜度。
以下是本文討論內容的總結：
時間複雜度
* = 運行時分攤
數據結構插入訪問查找刪除備註ArrayO(n)O(1)O(n)O(n)插入最後位置複雜度為O(1)。(Hash)MapO(1)*O(1)*O(1)*O(1)*重新計算哈希會影響插入時間。MapO(log(n))-O(log(n))O(log(n))通過二叉搜索樹實現Set（使用 HashMap）O(1）*-O(1)*O(1)*由 HashMap 實現Set (使用 List)O(n)-O(n)]O(n)通過 List 實現Set (使用二叉搜索樹)O(log(n))-O(log(n))O(log(n))通過二叉搜索樹實現Linked List (單向)O(n)-O(n)O(n)在起始位置添加或刪除元素，複雜度為O(1)Linked List (雙向）O(n)-O(n)O(n)在起始或結尾添加或刪除元素，複雜度為O(1)。然而在其他位置是O(n)。Stack (由 Array 實現)O(1)--O(1)]插入與刪除都遵循與後進先出（LIFO）Queue (簡單地由 Array 實現)O(n)--O(1)插入（Array.shift）操作的複雜度是 O(n)Queue (由 Array 實現，但進行了改進)O(1)*--O(1)插入操作的最差情況複雜度是 O(n)。然而分攤後是 O(1)Queue (由 List 實現)O(1)--O(1)使用雙向鍊表注意： 二叉搜索樹 與其他樹結構、圖結構，將在另一篇文章中討論。
關於奇舞周刊《奇舞周刊》是360公司專業前端團隊「奇舞團」運營的前端技術社區。關注公眾號後，直接發送連結到後臺即可給我們投稿。
360區塊鏈平臺部是公司整體區塊鏈的服務部門，涵蓋了區塊鏈底層技術研究，應用探索落地，標準技術輸出等區塊鏈的各大領域方向，為公司全方位業務打造區塊鏈場景提供支撐。
360區塊鏈官方公眾號，聚合區塊鏈安全、核心技術、架構、業界生態的趨勢和發展，參與業界貢獻，歡迎大家一起參與！