Оригинальная ссылка:Data Structures for Beginners: Arrays, HashMaps, and Lists

Адрес перевода Чжунчэн:Структуры данных, которые должны знать новички: массив, HashMap и список

Вычитка:Volong

Это длинная статья. Студентам, не знакомым со структурами данных, рекомендуется читать эту статью медленно. Надеюсь, она будет вам полезна. Ниже приводится текст перевода:

Data Structures for Beginners: Arrays, HashMaps, and Lists

При разработке программ нам (обычно) необходимо хранить данные в памяти. В зависимости от того, как обрабатываются данные, могут быть выбраны различные структуры данных. Существует много часто используемых структур данных, таких как: массив, карта, набор, список, дерево, график и т. д. (Однако) выбор правильной структуры данных для программы может быть непростым. Так что, надеюсь, эта статья поможет вам понять поведение (различных структур данных), чтобы разумно использовать их в своей работе.

Эта статья в основном посвящена линейным структурам данных, таким как: массив, набор, список, наборы, стеки, очереди и т. д.

Эта статья является частью следующих руководств:

Структуры данных и алгоритмы (DSA), которые должны знать новички

Временная сложность алгоритмов и нотация Big O
Восемь сложностей со временем, которые должен знать каждый программист
Структуры данных, которые должны знать новички: массив, HashMap и список👈 Это эта статья
Структуры данных, которые должны знать новички: граф (перевод)
Структуры данных, которые должны знать новички: дерево (Следите за обновлениями)
Приложение I: Анализ рекурсивных алгоритмов

Временная сложность (операционных) структур данных

В таблице ниже представлено краткое изложение того, что обсуждается в этой статье.

Добавьте эту статью в закладки, добавьте в избранное или поделитесь ею, когда она вам понадобится.

* = амортизация во время работы

структура данных	вставлять	доступ	найти	удалять	Примечание
Array	O(n)	O(1)	O(n)	O(n)	Сложность вставки последней позицииO(1).
(Hash)Map	O(1)*	O(1)*	O(1)*	O(1)*	Пересчет хэша влияет на время вставки.
Map	O(log(n))	-	O(log(n))	O(log(n))	Реализовано бинарным деревом поиска
Set(используя HashMap)	О(1)*	-	O(1)*	O(1)*	Реализовано HashMap
Set(используя список)	O(n)	-	O(n)]	O(n)	Реализован Список
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(реализовано массивом)	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(реализовано списком)	O(1)	-	-	O(1)	Использовать двусвязный список

Уведомление:бинарное дерево поискаС другими древовидными структурами, структурами графов, мы поговорим в другой статье.

примитивный тип данных

Примитивные типы данных являются наиболее фундаментальными элементами структуры данных. Некоторые примитивные примитивные типы данных перечислены ниже:

Целое число, например: 1, 2, 3, …
Такие символы, как: а, б, "1", "*"
логические, истинные и ложные.
Числа с плавающей запятой, такие как: 3.14159, 1483e-2.

Array

Массивы могут состоять из нуля или более элементов. Массивы являются одной из наиболее часто используемых структур данных из-за их простоты использования и превосходной производительности поиска.

Вы можете думать о массиве как о ящике, и вы можете хранить данные в ящике.

Массивы похожи на ящики для хранения вещей в коробках.

Array is like a drawer that stores things on bins

Когда вы хотите найти элемент, вы можете напрямую открыть соответствующее пронумерованное поле (время сложности равноO(1)). Однако, если вы забудете, что в коробке, вам придется открыть все коробки одну за другой (сложность по времениO(n)), пока не найдете то, что вам нужно. То же самое касается массивов.

Массивы имеют некоторые отличия в зависимости от языка программирования. Для динамических языков, таких как JavaScript и Ruby, массивы могут содержать разные типы данных: числа, строки, объекты и даже функции. В строго типизированных языках, таких как Java, C, C++, вы должны определить длину и тип данных массива перед его использованием. JavaScript автоматически увеличивает длину массива, когда это необходимо.

Встроенные методы массива

Массивы (методы) реализованы немного по-разному в зависимости от языка программирования.

Например, в JavaScript мы можем использоватьunshiftа такжеpushДобавьте элементы в начало или конец массива, и вы также можете использоватьshiftа такжеpopУдалить первый или последний элемент массива. Давайте определим некоторые общие методы массивов, используемые в этой статье.

Часто используемые встроенные функции массива JS

функция	сложность	описывать
array.push(элемент1[ …[ элементN]])	O(1)	Добавить один или несколько элементов в конец массива
array.pop()	O(1)	удалить элемент с конца массива
array.shift()	O(n)	удалить элемент в начале массива
array.unshift(элемент1[ …[ элементN]])	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)); // => [ 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, ]

Ты чувствуешьinsertToHeadКакова временная сложность функции? выглядит и выше(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);// => 1
access(array, 3);// => {a: 1}

Как видно из приведенного выше кода, доступ к элементам массива занимает постоянное время:

Временная сложность доступа к элементу массива равна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'));// => 1
console.log(search(array, 3.14));// => 2

Учитывая использование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));// => [ 0, 2, 3 ]

Мы использовали определенные выше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)

HashMaps

HashMap имеет множество названий, таких как HashTableHashMap, Map, Dictionary, Associative Array и т. д. Концептуально они все одинаковые, с немного разными реализациями.

Хэш-таблица — это ключсопоставить сСтруктура данных значения.

Вспомните аналогию с ящиком: теперь, когда у ящиков есть этикетки, они больше не упорядочены по номерам.

HashMap также хранит такие вещи, как ящики, различая разные ящики по разным идентификаторам.

HashMap is like a drawer that stores things on bins and label them

В этом примере, если вы ищете игрушку, вам не нужно открывать первую, вторую и третью коробки, чтобы увидеть, находится ли внутри игрушка. Вы можете напрямую открыть коробку с пометкой «игрушка». Это огромное улучшение, временная сложность поиска элемента идет отO(n)сокращено доO(1).

Числа — это индексы в массиве, а идентификаторы действуют как ключи для хранения данных в HashMap. Внутренний проход HashMapхэш-функцияПреобразование ключей (они же идентификаторы) в индексы.

Есть как минимум два способа реализовать хэш-карту:

множество: сопоставление ключей с индексами в массиве с помощью хеш-функции. (найти) наихудший случай: O(n), средний: O(1).
бинарное дерево поиска: поиск значений с помощью самобалансирующегося бинарного дерева поиска (подробнее об этом в другой статье). (найти) худший случай:O(log n),средний:O(log n).

Мы познакомим вас с деревьями и деревьями бинарного поиска, но пока не беспокойтесь слишком сильно. Самый распространенный способ реализации карты — это использованиемножествос функцией преобразования хэша. Давайте сделаем это (через массив)

Реализовать HashMap через массивы

HashMap: hash function translates keys into bucket (array) indexes

Как показано на изображении выше, каждый ключ преобразуется в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;
  }
}

полный код

мы используем напрямуюbucketsВместо ящиков и ящиков, я думаю, вы можете понять смысл метафор :)

Начальная емкость 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 ok
assert.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') // 3
hash('dog') // 3

Это создает много конфликтов.

2)Не занимайтесь этим вообщеконфликтСлучай.catа такжеdogбудут перезаписывать значения друг друга в HashMap (они оба находятся в корзине №1).

3 Длина массива. Даже если бы у нас была лучшая хеш-функция, поскольку длина массива равна 2, что меньше количества хранимых элементов, все равно будет много коллизий. Мы хотим, чтобы начальная емкость HashMap была больше, чем объем данных, которые мы храним.

Улучшить хэш-функцию

Основная цель HashMap — уменьшить временную сложность поиска и доступа к массиву изO(n)вплоть доO(1).

Для этого нам нужно:

Правильная хэш-функция, которая минимизирует максимально возможным столкновениями.
Массив достаточной длины для хранения данных.

Давайте изменим хеш-функцию, вместо использования длины строки в качестве хэш-кода, мы будем использовать хэш-код каждого символа в строке.ascii-кодСумма - это хэш-код.

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.

Однако есть еще проблемы! Слова «крыса» и «искусство» после преобразования равны 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); // 49
hash('1'); // 49
hash('1,2,3'); // 741485668
hash([1,2,3]); // 741485668
hash('undefined') // 3402815551
hash(undefined) // 3402815551

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

Ура!!! 🎉 Наконец-то у нас есть лучшая хеш-функция!

В то же время мы можем изменить исходную емкость 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); // 2
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); // this one is ok
assert.equal(hashMap.get('cat'), 2); // Good. Didn't got overwritten by art
assert.equal(hashMap.get('rat'), 7); // Good. Didn't got overwritten by art
assert.equal(hashMap.get('dog'), 1); // Good. Didn't got overwritten by art

Полированный HashMap прекрасно справляется со своей задачей, но все еще есть некоторые проблемы. Здорово, что дублирующиеся значения с меньшей вероятностью будут генерироваться с помощью модифицированной хеш-функции. Однако в корзине №0 и корзине №1 есть два значения. Почему это? ?

Поскольку емкость HashMap равна 2, несмотря на то, что рассчитанные хэш-коды отличаются, когда число, которое нужно поместить в корзину, вычисляется после остатка, результатом будет либо ведро № 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); // 1
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); // 0
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>
*/

Ура 🎊 Никаких конфликтов!

Увеличивая начальную мощность, конфликты можно очень хорошо уменьшить, но за счетБольше памяти, и скорее всего многие ведра не используются.

Не было бы лучше, если бы наш 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 (т.е.rehashfunction), где происходит волшебство перефразирования. Мы создаем новый 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 REHASH
assert.equal(hashMap.collisions, 0);
assert.equal(hashMap.getLoadFactor(), 0.40625);
assert.equal(hashMap.buckets.length, 32);

