「中高级前端」窥探数据结构的世界- ES6版

「中高级前端」窥探数据结构的世界- ES6版

1. 什么是数据结构?

数据结构是在计算机中组织和存储数据的一种特殊方式,使得数据可以高效地被访问和修改。更确切地说,数据结构是数据值的集合,表示数据之间的关系,也包括了作用在数据上的函数或操作。

1.1 为什么我们需要数据结构?

  • 数据是计算机科学当中最关键的实体,而数据结构则可以将数据以某种组织形式存储,因此,数据结构的价值不言而喻。
  • 无论你以何种方式解决何种问题,你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单,还是只是简单的电话簿问题。
  • 数据需要根据不同的场景,按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

1.2 八大常见的数据结构

  1. 数组: Array
  2. 堆栈: Stack
  3. 队列: Queue
  4. 链表: Linked Lists
  5. 树: Trees
  6. 图: Graphs
  7. 字典树: Trie
  8. 散列表(哈希表): Hash Tables

在较高的层次上,基本上有三种类型的数据结构:

  • 堆栈和队列是类似于数组的结构,仅在项目的插入和删除方式上有所不同。
  • 链表,树,和图 结构的节点是引用到其他节点。
  • 散列表依赖于散列函数来保存和定位数据。

在复杂性方面:

  • 堆栈和队列是最简单的,并且可以从中构建链表。
  • 树和图 是最复杂的,因为它们扩展了链表的概念。
  • 散列表和字典树 需要利用这些数据结构来可靠地执行。

就效率而已:

  • 链表是记录和存储数据的最佳选择
  • 而哈希表和字典树 在搜索和检索数据方面效果最佳。

2.数组 - 知识补充

数组是最简单的数据结构,这里就不讲过多了。 贴一张每个函数都运行10,000次迭代:

  • 10,000个随机密钥在10,000个对象的数组中查找的执行效率对比图:
[
  {
    id: "key0",
    content: "I ate pizza 0 times"
  },
  {
    id: "key1",
    content: "I ate pizza 1 times"
  },
  {
    id: "key2",
    content: "I ate pizza 2 times"
  },
  ...
]

["key284", "key958", "key23", "key625", "key83", "key9", ... ]

2.1 for...in为何这么慢?

for...in语法令人难以置信的缓慢。在测试中就已经比正常情况下慢近9倍的循环。

这是因为 for...in语法是第一个能够迭代对象键的JavaScript语句。

循环对象键( {})与在数组( [])上进行循环不同,

因为引擎会执行一些额外的工作来跟踪已经迭代的属性。

3. 堆栈: Stack

堆栈是元素的集合,可以在顶部添加项目,我们有几个实际的堆栈示例:

  • 浏览器历史记录
  • 撤消操作
  • 递归以及其它。

三句话解释堆栈:

  1. Two principles of operation: pushand pop. PushAdding elements to the top of the array, and Popremove them from the same location.
  2. Follow " Last In,First Out", that is:, LIFOlast in first out.
  3. Gone.

3.1 Implementation of the stack.

Please note that in the example below, we can reverse the order of the stack: the bottom becomes the top, and the top becomes the bottom.

Therefore, we can use an array respectively unshiftand shiftmethods in place pushand pop.

class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }

    pop() {
        return this.reverse? this.stack.shift(): this.stack.pop();
    }
}

const stack = new Stack(4, 5);
stack.reverse = true;
console.log(stack.push(1, 2, 3) === 5)//true
console.log(stack.stack ===[1, 2, 3, 4, 5])//true

4. Queue: Queue

In computer science, a queue is a special type of abstract data type or collection. The entities in the collection are stored in order.

In front-end development, the most famous use of queues is undoubtedly the knowledge of macro tasks and micro tasks, task queues in the browser/NodeJs. I won't repeat it here.

In the back-end field, the most widely used message queue is Messagequeue: such as RabbitMQ, ActiveMQetc.

In terms of programming ideas, it Queuecan be described in two sentences:

  • Just an array with two main operations: unshiftand pop.
  • Follow "Fist In,first out"namely: FIFOfirst in first out.

4.1 Implementation of Queue

Please note that in the example below, we can reverse the order of the heap queue.

Therefore, we can use an array respectively unshiftand shiftmethods in place pushand pop.

class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }

    dequeue() {
        return this.reverse? this.queue.shift(): this.queue.pop();
    }
}

5. Linked list: LinkedLists

Like arrays, linked lists store data elements in order.

The linked list does not retain the index, but points to other elements.

The first node is called the head ( head), and the last node is called the tail ( tail).

