程序员必须了解的数据结构:Array、HashMap 与 List

来自:众成翻译,译者 sea_ljf,《奇舞周刊》排版编辑 链接:https://www.zcfy.cc/article/data-structures-for-beginners-arrays-hashmaps-and-lists

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List、Tree、Graph 等等。(然而)为程序选取合适的数据结构可能并不容易。因此,希望这篇文章能帮助你了解(不同数据结构的)表现,以求在工作中合理地使用它们。

本文主要聚焦于线性的数据结构,如:Array、Set、List、Sets、Stacks、Queues 等等。原始数据类型

原始数据类型是构成数据结构最基础的元素。下面列举出一些原始原始数据类型:

  • 整数,如:1, 2, 3, …
  • 字符,如:a, b, "1", "*"
  • 布尔值, true 与 false.
  • 浮点数 ,如:3.14159, 1483e-2.

1. Array

数组可由零个或多个元素组成。由于数组易于使用且检索性能优越,它是最常用的数据结构之一。

你可以将数组想象成一个抽屉,可以将数据存到匣子中。

数组就像是将东西存到匣子中的抽屉

当你想查找某个元素时,你可以直接打开对应编号的匣子(时间复杂度为O(1))。然而,如果你忘记了匣子里存着什么,就必须逐个打开所有的匣子(时间复杂度为 O(n)),直到找到所需的东西。数组也是如此。

根据编程语言的不同,数组存在一些差异。对于 JavaScript 和 Ruby 等动态语言而言,数组可以包含不同的数据类型:数字,字符串,对象甚至函数。而在 Java 、 C 、C ++ 之类的强类型语言中,你必须在使用数组之前,定好它的长度与数据类型。JavaScript 会在需要时自动增加数组的长度

1.1 Array 的内置方法

根据编程序言的不同,数组(方法)的实现稍有不同。比如在 JavaScript 中,我们可以使用 unshift 与 push 添加元素到数组的头或尾,同时也可以使用 shift 与 pop 删除数组的首个或最后一个元素。让我们来定义一些本文用到的数组常用方法。

常用的 JS 数组内置函数

1.2 向数组插入元素

将元素插入到数组有很多方式。你可以将新数据添加到数组末尾,也可以添加到数组开头。

先看看如何添加到末尾:

function insertToTail(array, element) {  array.push(element);  return array;}
const array = [1, 2, 3];console.log(insertToTail(array, 4)); // => [ 1, 2, 3, 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));// => [ 0, 1, 2, 3, ]

你觉得添加元素到数组开头的函数,时间复杂度是什么呢?看起来和上面(push)差不多,除了调用的方法是 unshift 而不是 push。但这有个问题,unshift 是通过将数组的每一项移到下一项,腾出首项的空间来容纳新添加的元素。所以它是遍历了一次数组的。

Array.unshift 的时间复杂度度是 O(n)1.3 访问数组中的元素 如果你知道待查找元素在数组中的索引,那你可以通过以下方法直接访问该元素:

function access(array, index) {  return array[index];}
const array = [1, 'word', 3.14, { a: 1 }];access(array, 0);// => 1access(array, 3);// => {a: 1}

正如上面你所看到的的代码一样,访问数组中的元素耗时是恒定的:

访问数组中元素的时间复杂度是 O(1)

注意:通过索引修改数组的值所花费的时间也是恒定的。

1.4 在数组中查找元素

如果你想查找某个元素但不知道对应的索引时,那只能通过遍历数组的每个元素,直到找到为止。

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'));// => 1console.log(search(array, 3.14));// => 2

鉴于使用了 for 循环,那么:

在数组中查找元素的时间复杂度是 O(n)

1.5 在数组中删除元素

你觉得从数组中删除元素的时间复杂度是什么呢?

先一起思考下这两种情况:

  1. 从数组的末尾删除元素所需时间是恒定的,也就是 O(1)
  2. 然而,无论是从数组的开头或是中间位置删除元素,你都需要调整(删除元素后面的)元素位置。因此复杂度为 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));// => [ 0, 2, 3 ]

我们使用了上面定义的 search 函数来查找元素的的索引,复杂度为 O(n)。然后使用JS 内置的 splice 方法,它的复杂度也是 O(n)。那(删除函数)总的时间复杂度不是 O(2n) 吗?记住,(对于时间复杂度而言,)我们并不关心常量。

对于上面列举的两种情况,考虑最坏的情况:

在数组中删除某项元素的时间复杂度是 O(n)

1.6 数组方法的时间复杂度

在下表中,小结了数组(方法)的时间复杂度:

数组方法的时间复杂度


2. HashMaps

HashMap有很多名字,如 HashTable、HashMap、Map、Dictionary、Associative Array 等。概念上它们都是一致的,实现上稍有不同。

