## 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个对象的数组中查找的执行效率对比图：
```[
{
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倍的循环。

## 3. 堆栈： `Stack`

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

1. Two principles of operation: `push`and `pop`. `Push`Adding elements to the top of the array, and `Pop`remove them from the same location.
2. Follow " `Last In，First Out`", that is:, `LIFO`last 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 `unshift`and `shift`methods in place `push`and `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`, `ActiveMQ`etc.

In terms of programming ideas, it `Queue`can be described in two sentences:

• Just an array with two main operations: `unshift`and `pop`.
• Follow `"Fist In，first out"`namely: `FIFO`first 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 `unshift`and `shift`methods in place `push`and `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.

• 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 `Redux`it is constructed in the logical linked list therein.
• `React`The core algorithm `React Fiber`implementation is a linked list.
• `React Fiber`Previously `Stack Reconciler`, it was top-down recursion `mount/update`and 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 Fiber`Solve past `Reconciler`problems 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 `Express`such a `Web`framework 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
}
}

constructor() {
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.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.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) {
}
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
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()

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 `JavaScript`the 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.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 );
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) {
} 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.tail = null;
} else if (current == this.head) {
} 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) {
} 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
}
}```
• `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. `DOM`tree. Every web page has a tree data structure.
1. `Vue`And `React`is `Virtual DOM`also 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 `Google`Baidu.
• Use `LBS`map services, such as high moral, Google Maps.
• Use social media sites, such as microblogging `Facebook`.

The graphs are used in different industries and fields:

• `GPS`The 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.
• `Google`The 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:, `Node`such 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 `Edge`example, 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 `Dijkstra`algorithm 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
//print() {}
}```

#### 1. `addVertex` .: Add vertices

```addVertex(vertex) {
} else {
}
}```

Try to create vertices:

```let graph = new Graph();

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.
//Make sure the added edge does not yet exist.
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.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 `BFS`algorithm .
• Depth-first algorithm, `DFS`
• `BFS`The focus on the queue, but `DFS`the 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 `visited`object: .
• Initialize an empty array:, `q`the 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 `q`and store it in a variable.`（let current = q.pop()）`
• Print current `current`
• Acquired from the graph `current`edges. `（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 `be`6: `bear`, `bell`, `bid`, `bull`, `buy`, .

Searching for `be`a 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
//predictWord(string) {}
//logAllWords() {}
}```

#### 1 `addWord`.: Create a node

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

#### 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];
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(''));
}```

`logAllWords`By calling on an empty string `predictWord`to print`Trie` 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 `python`in the dictionary, `java`it 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. `Hashingalgorithms`A 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

`HashTables`Optimized 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 `0`and `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，e`And `f`the `ASCII`values of `97,98,99,100,101`and `102`, the sum of:`597`
• `597`It is not a prime number. Take the prime number nearby `599`to 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，e`and `f`composed
• 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 `2069`take 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);
}
}
//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 `leetcode`title 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