Single linked list and doubly linked list:

  • A singly linked list is a data structure that represents a series of nodes, where each node points to the next node in the list.
  • Linked lists usually need to traverse the entire operation list, so the performance is poor.
  • One way to improve the performance of a linked list is to add a second pointer to the previous node in the list on each node.
  • The doubly linked list has nodes that point to the elements before and after it.

Advantages of linked lists:

  • Links have constant time insertion and deletion, because we can only change the pointer.
  • Like arrays, linked lists can operate as stacks.

Application scenarios of linked lists:

Linked lists are useful on both the client and the server.

  • On the client, as Reduxit is constructed in the logical linked list therein.
  • ReactThe core algorithm React Fiberimplementation is a linked list.
    • React FiberPreviously Stack Reconciler, it was top-down recursion mount/updateand could not be interrupted (continuously occupying the main thread), so periodic tasks such as layout and animation on the main thread and interactive responses could not be processed immediately, affecting the experience.
    • React FiberSolve past Reconcilerproblems idea is to render/update process (recursive diff) split into a series of small tasks, each inspection, a small portion of the tree, done to see if there is still time to continue to the next task, any continued If not, suspend yourself and continue when the main thread is not busy.
  • On the server, as Expresssuch a Webframework are also constructed in a similar manner intermediate its logic. When a request is received, it is piped from one middleware to the next until the response is sent.

5.1 Realization of singly linked list

The core operations of singly linked lists are:

  • push(value) -Add a node at the end/head of the linked list
  • pop() -Delete a node from the end/head of the linked list
  • get(index) -Return the node at the specified index
  • delete(index) -Delete the node at the specified index
  • isEmpty() -Return true or false according to the length of the list
  • print() -Return the visible representation of the linked list
class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
   //length is not necessary
    this.length = 0
  }
  push(data) {
   //Create a new node
    const node = new Node(data)
   //Check if the head is empty
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
   //first check if the linked list is empty
    if(this.isEmpty()) {
      return null
    } 
   //if the length is 1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate

    while (currentNode) {
      if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }

    penultimate.next = null
    this.tail = penultimate
    this.length -
    return node
  }

  get(index){
   //deal with boundary conditions
    if (index === 0) {
      return this.head
    }
    if (index <0 || index> this.length) {
      return null
    }

    let currentNode = this.head
    let i = 0
    while(i <index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode

  }
  delete(index){
    let currentNode = this.head

    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--

      return deletedNode
    }

    if (index <0 || index> this.length) {
      return null
    }

    let i = 0
    let previous

    while(i <index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }

  isEmpty() {
    return this.length === 0
  }
  print() {
    const list = []
    let currentNode = this.head
    while(currentNode){
      list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join(' =>')
  }
}

have a test:

const l = new LinkedList()

//Add node
const values ​​= ['A','B','C']
values.forEach(value => l.push(value))

console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())

5.2 Realization of doubly linked list

1. Design of doubly linked list

Similar to a singly linked list, a doubly linked list consists of a series of nodes. Each node contains some data and a pointer to the next node in the list and a pointer to the previous node. This is JavaScriptthe simple, he said:

class Node {
    constructor(data) {
       //data contains the value that the linked list item should store
        this.data = data;
       //next is a pointer to the next item in the list
        this.next = null;
       //prev is a pointer to the previous item in the list
        this.prev = null;
    }
}

Just type it again:

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }
   //Various operation methods
   //...
}

2. Operation method of doubly linked list

  • Append & AppendAt: Add a node at the end/specified position of the linked list