哈希表是一种将键 映射到 值的数据结构。

回想一下关于抽屉的比喻,现在匣子有了标签,不再是按数字顺序了。

HashMap 也和抽屉一样存储东西,通过不同标识来区分不同匣子。

此例中,如果你要找一个玩具,你不需要依次打开第一个、第二个和第三个匣子来查看玩具是否在内。直接代开被标识为“玩具”的匣子即可。这是一个巨大的进步,查找元素的时间复杂度从 O(n) 降为 O(1) 了。

数字是数组的索引,而标识则作为 HashMap 存储数据的键。HashMap 内部通过 哈希函数 将键(也就是标识)转化为索引。

至少有两种方式可以实现 hashmap:

  1. 数组:通过哈希函数将键映射为数组的索引。(查找)最差情况: O(n),平均: O(1)。
  2. 二叉搜索树: 使用自平衡二叉搜索树查找值(另外的文章会详细介绍)。 (查找)最差情况: O(log n),平均:O(log n)

我们会介绍树与二叉搜索树,现在先不用担心太多。实现 Map 最常用的方式是使用 数组与哈希转换函数。让我们(通过数组)来实现它吧

通过数组实现 HashMap

正如上图所示,每个键都被转换为一个 hash code。由于数组的大小是有限的(如此例中是10),(如发生冲突,)我们必须使用模函数找到对应的桶(译者注:桶指的是数组的项),再循环遍历该桶(来寻找待查询的值)。每个桶内,我们存储的是一组组的键值对,如果桶内存储了多个键值对,将采用集合来存储它们。

我们将讲述 HashMap 的组成,让我们先从哈希函数开始吧。

2.1 哈希函数

实现 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 吧。

// Usage: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); // this one is okassert.equal(hashMap.get('cat'), 8); // got overwritten by art ?assert.equal(hashMap.get('rat'), 8); // got overwritten by art ?assert.equal(hashMap.get('dog'), 8); // got overwritten by art ?

这个 HashMap 允许我们通过 set 方法设置一组键值对,通过往 get 方法传入一个键来获取对应的值。其中的关键是哈希函数,当我们存入多组键值时,看看这 HashMap 的表现。

你能说出这个简单实现的 HashMap 存在的问题吗?

1) Hash function 转换出太多相同的索引。如:

hash('cat') // 3hash('dog') // 3

这会产生非常多的冲突。

2) 完全不处理冲突的情况。cat 与 dog 会重写彼此在 HashMap 中的值(它们均在桶 #1 中)。

3 数组长度。 即使我们有一个更好的哈希函数,由于数组的长度是2,少于存入元素的数量,还是会产生很多冲突。我们希望 HashMap 的初始容量大于我们存入数据的数量。

2.2 改进哈希函数

HashMap 的主要目标是将数组查找与访问的时间复杂度,从 O(n) 降至 O(1)

为此,我们需要:

  1. 一个合适的哈希函数,尽可能地减少冲突。
  2. 一个长度足够大的数组用于保存数据。

让我们重新设计哈希函数,不再采用字符串的长度为 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') // 312 (c=99 + a=97 + t=116)hash('dog') // 314 (d=100 + o=111 + g=103)

这函数比之前的要好!这是因为相同长度的单词由不一样的字母组成,因而 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;}

现在继续试验,下面列举出了十六进制的数字,这样可以方便我们观察位移。

// r = 114 or 0x72; a = 97 or 0x61; t = 116 or 0x74
hash('rat'); // 7,627,122 (r: 114 * 1 + a: 97 * 256 + t: 116 * 65,536) or in hex: 0x726174 (r: 0x72 + a: 0x6100 + t: 0x740000)
hash('art'); // 7,631,457 or 0x617274

然而,以下两种类型有何不同呢?

hash(1); // 49hash('1'); // 49hash('1,2,3'); // 741485668hash([1,2,3]); // 741485668hash('undefined') // 3402815551hash(undefined) // 3402815551

天啊,仍然有问题!!不同的数据类型不应该返回相同的 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)); // 1843909523console.log(hash('1')); // 1927012762console.log(hash('1,2,3')); // 2668498381console.log(hash([1,2,3])); // 2533949129console.log(hash('undefined')); // 5329828264console.log(hash(undefined)); // 6940203017

Yay!!! ? 我们终于有了更好的哈希函数!

同时,我们可以改变 HashMap 的原始容量以减少冲突,让我们在下一节中优化 HashMap。

更完善的 HashMap 实现

通过优化好的哈希函数,HashMap 可以表现得更好。

尽管冲突仍可能发生,但通过一些方式可以很好地处理它们。

对于我们的 HashMap,希望有以下改进:

  • 哈希函数, 检查类型与计算各字符(ascii 码的总和)以减少冲突的发生。
  • 处理冲突,通过将值添加到集合中来解决这问题,同时需要一个计数器追踪冲突的数量。