Обратите внимание, что при сохранении 12-го элемента в HashMap коэффициент загрузки превысит 0,75, что приведет к повторному хэшированию и удвоению емкости 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)); // => { word: 1 }

В новых версиях JavaScript вы можете использовать Карты.

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.setпросто вставьте элемент в массив (как указано вышеDecentHashMap.setпоказано), аналогичноArray.push, поэтому мы можем сказать:

Вставка элементов в hashmap, момент сложностиO(1). Если требуется перефразирование, то сложностьO(n).

перефразирование может свести к минимуму возможность конфликтов. Временная сложность операции перефразирования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). Однако с помощью операции повторного хеширования вероятность наихудшего случая может быть значительно снижена.

Средняя временная сложность модификации или удаления 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, вызывая перефразирование
удалять (`HashMap.delete`)	O(n)	O(1)	O(n)крайний случай конфликта

Sets

Коллекции очень похожи на массивы. Отличие между ними в том, что элементы в наборе уникальны.

Как реализовать коллекцию (т. е. массив без дубликатов)? Это можно реализовать с помощью массива, проверяя наличие нового элемента перед его вставкой. Но временная сложность проверки существованияO(n). Можно ли это оптимизировать? Временная сложность ранее разработанной Карты (операция вставки) амортизируетсяO(1)!

Реализация набора

Вы можете использовать встроенный в JavaScript метод Set. Однако, реализуя его самостоятельно, вы можете получить более интуитивное представление о его временной сложности. Мы будем использовать приведенный выше оптимизированный 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
    }, []);
  }
}

(Примечание переводчика: из-заhasВозникла проблема с методом, из-за чего набор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-in
const set = new MySet(); // Using our own implementation
set.add('one');
set.add('uno');
set.add('one'); // should NOT add this one twice
assert.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, временная сложность, которая может быть меньше, выглядит следующим образом (очень похожа на HashMap):

Временная сложность метода Set

Как работать	худший случай	средний	Примечание
посетите или найдите (`Set.has`)	O(n)	O(1)	O(n)крайний случай конфликта
Вставьте или измените (`Set.add`)	O(n)	O(1)	O(n)Происходит только тогда, когда коэффициент загрузки превышает 0,75, вызывая перефразирование
удалять (`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: добавляет элемент в начало связанного списка.
RiewFirst: Удаляет первый элемент связанного списка.

Добавить и удалить элемент из конца связанного списка

Есть два случая (для операций добавления). 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)

Временная сложность метода работы с односвязным списком

В следующей таблице представлена временная сложность односвязного списка (метода):

Как работать	временная сложность	Примечания
addFirst	O(1)	Вставить элемент в начало связанного списка
addLast	O(n)	вставить элемент в конец связанного списка
add	O(n)	Вставка элементов в любом месте связанного списка
removeFirst	O(1)	удалить первый элемент связанного списка
removeLast	O(n)	удалить последний элемент связанного списка
remove	O(n)	удалить любой элемент в связанном списке
contains	O(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; // 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).

Временная сложность метода двусвязного списка

Временная сложность каждого метода двусвязного списка следующая:

Как работать	временная сложность	Примечания
addFirst	O(1)	Вставить элемент в начало связанного списка
addLast	O(1)	вставить элемент в конец связанного списка
add	O(n)	Вставка элементов в любом месте связанного списка
removeFirst	O(1)	удалить первый элемент связанного списка
removeLast	O(1)	удалить последний элемент связанного списка
remove	O(n)	удалить любой элемент в связанном списке
contains	O(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(); // c
stack.pop(); // b
stack.pop(); // a

Элемент 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Какова временная сложность?

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() // a
queue.add('c');
queue.remove() // b
queue.remove() // c

Когда мы выполняем операцию удаления из очереди в первый раз,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). Вот в чем важность выбора правильной структуры данных для проблемы, с которой вы сталкиваетесь 💪.

Суммировать

Мы обсуждали в основном линейные структуры данных. Видно, что одна и та же структура данных будет иметь разную временную сложность в зависимости от метода реализации.

Ниже приводится краткое изложение того, что обсуждалось в этой статье:

временная сложность

* = амортизация во время работы

структура данных	вставлять	доступ	найти	удалять	Примечание
Array	O(n)	O(1)	O(n)	O(n)	Сложность вставки последней позицииO(1).
(Hash)Map	O(1)*	O(1)*	O(1)*	O(1)*	Пересчет хэша влияет на время вставки.
Map	O(log(n))	-	O(log(n))	O(log(n))	Реализовано бинарным деревом поиска
Set(используя HashMap)	О(1)*	-	O(1)*	O(1)*	Реализовано HashMap
Set(используя список)	O(n)	-	O(n)]	O(n)	Реализован Список
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(реализовано массивом)	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(реализовано списком)	O(1)	-	-	O(1)	Использовать двусвязный список