Структуры данных, которые должны знать веб-разработчики

концепция структуры данных

Структура данных относится к набору элементов данных, которые имеют одно или несколько отношений друг с другом и отношения между элементами данных в наборе.

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

Каждая структура данных имеет уникальный способ хранения данных.Разные типы структур данных подходят для разных типов приложений.Некоторые структуры данных даже предназначены для решения конкретных задач. Правильный выбор структуры данных может повысить эффективность алгоритма.

Ниже приводится их структура, преимущества и недостатки.

массив 🌈

определение

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

преимущество

Запрос элементов по индексу выполняется быстро
Легко перемещаться по массиву по индексу

недостаток

Как только размер массива фиксирован, его нельзя расширить.
Массивы могут хранить только один тип данных

расширять

Значение хранилища по умолчанию в массивах JavaScript не определено, а значение хранилища по умолчанию в массивах в других языках программирования равно 0 или мусорным данным.
В отличие от других языков программирования, JavaScript может обращаться к индексам, которых нет в массиве, и будет возвращать undefined, в то время как другие языки программирования будут сообщать об ошибках или возвращать мусорные данные.
JavaScript может хранить данные разных типов, в то время как другие языки программирования могут хранить данные только одного типа данных.
Когда места для хранения массива в JavaScript недостаточно, он будет автоматически расширяться, в то время как размер массива в других языках фиксирован, после определения его нельзя изменить.
Место для хранения, выделенное для массивов в JavaScript, не является непрерывным, в то время как место для хранения, выделенное для массивов в других языках программирования, является непрерывным.

Применимая сцена

Частые запросы, небольшие требования к месту для хранения и мало добавлений и удалений.

стек 🎯

определение

Стек, также известный как стек, представляет собой специальную линейную таблицу, с которой можно работать только на одном конце линейной таблицы.Верхняя часть стека может работать, а нижняя часть стека не может работать. Характеристики стека: «первым пришел», «последним вышел» или «последним пришел — первым ушел» (LIFO, Last In First Out), операция помещения элементов из вершины стека называется push, а извлечение элементы называется поп;

Применимая сцена

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

выполнить

Здесь стек используется для реализации функции отмены.

Пример:

module.exports =  class Stack {
  data = []
  maxSize

  constructor(initialData, maxSize = -1) {
      this.data = Array.isArray(initialData) ? initialData : (typeof initialData == "undefined" ? [] : [initialData])
      this.maxSize = maxSize
  }
  
  isFull() {
      return this.maxSize != -1 ? (this.data.length == this.maxSize) : false
  }
  
  isEmpty() {
      return this.data.length == 0
  }
  
  add(item) {
      if(this.isFull()) {
          return false
      }
      this.data.push(item)
  }
  
  *generator() {
      while(!this.isEmpty()) {
          yield this.data.pop()
      }
  }
  
  pop() {
     const { value, done } = this.generator().next() 
     if(done) return false
     return value
  }
}

использовать:

const Stack = require("./stack.js")
class Operation {
   constructor(val) {
       this.value = val
   }
}
class Add extends Operation {
   apply(value) {
       return value + this.value
   ｝
   undo(value) {
       return value - this.value 
   }
}
class Times extends Operation {
   apply(value) {
       return value * this.value
   }
   undo(value) {
       return value / this.value
   }
}
/** 操作栈 **/
class OpsStack {
   constructor() {
       this.value = 0
       this.operations = new Stack()
   }
   add(op) {
       this.value = op.apply(this.value)
       this.operations.add(op) 
   }
   
