series

  • Using JavaScript learning data structures and algorithms (1) | small volume of free learning
  • Using JavaScript learning data structures and algorithms (2) | small volume of free learning
  • Using JavaScript learning data structures and algorithms (3) | small volume of free learning
  • (4) using JavaScript learning data structure and algorithm booklet | free education

The dictionary

Dictionaries are much like collections, which are stored as values. Dictionaries store elements in the form of keys and values. Dictionaries are also called “maps.” Dictionaries store key and value pairs where the key names are used to look up a particular element. The Map data structure in EACAScript 6 is an implementation of dictionaries, which are like objects.

Hash table (Hash map Hash)

  • Hash algorithm: Find a value in the data structure as quickly as possible.
  • Handle conflicts in hash tables (only one value can be stored in the same place)
    • Split links: Create a linked list for each position in the hash table and store the elements in it.
    • Linear probe: When a new element is added to the list, if the position with index as index is already occupied, try the position with index+1, and so on, the empty position is found and unknown.
    • Double hashing
  • Better hash function djB2
let djb2HashCode = function(key) {
  let hash = 5371;
  for (let i = 0; i < key.length; i++) {
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
};
Copy the code

The tree

A tree is a non-sequential data structure that is useful for storing data that needs to be looked up quickly. A tree is a hierarchical abstract model, such as a family tree, a diagram of a company’s organizational structure, etc.

Each tree is composed of a root node and multiple child nodes. Nodes are divided into inner nodes and outer nodes. Nodes with at least one node are called inner nodes, and nodes without child elements are called outer nodes. The height of the tree depends on the maximum depth of all nodes.

Binary trees and binary trees search trees

  • A binary tree can have a maximum of two nodes, one on the left and one on the right.

  • Binary tree search tree: A binary tree search tree is a type of binary tree, but it only allows you to store values smaller (than the parent) on the left node and larger (or equal) on the right node.

Binary tree traversal

Let’s say that the left subtree is always traversed before the right subtree

  • Sequential traversal: root node -> left subtree -> right subtree
  • Middle order traversal: left subtree -> root node -> right subtree
  • Back-order traversal: left subtree -> right subtree -> root node

figure

A graph is a nonlinear data structure. A graph is a network abstract model. It is a set of nodes (or vertices) connected by edges. Any binary relationship can be represented by a graph.

The characteristics of

  • Ringed or acyclic
  • Directed graph or undirected graph
  • Weighted or unweighted
  • Whether it is strongly connected

The representation of figure

  • Adjacency matrix: is a two-dimensional array (matrix) used to describe the graph
  • Collar tables: Use dynamic data structures (linked lists, arrays, dictionaries) to describe graphs
  • Incidence matrix: The rows of a matrix represent vertices and the columns represent edges

Graph traversal

Breadth First Search (BFS)

  • Queue implementation: by queuing vertices, the top line that is queued first is searched first.
  • Simple understanding: is a layer of access traversal, go until the end.

Depth-first Search (DFS)

  • Stack implementation: by storing vertices in the stack, vertices are explored along the path, and new adjacent vertices are accessed.
  • Simple idea: start at the end of one side, and then go on to the next side until you finish.

reference

  • Basic Algorithms — Depth-first Search (DFS) and Breadth-first Search (BFS)

Original from Ninety: links to original blog posts

This article is part of the “Gold Nuggets For Free!” Event, click to view details of the event