append( item) {
  let node = new Node( item );
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node
  }
}
appendAt( pos, item) {
   let current = this.head;
   let counter = 1;
   let node = new Node( item );
   if( pos == 0) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } else {
     while(current) {
      current = current.next;
      if( counter == pos) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}
  • Remove & RemoveAt: Delete the node at the end/specified position of the linked list
remove( item) {
  let current = this.head;
  while( current) {
    if( current.data === item) {
      if( current == this.head && current == this.tail) {
        this.head = null;
        this.tail = null;
      } else if (current == this.head) {
        this.head = this.head.next
        this.head.prev = null
      } else if (current == this.tail) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}
removeAt( pos) {
  let current = this.head;
  let counter = 1;
  if( pos == 0) {
   this.head = this.head.next;
   this.head.prev = null;
  } else {
   while( current) {
    current = current.next
    if (current == this.tail) {
     this.tail = this.tail.prev;
     this.tail.next = null;
    } else if( counter == pos) {
     current.prev.next = current.next;
     current.next.prev = current.prev;
     break;
    }
    counter++;
   }
  }
}
  • Reverse: Flip doubly linked list
reverse(){
  let current = this.head;
  let prev = null;
  while( current ){
   let next = current.next
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}
  • Swap: Exchange between two nodes.
swap( node1. nodeTwo) {
   let current = this.head;
   let counter = 0;
   let firstNode;
   while( current !== null) {
     if( counter == nodeOne ){
       firstNode = current;
     } else if( counter == nodeTwo) {
       let temp = current.data;
       current.data = firstNode.data;
       firstNode.data = temp;
     }
     current = current.next;
     counter++;
   }
   return true
}
  • IsEmpty & Length: Query whether it is empty or length.
length() {
  let current = this.head;
  let counter = 0;
  while( current !== null) {
   counter++
   current = current.next
  }
  return counter;
}
isEmpty() {
  return this.length() <1
}
  • Traverse: Traverse the linked list
traverse( fn) {
   let current = this.head;
   while( current !== null) {
    fn(current)
    current = current.next;
   }
   return true;
}

Add 10 to each item

  • Search: Find the index of the node.
search( item) {
  let current = this.head;
  let counter = 0;
  while( current) {
    if( current.data == item) {
     return counter
    }
    current = current.next
    counter++
  }
  return false;
}

6. Tree: Tree

A non-linear data structure often used in computers-tree (Tree), because of the obvious hierarchical characteristics between all elements stored, it is often used to store data with hierarchical relationships, such as in file systems Files; will also be used to store ordered lists, etc.

  • In the tree structure, each node has only one parent node. If a node has no parent node, it is called the root node of the tree, referred to as the root of the tree.
  • Each node can have multiple child nodes.
  • Nodes without child nodes are called leaf nodes.
  • The number of child nodes owned by a node is called the degree of the node.
  • The largest degree among all nodes is called the degree of the tree. The maximum level of the tree is called the depth of the tree.

6.1 Classification of trees

The common tree classification is as follows, among which we can master the binary search tree.

  • Binary tree: Binary Search Tree
  • AVL tree: AVL Tree
  • Red-black tree: Red-Black Tree
  • Line segment tree: Segment Tree-with min/max/sum range queries examples
  • Fenwick Tree: Fenwick Tree( Binary Indexed Tree)

6.2 Application of tree

  1. DOMtree. Every web page has a tree data structure.
  1. VueAnd Reactis Virtual DOMalso a tree.

6.3 Binary tree: BinarySearchTree

  • Binary tree is a special tree with no more than two child nodes.
  • They are called the left subtree and the right subtree of the node respectively.
  • Binary trees are often used as binary search trees and binary search trees, or binary sort trees (BST).

6.4 Traversal of Binary Tree

Walk through all the nodes of the binary tree according to certain rules and order, so that each node is visited once and only once. This operation is called tree traversal , which is one of the most basic operations on the tree.

Since the binary tree is a non-linear structure, the traversal of the tree essentially converts each node of the binary tree into a linear sequence to represent it.

According to the order in which the root node is visited, the traversal of the binary tree is divided into the following three types: preorder traversal, middle order traversal, and postorder traversal;

Preorder traversal :Pre-Order

Root Node -> Left Subtree -> Right Subtree

In-order traversal :In-Order

Left subtree -> root node -> right subtree

Post-order traversal :Post-Order

Left subtree -> right subtree -> root node

Therefore, we can get the traversal results of the above binary tree as follows:

  • Preorder traversal: ABDEFGC
  • Mid-order traversal: DEBGFAC
  • Post-order traversal: EDGFBCA

6.5 Implementation of Binary Tree

class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = value
  } 
} 

class BST {
    constructor() {
        this.root = null
    }
   //Various operations of binary tree
   //insert(value) {...}
   //insertNode(root, newNode) {...}
   //...

1. insertNode& insert: Insert a new child node/node

insertNode(root, newNode) {
    if (newNode.value <root.value) {
     //First perform no left node operation
      (!root.left)? root.left = newNode: this.insertNode(root.left, newNode)
    } else {
      (!root.right)? root.right = newNode: this.insertNode(root.right, newNode)
    }
  }

insert(value) {
    let newNode = new Node(value)
   //If there is no root node
    if (!this.root) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
}

2. removeNode& remove: Remove child nodes/nodes

removeNode(root, value) {
    if (!root) {
      return null
    }

   //Start to judge from the value less than the root node
    if (value <root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value> root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
     //If there is no left and right nodes
      if (!root.left && !root.right) {
        root = null
        return root
      }

     //There is a left node
      if (root.left) {
        root = root.left
        return root
     //There is a right node
      } else if (root.right) {
        root = root.right
        return root
      }

     //Get the minimum value of the correct child node to ensure that we have a valid replacement
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
     //Make sure to delete the replaced node
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }

remove(value) {
    if (!this.root) {
      return'Tree is empty!'
    } else {
      this.removeNode(this.root, value)
    }
}

3 findMinNode.: Get the minimum value of the child node

findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}

4. searchNode& search: Find child nodes/nodes

searchNode(root, value) {
    if (!root) {
      return null
    }

    if (value <root.value) {
      return this.searchNode(root.left, value)
    } else if (value> root.value) {
      return this.searchNode(root.right, value)
    }

    return root
}

search(value) {
    if (!this.root) {
      return'Tree is empty'
    } else {
      return Boolean(this.searchNode(this.root, value))
    }
}
  1. Pre-Order: Preorder traversal
preOrder(root) {
    if (!root) {
      return'Tree is empty'
    } else {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }
  1. In-Order: Mid-order traversal
inOrder(root) {
    if (!root) {
      return'Tree is empty'
    } else {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }
  1. Post-Order: Post-order traversal
postOrder(root) {
    if (!root) {
      return'Tree is empty'
    } else {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}

7. Picture: Graph

A graph is a data structure composed of a collection of nodes with edges. The graph can be directional or non-directional.

The introduction of the picture is popular, and I found a circle of articles, but this is the best:

Graphs—-A Visual Introduction for Beginners

7.1 Application of graphs

In the following scenarios, you have used graphs:

  • Use search services, such as GoogleBaidu.
  • Use LBSmap services, such as high moral, Google Maps.
  • Use social media sites, such as microblogging Facebook.

The graphs are used in different industries and fields:

  • GPSThe system and Google Maps use graphs to find the shortest path from one destination to another.
  • Social networks use graphs to represent the connections between users.
  • GoogleThe search algorithm uses graphs to determine the relevance of search results.
  • Operations research is a field that uses graphs to find the best way to reduce the cost of transportation and delivery of goods and services.
  • Even chemistry uses diagrams to represent molecules!

Graphs can be said to be one of the most widely used data structures. There are graphs everywhere in real scenes.

7.2 Graph composition

Diagrams are used to represent, find, analyze and optimize the connections between elements (houses, airports, locations, users, articles, etc.).

1. The basic elements of a graph

  • Node:, Nodesuch as a certain station in a subway station/a certain village in multiple villages/a certain host in the Internet/people in interpersonal relationships.
  • Edge: For Edgeexample, the direct connection between two stations in a subway station is an edge.

2. Symbols and terminology

  • |V|= The total number of vertices (nodes) in the graph.
  • |E|= Total number of connections (edges) in the graph.

In the example below

|V| = 6 
|E| = 7

3. Directed and undirected graphs

Graphs are classified according to the characteristics of their edges (connections).

1. a directed graph

In a directed graph, edges have directions. They go from one node to another node, and cannot return to the original node through that edge.

As shown in the image below, the edges (connections) now have arrows pointing in specific directions. Think of these edges as one-way streets. You can go in one direction and reach your destination, but you cannot return via the same street, so you need to find another path.

Directed graph

2. Undirected graph

In this type of graph, the edges are undirected (they have no specific direction). Treat undirected edges as two-way streets. You can go from one node to another and return the same "path".

4. Weighted graph

In a weighted graph, each edge has a value (called a weight) associated with it. This value is used to represent a certain quantifiable relationship between the nodes they connect. E.g:

  • The weight can represent distance, time, and the number of connections shared between two users in a social network.
  • Or anything that can be used to describe the connections between nodes in the context you are using.

The famous Dijkstraalgorithm is to use these weights by finding the shortest or optimal route between the nodes in the network to optimize routing.

5. Sparse and dense graphs

When the number of edges in the graph is close to the maximum number of edges, the graph is dense.

Dense map

When the number of edges in the graph is significantly less than the maximum number of edges, the graph is sparse.

Sparse graph

6. Loop

If you follow a series of connections in the graph, you may find a path that will take you back to the same node. It's like "walking in a circle", like you are driving around a city, the path you walk can bring you back to your original position. ?

In the figure, these "circular" paths are called "loops." They are valid paths that start and end on the same node. For example, in the image below, you can see that if you start from any node, you can return to the same node by following the edge.

Cycles are not always "isolated" because they can be part of a larger graph. They can be detected by starting a search on a specific node and finding the path that takes you back to the same node.

Cycle diagram

7.3 Realization of the graph

We will implement a directed graph with an adjacency list.

class Graph {
  constructor() {
    this.AdjList = new Map();
  }

 //Basic operation method
 //addVertex(vertex) {}
 //addEdge(vertex, node) {}
 //print() {}
}

1. addVertex .: Add vertices

addVertex(vertex) {
  if (!this.AdjList.has(vertex)) {
    this.AdjList.set(vertex, []);
  } else {
    throw'Already Exist!!!';
  }
}

Try to create vertices:

let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');

After printing, you will find:

Map {
  'A' => [],
  'B' => [],
  'C' => [],
  'D' => []
}

The reason why they are all empty arrays '[]'is because the edge ( Edge) relationship needs to be stored in the array . For example, the following figure:

Of the figure Map will be:

Map {
  'A' => ['B','C','D'],
 //B doesn't point to anything
  'B' => [],
  'C' => ['B'],
  'D' => ['C']
}

2 addEdge.: Add edge (Edge )

addEdge(vertex, node) {
   //Before adding an edge to a vertex, you must verify that the vertex exists.
    if (this.AdjList.has(vertex)) {
     //Make sure the added edge does not yet exist.
      if (this.AdjList.has(node)){
        let arr = this.AdjList.get(vertex);
       //If all passes, then you can add the edge to the vertex.
        if(!arr.includes(node)){
          arr.push(node);
        }
      }else {
        throw `Can't add non-existing vertex ->'${node}'`;
      }
    } else {
      throw `You should add'${vertex}' first`;
    }
}

3. print:Print the picture ( Graph)

print() {
  for (let [key, value] of this.AdjList) {
    console.log(key, value);
  }
}

have a test

let g = new Graph();
let arr = ['A','B','C','D','E','F'];
for (let i = 0; i <arr.length; i++) {
  g.addVertex(arr[i]);
}
g.addEdge('A','B');
g.addEdge('A','D');
g.addEdge('A','E');
g.addEdge('B','C');
g.addEdge('D','E');
g.addEdge('E','F');
g.addEdge('E','C');
g.addEdge('C','F');
g.print();
/* PRINTED */
//A ['B','D','E']
//B ['C']
//C ['F']
//D ['E']
//E ['F','C']
//F []

So far, this is all you need to create the graph. However, in 99% of cases, you will be required to implement two other methods:

  • Breadth-first BFSalgorithm .
  • Depth-first algorithm, DFS
  • BFSThe focus on the queue, but DFSthe focus is recursive. This is their essential difference.

5. Breadth-first algorithm implementation

Breadth-First Search is the same as Breadth-First Search.

It is a search algorithm implemented using queues . To put it simply, the search process is similar to "throwing a stone into the lake to cause layers of ripples."

As shown in the figure above, starting from the starting point, for each point out of the queue, it is necessary to traverse the points around it. Therefore, the search process of BFS is very similar to "throwing a stone into the lake to cause ripples", which is the origin of the "breadth" in the "breadth first search algorithm".

The specific steps of the algorithm are:

  • BFS takes the starting node as a parameter. (For example 'A')
  • Initialize an empty visitedobject: .
  • Initialize an empty array:, qthe array will be used as a queue.
  • Mark the starting node as visited. (visited = {'A': true})
  • Put the starting node in the queue. (q = ['A'])
  • Loop until the queue is empty

Inside the loop:

  • Elements derive qand store it in a variable.(let current = q.pop())
  • Print current current
  • Acquired from the graph currentedges. (let arr = this.AdjList.get(current)).
  • If the elements are not visited, mark each element as visited and put it in the queue.
visited = {
  'A': true,
  'B': true,
  'D': true,
  'E': true
}
q = ['B','D','E']

Concrete realization :

createVisitedObject(){
  let arr = {};
  for(let key of this.AdjList.keys()){
    arr[key] = false;
  }
  return arr;
}

bfs(startingNode){
  let visited = this.createVisitedObject();
  let q = [];

  visited[startingNode] = true;
  q.push(startingNode);

  while(q.length){
    let current = q.pop()
    console.log(current);

    let arr = this.AdjList.get(current);

    for(let elem of arr){
      if(!visited[elem]){
        visited[elem] = true;
        q.unshift(elem)
      }
    }

  }
}

6. Depth-first algorithm implementation

The depth-first search algorithm (Depth-First-Search, abbreviated as DFS) is a search algorithm implemented by recursion. Simply put, the search process is similar to "don't hit the south wall and don't look back".

As shown in the figure above, starting from the starting point, first traverse all the points in one direction before changing the direction... Therefore, the search process of DFS is very similar to "Don’t hit the south wall and don’t look back", which means " The origin of "depth" in "depth-first search algorithm".

The early steps of the algorithm are similar to BFS, accepting the starting node and tracking the visited node, and finally executing a recursive auxiliary function.

Specific steps:

  • Accept the starting point as a parameter dfs(startingNode).
  • Create an access object let visited = this.createVisitedObject().
  • Call the auxiliary function to recursively start the node and visit the object this.dfsHelper(startingNode, visited).
  • dfsHelper Mark it as visited and print it out.
createVisitedObject(){
  let arr = {};
  for(let key of this.AdjList.keys()){
    arr[key] = false;
  }
  return arr;
}

 dfs(startingNode){
    console.log('\nDFS')
    let visited = this.createVisitedObject();
    this.dfsHelper(startingNode, visited);
  }

  dfsHelper(startingNode, visited){
    visited[startingNode] = true;
    console.log(startingNode);

    let arr = this.AdjList.get(startingNode);

    for(let elem of arr){
      if(!visited[elem]){
        this.dfsHelper(elem, visited);
      }
    }
  }

  doesPathExist(firstNode, secondNode){
    let path = [];
    let visited = this.createVisitedObject();
    let q = [];
    visited[firstNode] = true;
    q.push(firstNode);
    while(q.length){
      let node = q.pop();
      path.push(node);
      let elements = this.AdjList.get(node);
      if(elements.includes(secondNode)){
        console.log(path.join('->'))
        return true;
      }else{
        for(let elem of elements){
          if(!visited[elem]){
            visited[elem] = true;
            q.unshift(elem);
          }
        }
      }
    }
    return false;
  }
}

Vans,Next.

8. Dictionary tree: Trie

Trie(Usually pronounced "try") is a tree data structure optimized for specific types of searches. You can use it when you want to get a partial value and return a set of possible complete values Trie. The typical example is automatic completion.

Trie, Is a kind of search tree, also called dictionary tree or word search tree, and also called prefix tree, because the descendants of a node have a common prefix.

Its characteristics:

  • The keys are all strings, which can achieve efficient query and insertion. The time complexity is O(k), k is the length of the string
  • The disadvantage is that it consumes memory if a large number of strings do not have a common prefix.
  • Its core idea is to reduce unnecessary character comparisons and make queries more efficient.
  • That is, the space is exchanged for time, and the common prefix is ​​used to improve query efficiency.

For example: search prefix "b" would match the value returned be6: bear, bell, bid, bull, buy, .

Searching for bea match with the prefix " " will return 2 values:bear,bell

8.1 Application of Dictionary Tree

You can use it whenever you want to match the prefix with a possible complete value Trie.

In reality, it is mostly used in:

  • Auto-fill/pre-enter
  • search for
  • Input method options
  • classification

Can also be used in:

  • IP address search
  • telephone number
  • And more...

8.2 Implementation of Dictionary Tree

class PrefixTreeNode {
  constructor(value) {
    this.children = {};
    this.endWord = null;
    this.value = value;
  }
}
class PrefixTree extends PrefixTreeNode {
  constructor() {
    super(null);
  }
 //Basic operation method
 //addWord(string) {}
 //predictWord(string) {}
 //logAllWords() {}
}

1 addWord.: Create a node

addWord(string) {
    const addWordHelper = (node, str) => {
        if (!node.children[str[0]]) {
            node.children[str[0]] = new PrefixTreeNode(str[0]);
            if (str.length === 1) {
                node.children[str[0]].endWord = 1;
            } else if (str.length> 1) {
                addWordHelper(node.children[str[0]], str.slice(1));
        }
    };
    addWordHelper(this, string);
}

2 predictWord.: Predict the word

That is: given a string, return all words in the tree starting with that string.

predictWord(string) {
    let getRemainingTree = function(string, tree) {
      let node = tree;
      while (string) {
        node = node.children[string[0]];
        string = string.substr(1);
      }
      return node;
    };

    let allWords = [];

    let allWordsHelper = function(stringSoFar, tree) {
      for (let k in tree.children) {
        const child = tree.children[k]
        let newString = stringSoFar + child.value;
        if (child.endWord) {
          allWords.push(newString);
        }
        allWordsHelper(newString, child);
      }
    };

    let remainingTree = getRemainingTree(string, this);
    if (remainingTree) {
      allWordsHelper(string, remainingTree);
    }

    return allWords;
  }

3 logAllWords.: Print all nodes

logAllWords() {
    console.log('------ all nodes in the dictionary tree-----------')
    console.log(this.predictWord(''));
  }

logAllWordsBy calling on an empty string predictWordto printTrie all nodes.

9. Hash table (hash table): HashTables

Use hash tables to perform very fast lookup operations. But what exactly is a hash table?

Built-in data structures, like many languages pythonin the dictionary, javait is HashMap, are based on a hash table implementation. But what exactly is a hash table?

9.1 What is a hash table?

Hashing is a method of processing data in computer science. Through a certain function/algorithm (called hash function/algorithm), the item to be retrieved and the index used for retrieval (called hashing, Or hash value) to generate a data structure that is easy to search (called a hash table). Also translated as hash. The old translation Hash (it was mistaken for a person's name and used a transliteration). It is also often used as an information security implementation method. HashingalgorithmsA data fingerprint ( data fingerprint) calculated by a hash algorithm ( ) in a string of data is often used to identify whether files and data have been tampered with to ensure that the files and data are authentic It is provided by the original creator. —-Wikipedia

9.2 The composition of the hash table

HashTablesOptimized the storage of key-value pairs. In the best case, the insertion, retrieval and deletion of the hash table is constant time. Hash tables are used to store large amounts of quickly accessible information, such as passwords.

A hash table can be conceptualized as an array, which contains a series of tuples stored in an internal sub-array of the object:

{[[['a', 9], ['b', 88]], [['e', 7], ['q', 8]], [['j', 7], ['l ',8]]]};
  • The external array has multiple buckets (sub-arrays) equal to the maximum length of the array.
  • Inside the bucket, tuples or two-element arrays hold key-value pairs.

9.3 Basic knowledge of hash tables

Here I will try to explain the basic knowledge of hash tables clearly in a vernacular form:

Hashing is a technique used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:

  • In universities, each student is assigned a unique volume number that can be used to retrieve information about them.
  • In the library, each book is assigned a unique number, which can be used to determine information about the book, such as the exact location in the library or the user who has issued the book.

In both examples, students and books are divided into a unique number.

1. Think about a problem

Suppose there is an object and you want to assign a key to it to facilitate searching. To store key/value pairs, you can use a simple array, such as a data structure, where the key (integer) can be used directly as an index to store the value.

However, if the key is large and cannot be used directly as an index, then hashing should be used.

2, the birth of a hash table

Specific steps are as follows:

  1. In hashing, a large key is converted to a small key by using a hash function .
  2. These values ​​are then stored in a data structure called a hash table.
  3. The idea of ​​hashing is to distribute items (key/value pairs) uniformly in an array. Assign a key (transition key) to each element.
  4. By using this button, you can O(1)access the element time.
  5. Using a key, an algorithm (hash function) to calculate an index, you can find or insert the position of the entry.

The specific implementation is divided into two steps:

  • The element is converted to an integer by using a hash function. This element can be used as an index to store the original element, which belongs to the hash table.
  • The element is stored in a hash table, and it can be retrieved quickly using the hash key.
hash = hashfunc(key)
index = hash % array_size

In this method, the hash has nothing to do with the size of the array, and then by using the operator (%) which was reduced to index (between 0and array_size之间的数字-1).

3. Hash function

  • A hash function is any function that can be used to map a data set of any size to a data set of a fixed size, which is a hash table
  • The value returned by the hash function is called a hash value, hash code, hash value or simple hash value.

To achieve a good hashing mechanism, the following basic requirements are required:

  1. Easy to calculate: It should be easy to calculate and cannot be the algorithm itself.
  2. Uniform distribution: It should provide uniform distribution in the hash table and should not cause clustering.
  3. Fewer conflicts: conflicts occur when pairs of elements are mapped to the same hash value. These should be avoided.

Note: No matter how robust the hash function is, conflicts will inevitably occur. Therefore, in order to maintain the performance of the hash table, it is important to manage conflicts through various conflict resolution techniques.

4. Good hash function

Assuming you have to use hashing technology {“abcdef”,“bcdefa”,“cdefab”,“defabc”} such as strings are stored in a hash table.

The first is to build an index:

  • a,b,c,d,eAnd fthe ASCIIvalues of 97,98,99,100,101and 102, the sum of:597
  • 597It is not a prime number. Take the prime number nearby 599to reduce the possibility of indexing different strings (conflict).

The hash function will calculate the same index for all strings, and the strings will be stored in the hash table in the following format.

Since all strings have the same index, all strings are in the same "bucket" at this time.

  • Here, string needs to access a specific O(n)time (where n is the number of strings).
  • This shows that the hash function is not a good hash function.

How to optimize this hash function?

Pay attention to the similarities and differences of these strings

{"Abcdef", "bcdefa", "cdefab", "defabc"}
  • They are made a,b,c,d,eand fcomposed
  • The difference lies in the order of composition.

Let's try different hash functions.

  • The index of a particular string will be equal to the sum of the ASCII values ​​of the characters multiplied by their respective order in the string
  • Then 2069take the remainder of it and (prime number).

String hash function index

String

Index generation

Calculated

abcdef

(97 1 + 98 2 + 99 3 + 100 4 + 101 5 + 102 6)% 2069

38

bcdefa

(98 1 + 99 2 + 100 3 + 101 4 + 102 5 + 97 6)% 2069

23

cdefab

(99 1 + 100 2 + 101 3 + 102 4 + 97 5 + 98 6)% 2069

14

defabc

(100 1 + 101 2 + 102 3 + 97 4 + 98 5 + 99 6)% 2069

11

Under reasonable assumptions, the average time required to search for elements in the hash table should be O(1).

9.4 Implementation of Hash Table

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

class HashTableWithChaining {
    constructor( size = 10) {
        this.table = new Array( size );
    }

   //method of operation
   //computeHash( string) {...}
   //...
}

1 isPrime.: Judgment of prime numbers

isPrime( num) {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num% i === 0) return false; 
    return num !== 1;
}

2 computeHash|findPrime.: Hash function generation

computeHash( string) {
    let H = this.findPrime( this.table.length );
    let total = 0;
    for (let i = 0; i <string.length; ++i) {
          total += H * total + string.charCodeAt(i);
       }
    return total% this.table.length;
}
//Take the modulus
findPrime( num) {
    while(true) {
        if( this.isPrime(num) ){ break;}
        num += 1
    }
    return num;
}

3 Put.: Insert value

put( item) {
    let key = this.computeHash( item );
    let node = new Node(item)
    if (this.table[key]) {
        node.next = this.table[key]
    }
    this.table[key] = node
}

4 Remove.: Delete value

remove( item) {
    let key = this.computeHash( item );
    if( this.table[key]) {
        if( this.table[key].data === item) {
            this.table[key] = this.table[key].next
        } else {
            let current = this.table[key].next;
            let prev = this.table[key];
            while( current) {
                if( current.data === item) {
                    prev.next = current.next
                }
                prev = current
                current = current.next;
            }
        }
    }
}

5 contains.: Judgment contains

contains(item) {
    for (let i = 0; i <this.table.length; i++) {
        if (this.table[i]) {
            let current = this.table[i];
            while (current) {
                if (current.data === item) {
                    return true;
                }
                current = current.next;
            }
        }
    }
    return false;
}

6. Size&IsEmpty:Judging the length or empty

size( item) {
  let counter = 0
  for(let i=0; i<this.table.length; i++){
    if( this.table[i]) {
      let current = this.table[i]
      while( current) {
        counter++
        current = current.next
      }
    }
  }
  return counter
}
isEmpty() {
  return this.size() <1
}

7 Traverse.: Traverse

traverse( fn) {
  for(let i=0; i<this.table.length; i++){
    if( this.table[i]) {
      let current = this.table[i];
      while( current) {
        fn( current );
        current = current.next;
      }
    }
  }
}

Finally, release the execution efficiency graph of the hash table

10. Why write this

It's still related to the interview. Although the leetcodetitle on some brush, but because of the overall lack of awareness of the data structure. Many times when asked or tested, there will be nothing to do.

Most of the posts on the Internet are of different depths. I read a lot of materials and examples in the process of writing this article. The following articles are summaries of the learning process. If you find errors, please leave a message to point out.

reference:

  1. DS with JS-Hash Tables— I
  2. Joseph Crick-Practical Data Structures for Frontend Applications: When to use Tries
  3. Thon Ly-Data Structures in JavaScript
  4. Graphs — A Visual Introduction for Beginners
  5. Graph Data Structure in JavaScript
  6. Trie (Keyword Tree)

Seeking an internal recommendation in Shenzhen

Okay, I'm finished with another article, and enter the topic:

At present, I am (again) preparing to quit. I hope that the big brothers and HR ladies can promote a reliable front-end position in Shenzhen!

  • WeChat: huab119
  • mailbox: 454274033@qq.com

Author Nuggets Article Collection

If you need to repost it to the official account, just call me to add the whitelist.

  • "Vue Practice" A Vue CLI plug-in in 5 minutes
  • "Vue practice" arm your front-end project
  • "Intermediate and advanced front-end interview" JavaScript handwritten code invincible cheats
  • ``Learn from the source code'' Vue question answers that interviewers don't know
  • "Learn from the source code" JS Sao operation in Vue source code
  • "Learn from the source code" thoroughly understand the Vue option Props
  • The correct posture of the "Vue practice" project to upgrade vue-cli3
  • Why can't you understand the JavaScript scope chain?
Reference: https://cloud.tencent.com/developer/article/1488437 "Intermediate and high-end front-end" peeking into the world of data structures-ES6 version-Cloud + community-Tencent Cloud