   undo() {
       if(this.operations.isEmpty()) {
           return false
       }
       this.value = (this.operations.pop()).undo(this.value)
   }
}
let s = new OpsStack()
s.add(new Add(1))
s.add(new Add(1))
s.add(new Times(2))
console.log("Current value: ", s.value)
s.undo()
s.undo()
console.log("Final value: ", s.value
// Current value:  4
// Final value:  1

Классы операций (Add, Times) имеют два метода: apply делает операцию эффективной (сложение и умножение), а undo означает противоположную операцию (вычитание).

очередь ✍

определение

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

Применимая сценаБлагодаря функции очереди «первым поступил — первым обслужен» она очень удобна для управления многопоточными блокирующими очередями.

выполнить

Пример:

class Queue {
  data = [];
  maxSize;

  constructor(initialData, maxSize = -1) {
    this.data = Array.isArray(initialData) ? initialData : typeof initialData == 'undefined' ? [] : [initialData];
    this.maxSize = maxSize;
  }

  isFull() {
    return this.maxSize != -1 ? this.data.length == this.maxSize : false;
  }

  isEmpty() {
    return this.data.length == 0;
  }

  enqueue(item) {
    if (this.isFull()) {
      return false;
    }
    this.data.push(item);
  }

  *generator() {
    while (!this.isEmpty()) {
      yield this.data.shift();
    }
  }

  dequeue() {
    const { value, done } = this.generator().next();
    if (done) return false;
    return value;
  }
}

В основном реализуется методами enqueue и dequeue. Элементы можно добавлять в очередь с помощью enqueue и удалять с помощью последнего. Массивы используются здесь для базовых структур данных, потому что это значительно упрощает оба подхода. Ставить в очередь — это то же самое, что помещать элемент в массив, удаление из очереди решается простым вызовом shift, который удаляет первый элемент и возвращает его.

использовать:

const  Queue  = require('./queues')

let q = new Queue(3, 2)

q.enqueue(1)
q.enqueue(2) 

let x = 0
while(x = q.dequeue()) {
 console.log(x)
}
/*
Prints:
3
1
*/

В дополнение к простой очереди, которую я показываю здесь:

Очередь с приоритетом: ее элементы упорядочены внутри по значению приоритета.
Круговая очередь: ее последний элемент указывает на первый.
Двусторонняя очередь: структура данных со свойствами очереди и стека. Элементы в двухсторонней очереди могут быть извлечены с обоих концов (похоже на читерство!).

куча 🚀

определение

Куча — это специальная структура данных, которую можно рассматривать как куча объектов массива дерева (куча) и приоритетную очередь (priority queue). Несмотря на очереди с приоритетом имен, кучи не являются очередями. Поскольку в очереди разрешены операции «первым поступил — первым обслужен» (FIFO), элементы вставляются в конец очереди, а элементы удаляются в начале очереди. В куче, хотя элементы вставляются внизу кучи, а элементы вынимаются вверху кучи, расположение элементов в куче происходит не в порядке поступления, а в определенном приоритетном порядке. Самый верхний узел в куче называется корневым узлом, а сам корневой узел не имеет родительского узла.

Классической реализацией кучи является полное двоичное дерево, а куча, реализованная таким образом, называется двоичной кучей.

Здесь, чтобы объяснить концепцию полного бинарного дерева и концепцию полного бинарного дерева.

Полное двоичное дерево: за исключением листовых узлов, левые и правые дочерние элементы всех узлов не пусты, что представляет собой полное двоичное дерево, как показано на следующем рисунке.Можно видеть, что все узлы в полном бинарном дереве имеют левых и правых потомков. Полное бинарное дерево: это не обязательно полное бинарное дерево, но часть, которой оно не заполнено, должна быть в нижней правой части, как показано ниже.Куча с наибольшим корневым узлом называется максимальной кучей или большой корневой кучей, а куча с наименьшим корневым узлом называется минимальной кучей или малой корневой кучей. Общие кучи включают бинарные кучи, кучи Фибоначчи и т. д.

Функции

Значение любого узла — это максимальное или минимальное значение всех узлов в его поддереве.
Должно быть полным бинарным деревом

Применимая сцена

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

выполнить

Вставка минимальной кучи (ADD)

Предполагая, что существующий элемент 5 необходимо вставить, для сохранения характеристик полного бинарного дерева вновь вставленный элемент необходимо поместить в правое поддерево узла 6; в то же время, чтобы удовлетворить свойству, что значение любого узла меньше, чем значение левого и правого поддеревьев, вновь вставленный элемент следует сравнить с его родительским узлом.Если он меньше родительского узла, родительский узел должен быть опущен, чтобы заменить позицию текущий узел.Щелкните и потяните вниз, пока не останется совпадающих значений.

Здесь элемент 5 сначала вставляется в конец, то есть помещается в правое поддерево узла 6.
Затем сравните с родительским классом, 6 > 5, номер родительского класса больше, чем номер дочернего класса, дочерний класс обменивается с родительским классом.
Повторяйте это до тех пор, пока не произойдет замена.

Минимальное удаление кучи (DELETE)

核心点：将最后一个元素填充到堆顶，然后不断的下沉这个元素。

Предположим, мы хотим извлечь узел 1 из узла 1. Чтобы сохранить характеристики полного бинарного дерева, мы заменим этот элемент 1 последним элементом 6, а затем сравним отношение размеров между 1 и его поддеревом, если оно больше, чем левое и правое поддеревья ( Если оно существует), то для его замены необходимо найти меньшее значение из левого и правого поддеревьев, и оно само перейдет на позицию соответствующего поддерева, и циклически повторять эту операцию до тех пор, пока не будет нет поддерева меньшего, чем это.

Благодаря этой операции куча все еще остается кучей, чтобы подвести итог:

Найдите позицию в массиве узла, который нужно удалить (удаленный узел)
Замените элемент в этой позиции последним элементом в массиве
Сравните текущую позицию с ее левым и правым поддеревьями, чтобы обеспечить соответствие правилам минимальной кучи между узлами.
удалить последний элемент

связанный список 🏉

определение

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

преимущество

Связный список — это очень часто используемая структура данных, для нее не требуется инициализация емкости, а элементы можно добавлять или вычитать произвольно;
При добавлении или удалении элементов вам нужно только изменить поля указателя двух узлов элементов до и после адреса, поэтому добавление и удаление выполняются очень быстро;

недостаток

Поскольку он содержит большое количество полей указателя, он занимает много места;
Поиск элементов требует обхода связанного списка, что занимает очень много времени.

Применимая сцена

Сценарии, в которых объем данных невелик и требует частых операций добавления и удаления.

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

Особенности кругового связанного списка

Преимущество кругового связанного списка по сравнению с односвязным списком состоит в том, что удобнее переходить от хвоста к началу цепочки.Когда обрабатываемые данные имеют характеристики кольцевой структуры, удобно использовать круговой связанный список.

Особенности двусвязного списка.

По сравнению с односвязным списком, двусвязному списку требуется на один указатель больше, чтобы указать на предшествующий узел, поэтому, если сохраняется тот же объем данных, двусвязный список занимает больше места в памяти, чем односвязный список.
Вставка и удаление двусвязного списка должны одновременно поддерживать два указателя next и prev.
Доступ к элементам в двусвязном списке должен осуществляться последовательно и поддерживает двунаправленный обход, который является основой гибкости операций с двусвязным списком.

выполнить

Основные операции двусвязного списка

добавить элемент

По сравнению с односвязным списком двусвязный список может быть выполнен с временной сложностью O (1), в то время как односвязный список требует временной сложности O (n).

Добавленные элементы двусвязного списка включают вставку начала и конца. 头插法：Левая часть связанного списка называется головой связанного списка, а правая часть называется хвостом связанного списка. Метод вставки заголовка заключается в фиксации правой стороны, и каждый новый элемент добавляется в левый заголовок.

尾插法：Левая часть связанного списка называется головой связанного списка, а правая часть называется хвостом связанного списка. Метод вставки хвоста заключается в фиксации левой стороны, и каждое новое добавление находится в конце правой части связанного списка.

элемент запроса

Гибкость двусвязного списка заключается в том, что知道链表中的一个元素结构就可以向左或者向右开始遍历查找需要的元素结构。Следовательно, для упорядоченного связанного списка эффективность запроса по значению для двусвязного списка выше, чем для односвязного списка. Поскольку мы можем записать позицию p последнего поиска, и каждый раз, когда мы запрашиваем, мы решаем, следует ли искать вперед или назад, в соответствии с отношением между искомым значением и p, поэтому в среднем требуется только половина данных. искал.

удалить элемент

В реальной разработке программного обеспечения удаление данных из связанного списка представляет собой не что иное, как следующие две ситуации:

Удалить узлы со «значением, равным заданному значению» в узлах
удаляет узел, на который указывает данный указатель

Для двусвязного списка узлы в двусвязном списке сохранили указатель узла-предшественника, и его не нужно обходить, как односвязный список, при удалении. Следовательно, во втором случае операция удаления односвязного списка требует временной сложности O(n), а двусвязный список требует временной сложности O(1). 4. Дважды циклический связанный списокКак показано на рисунке, концепция двусвязного списка хорошо понятна: комбинация «двусвязный список» + «циклический связанный список».

дерево 🏈

определение

Дерево — это структура данных, которая состоит из n (n>=1) конечных узлов, образующих набор с иерархическими отношениями. Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что у него корни вверх, а листья вниз.

Функции

каждый узел имеет ноль или более дочерних узлов;
Узел без родительского узла называется корневым узлом;
Каждый некорневой узел имеет один и только один родительский узел;
За исключением корневого узла, каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев;

Различные части дерева называются:

Корневой узел/родительский узел: узел, под которым находятся дочерние узлы.
Листовые узлы: узлы, с которыми не связаны дочерние узлы.
Ребра: связи между двумя узлами.

Некоторые определения деревьев:

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

По структуре данных его можно разделить на разные типы деревьев:

Двоичное дерево: Двоичное дерево — это особый тип дерева. Оно быстро добавляет и удаляет элементы, а в поиске используется множество оптимизаций алгоритмов. Таким образом, двоичное дерево обладает как преимуществами связанных списков, так и массивов. Это схема оптимизации для обоих. Очень полезны при обработке больших пакетов динамических данных, они также используются для создания бинарных деревьев поиска. Одним из возможных вариантов его использования являются алгоритмы сжатия. Имеет следующие характеристики:

Каждый узел имеет не более двух поддеревьев, а максимальная степень узла равна 2.
Левое поддерево и правое поддерево идут по порядку, и порядок не может быть изменен на противоположный.
Даже если узел имеет только одно поддерево, необходимо различать левое и правое поддеревья.

Двоичное дерево поиска: также известное как двоичное дерево поиска, упорядоченное двоичное дерево или отсортированное двоичное дерево, относится к пустому дереву или двоичному дереву со следующими свойствами.

Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
Если правое поддерево любого узла не пусто, значение всех узлов в правом поддереве больше или равно значению его корневого узла;
Любой узел левого и правого поддеревьев также является бинарным деревом поиска;

Поиск в глубину (DFS): это способ найти дерево. Это работает следующим образом: сначала он проходит всю левую сторону, затем возвращается к последнему посещенному родителю, а затем переходит к правому поддереву.

Обходим результат: A->B->C->D->E. Порядок узлов определяется методом DFS, а также может проходиться в обратном порядке.

выполнить

Пример:

Реализовать бинарное дерево поиска

class BinaryTreeNode {
 constructor(value) {
   this.value = value;
   this.left_child = null;
   this.right_child = null;
 }
 compare(v) {
   if (this.value > v) return -1;
   if (this.value == v) return 0;
   if (this.value < v) return 1;
 }
}
class BST {
 constructor() {
   this.root_node = null;
 }
 /* 如果根节点为空（树为空），则elem将成为根节点
如果elem低于根节点，则切换到左边的子节点，检查是否为空
如果为空，elem将成为左子节点
如果没有，继续沿着这条路走
若elem高于或等于根节点，则切换到右子节点并检查它是否为空
如果为空，elem将成为正确的子节点
如果没有，继续沿着这条路走 */
 add(elem) {
   if (!this.root_node) {
     this.root_node = new BinaryTreeNode(elem);
     return;
   }
   let inserted = false;
   let currentNode = this.root_node;
   do {
     let comp = currentNode.compare(elem);
     if (comp == -1) {
       if (!currentNode.left_child) {
         currentNode.left_child = new BinaryTreeNode(elem);
         inserted = true;
       } else {
         currentNode = currentNode.left_child;
       }
     }
     if (comp != -1) {
       if (!currentNode.right_child) {
         currentNode.right_child = new BinaryTreeNode(elem);
         inserted = true;
       } else {
         currentNode = currentNode.right_child;
       }
     }
   } while (!inserted);
 }
 inorder(parent) {
   if (parent) {
     this.inorder(parent.left_child);
     console.log(parent.value);
     this.inorder(parent.right_child);
   }
 }
 print() {
   this.inorder(this.root_node);
 }
}

использовать:

const Tree = require("./bst")
const t = new Tree()
t.add(10)
t.add(8)
t.add(11)
t.add(23)
t.add(1)
t.add(9)
t.print()
/*
Prints: 
1
8
9
10
11
23
*/

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

Расширение:

Двоичные деревья имеют множество расширенных структур данных, включая сбалансированные бинарные деревья, красно-черные деревья, B+-деревья и т. д. Эти структуры данных основаны на бинарных деревьях и содержат множество функций, которые широко используются в практических приложениях, например, индекс базы данных. структура использования mysql Красно-черное дерево используется в дереве B+ и базовом исходном коде HashMap. Функции этих бинарных деревьев мощные, но алгоритмы сложнее.Если вы хотите научиться, вам все равно нужно потратить время на углубление.

Рисунок 🏂

определение

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

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

Применимая сцена

Графики очень универсальны, потому что их можно использовать для представления практически любого сценария, в котором объекты связаны друг с другом. Я говорю о вариантах использования, начиная от сетевых макетов и заканчивая архитектурами на основе микросервисов, реальными картами и почти всем, что вы можете себе представить.

Настолько, что все движки баз данных основаны на концепции графов (например, Neo4J — очень популярный движок). Все концепции деревьев, которые мы только что рассмотрели (такие как ребра, узлы, пути и т. д.), здесь по-прежнему применимы.

выполнить

Здесь показано простое дерево, включая способ реализации обхода поиска в глубину (что это означает, см. в разделе «Деревья»).

Пример:

class Node {

   constructor(value) {
       this.value = value
       this.links = []
   }
   
   linkTo(node, weight) {
       this.links.push(new Link(this, weight, node))
   }
}

class Link {

   constructor(a, weight, b) {
       this.left = a;
       this.weight = weight
       this.right = b
   }
}

class Graph {

   constructor(root_node) {
       this.root_node = root_node
       this.dfs_visited = new Set();
   }
   
   dfs(starting_node) {
       if(!starting_node) starting_node = this.root_node
       let node = starting_node 
       console.log(node.value);
       this.dfs_visited.add(node);
       node.links.forEach( neighbour => {
           if (!this.dfs_visited.has(neighbour.right)) {
               this.dfs(neighbour.right);
           }
       })
   }

}

использовать:

Каждый узел имеет список «ссылок», которые представляют отношения между двумя узлами. И вы можете добавить значения, которые вы хотите, где угодно (например, задержка мс для сетевых подключений, трафик между двумя местоположениями или почти все, что вы хотите). Используйте метод dfs для обхода графа, гарантируя, что каждый узел посещается только один раз. Вот пример:

//定义节点
let A = new Node("A")
let B = new Node("B")
let C = new Node("C")
let D = new Node("D")
let E = new Node("E")
let F = new Node("F")
let G = new Node("G")

//定义节点间的关系
A.linkTo(B, 1)
A.linkTo(C, 2)
B.linkTo(D, 1)
C.linkTo(E, 10)
D.linkTo(E, 10)
D.linkTo(F, 1)
D.linkTo(G, 1)
G.linkTo(G, 1)

let g = new Graph(A)
//遍历图表
g.dfs()

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

Хэш-таблица 🎉

определение

Хеш-таблица, также называемая хэш-таблицей, представляет собой структуру данных, к которой осуществляется прямой доступ в соответствии с кодом и значением ключа (ключ и значение), и она сопоставляется с позицией в коллекции с помощью ключа и значения, так что соответствующие соответствие в коллекции можно быстро найти элемент.

Место хранения записи = f(key)

Соответствующее отношение f здесь становится хэш-функцией, также известной как хэш (хэш-функция), а хэш-таблица предназначена для преобразования Ключа в целое число с помощью функции фиксированного алгоритма, так называемой хеш-функции, а затем преобразования числа в целое число. Возьмите оставшуюся часть длины массива, и результат остатка используется в качестве нижнего индекса массива, а значение сохраняется в пространстве массива с номером в качестве нижнего индекса. Это пространство для хранения может в полной мере использовать преимущество поиска массива, чтобы найти элементы, поэтому искали высокую скорость. Это позволяет хранить пары ключ-значение и быстро их извлекать (некоторые говорят, что в лучшем случае это O(1)), что довольно удивительно. Хеш-таблицы также довольно распространены в приложениях, например, некоторые классы коллекций в Java строятся с использованием заимствования принципа хеширования, например, HashMap, HashTable и т. д.

преимущество

Используя преимущества хеш-таблицы, очень удобно находить элементы коллекции;

недостаток

Поскольку хеш-таблица основана на структуре данных, производной от массива, она относительно медленно добавляет и удаляет элементы;

Применимая сцена

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

выполнить

В JavaScript реализовать хеш-карту очень просто, потому что у нас есть литералы объектов, которые мы можем использовать для добавления случайных свойств (т. е. ключей). Это необходимо для реализации хэш-карты, которая позволяет использовать числовые ключи.

Пример:

class HashMap {
   
   constructor() {
       this.map = {}
   }
   
   hash(k) {
       return k % 10
   }
   
   add(key, value) {
       let k = this.hash(key)
       if(!this.map[k]) {
           this.map[k] = []
       }
       this.map[k].push(value)
   }
   
   get(key) {
       let k = this.hash(key)
       return this.map[k]
   }
   
}

let h = new HashMap()

h.add(10, "hello")
h.add(100001, "world")
h.add(1, "this is a string")

console.log(h)

использовать:

输出结果如下

HashMap {
map: { '0': [ 'hello' ], '1': [ 'world', 'this is a string' ] }
}

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

Резюме 🥇

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

расширение 🏆

Если эта статья окажется для вас полезной, вы можете ознакомиться с другими моими статьями ❤️:

👍5 шаблонов дизайна, которые вы должны знать о веб-разработке 🍊

👍10 простых приемов, которые сделают ваш код vue.js более элегантным 🍊

👍Классические вопросы на собеседовании! Не спешите ли вы научиться вводить URL для отображения страницы? 🍊

👍Говоря о процессе рукопожатия протокола SSL🍊

Справочная статья 📜

LeetCodeAnimation

Data Structures You Should Know as a JavaScript Developer