更完善 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 表现如何:

// Usage: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); // 2console.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); // this one is okassert.equal(hashMap.get('cat'), 2); // Good. Didn't got overwritten by artassert.equal(hashMap.get('rat'), 7); // Good. Didn't got overwritten by artassert.equal(hashMap.get('dog'), 1); // Good. Didn't got overwritten by art

完善后的 HashMap 很好地完成了工作,但仍然有一些问题。使用改良后的哈希函数不容易产生重复的值,这非常好。然而,在桶#0与桶#1中都有两个值。这是为什么呢??

由于 HashMap 的容量是2,尽管算出来的 hash code 是不一样的,当求余后算出所需放进桶的编号时,结果不是桶#0就是桶#1。

hash('cat') => 3789411390; bucketIndex => 3789411390 % 2 = 0hash('art') => 3789415740; bucketIndex => 3789415740 % 2 = 0hash('dog') => 3788563007; bucketIndex => 3788563007 % 2 = 1hash('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); // 1console.log('hashMapSize10 ', 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); // 0console.log('hashMapSize100 ', 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) {      // initialize array and save key/value      const keyIndex = this.keys.push({content: key}) - 1; // keep track of the key index      this.buckets[bucketIndex] = this.buckets[bucketIndex] || [];      this.buckets[bucketIndex].push({key, value, keyIndex});      this.size++;      // Optional: keep count of collisions      if(this.buckets[bucketIndex].length > 1) { this.collisions++; }    } else {      // override existing value      this.buckets[bucketIndex][entryIndex].value = value;    }    // check if a rehash is due    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));      }    });    // update bucket    this.buckets = newMap.buckets;    this.collisions = newMap.collisions;    // Optional: both `keys` has the same content except that the new one doesn't have empty spaces from deletions    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'); // <--- Trigger REHASHassert.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 的性能取决于:

  1. 哈希函数能根据不同的键输出不同的值。
  2. HashMap 容量的大小。

我们终于处理好了各种问题 ?。有了不错的哈希函数,可以根据不同输入返回不同输出。同时,我们也有 rehash 函数根据需要动态地调整 HashMap的容量。这实在太好了!

HashMap 中插入元素的时间复杂度

往一个 HashMap 插入元素需要两样东西:一个键与一个值。可以使用上文开发优化后的 HashMap 或内置的对象进行操作:

function insert(object, key, value) {  object[key] = value;  return object;}const hash = {};console.log(insert(hash, 'word', 1)); // => { 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 { '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(方法)的时间复杂度:

2.3 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 Set(); // Using the built-inconst set = new MySet(); // Using our own implementationset.add('one');set.add('uno');set.add('one'); // should NOT add this one twiceassert.equal(set.has('one'), true);assert.equal(set.has('dos'), false);assert.equal(set.size, 2);// assert.deepEqual(Array.from(set), ['one', 'uno']);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 非常相似):


3. Linked Lists

链表是一种一个节点链接到下一个节点的数据结构。

链表是(本文)第一种不用数组(作为底层)实现的数据结构。我们使用节点来实现,节点存储了一个元素,并指向下一个节点(若没有下一个节点,则为空)。

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}

当每个节点都指向它的下了一个节点时,我们就拥有了一条由若干节点组成链条,即单向链表

3.1 Singly Linked Lists

对于单向链表而言,我们只需关心每个节点都有指向下一个节点的引用。

从首个节点或称之为根节点开始构建(单向链表)。

class LinkedList {  constructor() {    this.root = null;  }  // ...}

每个链表都有四个基础操作:

  1. addLast:将一个元素添加至链表尾部。
  2. removeLast:删除链表的最后一个元素。
  3. addFirst:将一个元素添加到链表的首部。
  4. removeFirst:删除链表的首个元素。

向链表末尾添加与删除一个元素

(对添加操作而言,)有两种情况。1)如果链表根节点不存在,那么将新节点设置为链表的根节点。2)若存在根节点,则必须不断查询下一个节点,直到链表的末尾,并将新节点添加到最后。

addLast(value) { // similar Array.push  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) { // if it doesn't have next it means that it is the last        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)

单向链表操作方法的时间复杂度

在下表中,小结了单向链表(方法)的时间复杂度:

注意,当我们增删链表的最后一个元素时,该操作的时间复杂度是 O(n)…

但只要持有最后一个节点的引用,可以从原来的 O(n),降至与增删首个元素一致,变为 O(1)

3.2 Doubly Linked Lists

当我们有一串节点,每一个都有指向下一个节点的引用,也就是拥有了一个单向链表。而当一串节点,每一个既有指向下一个节点的引用,也有指向上一个节点的引用时,这串节点就是双向链表

双向链表的节点有两个引用(分别指向前一个和后一个节点),因此需要保持追踪首个与最后一个节点。

class Node {  constructor(value) {    this.value = value;    this.next = null;    this.previous = null;  }}class LinkedList {  constructor() {    this.first = null; // head/root element    this.last = null; // last element of the list    this.size = 0; // total number of elements in the list  }  // ...}

(双向链表的完整代码)

添加或删除链表的首个元素

由于持有首个节点的引用,因而添加或删除首个元素的操作是十分简单的:

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; // update head  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) { // if it doesn't have next it means that it is the last        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). 双向链表方法的时间复杂度 双向链表每个方法的时间复杂度如下表:

与单向链表相比,有了很大的改进(译者注:其实看场景,不要盲目认为双向链表一定比单向链表强)!(addLast 与 removeLast)操作时间复杂度从O(n) 降至 O(1) ,这是由于:

  • 添加对前一个节点的引用。
  • 持有链表最后一个节点的引用。

删除首个或最后一个节点可以在恒定时间内完成,然而删除中间的节点时间复杂度仍然是 O(n)


4. 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(); // cstack.pop(); // bstack.pop(); // a

最先被加入进去的元素 a 直到最后才被弹出。栈也可以通过链表来实现,对应方法的时间复杂度是一样的。

这就是栈的全部内容啦!


5. Queues

队列是一种越先被添加的元素,越先被出列的数据结构。也就是先进先出(FIFO)。就如现实中排成一条队的人们一样,先排队的先被服务(也就是出列)。

可以通过数组来实现一个队列,代码与栈的实现相类似。

5.1 通过数组实现队列

通过 Array.push 与 Array.shift 可以实现一个简单(译者注:即不是最优的实现方式)的队列:

class Queue {  constructor() {    this.input = [];  }  add(element) {    this.input.push(element);  }  remove() {    return this.input.shift();  }}

Queue.add 与 Queue.remove 的时间复杂度是什么呢?

  • Queue.add 使用 Array.push 实现,可以在恒定时间内完成。这非常不错!
  • Queue.remove 使用 Array.shift 实现,Array.shift 耗时是线性的(即 O(n))。我们可以减少 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() // aqueue.add('c');queue.remove() // bqueue.remove() // c

当我们第一次执行出列操作时,output 数组是空的,因此将 input 数组的内容反向添加到 output 中,此时 output 的值是 ['b', 'a']。然后再从 output 中弹出元素。正如你所看到的,通过这个技巧实现的队列,元素输出的顺序也是先进先出(FIFO)的。

那时间复杂度是什么呢?

如果 output 数组已经有元素了,那么出列操作就是恒定的 O(1)。而当 output 需要被填充(即里面没有元素)时,时间复杂度变为 O(n)。output 被填充后,出列操作耗时再次变为恒定。因此分摊后是 O(1)

也可以通过链表来实现队列,相关操作耗时也是恒定的。下一节将带来具体的实现。

5.2 通过双向链表实现队列

如果希望队列有最好的性能,就需要通过双向链表而不是数组来实现(译者注:并非数组实现就完全不好,空间上双向链表就不占优势,还是具体问题具体分析)。

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)。这就是为遇到的问题选择合适数据结构的重要性 ?。


6. 总结

我们讨论了大部分线性的数据结构。可以看出,根据实现方法的不同,相同的数据结构也会有不同的时间复杂度。

以下是本文讨论内容的总结:

时间复杂度

* = 运行时分摊


声明:本文系网络转载,版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2018-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

4247
来自专栏mathor

ST算法

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i...

2152
来自专栏GIS讲堂

面向对象的三个基本特征

封装,也就是把客观事物封装成抽象的类,并且类可以把自己的数据和方法只让可信的类或者对象操作,对不可信的进行信息隐藏。

1913
来自专栏程序员宝库

如何用JavaScript手动实现一个栈

在生活中也能发现很多栈的例子。例如,厨房里堆放的盘子,总是叠在上方的先被使用;输入框内容进行删除时,总是最后输入的先删除;弹夹中的子弹,越后装入的,越先发射.....

1194
来自专栏有趣的Python

1-Java面向对象-面向对象

通过前面的学习我们对于java的语法结构有了一定的认识,掌握了分支结构,循环结构等常用的程序逻辑,也能运用这些知识解决一些简单问题。

2881
来自专栏web编程技术分享

【干货】用大白话聊聊JavaSE — ArrayList 深入剖析和Java基础知识详解(二)1. 新建一个MyList类2. 构造函数设计3. add方法实现4. remove方法实现

3206
来自专栏老马说编程

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。...

2519
来自专栏chenjx85的技术专栏

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

1843
来自专栏前端儿

表达式求值(1)

Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值...

1862
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4425

扫码关注云+社区

领取腾讯云代金券