数据结构是在计算机中组织和存储数据的一种特殊方式，使得数据可以高效地被访问和修改。更确切地说，数据结构是数据值的集合，表示数据之间的关系，也包括了作用在数据上的函数或操作。
Array
Stack
Queue
Linked Lists
Trees
Graphs
Trie
Hash Tables
在较高的层次上，基本上有三种类型的数据结构:
在复杂性方面：
就效率而已：
数组是最简单的数据结构，这里就不讲过多了。 贴一张每个函数都运行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", ... ]
for...in
为何这么慢？for...in
语法令人难以置信的缓慢。在测试中就已经比正常情况下慢近9倍的循环。
这是因为 for...in
语法是第一个能够迭代对象键的JavaScript语句。
循环对象键（ {}
）与在数组（ []
）上进行循环不同，
因为引擎会执行一些额外的工作来跟踪已经迭代的属性。
Stack
堆栈是元素的集合，可以在顶部添加项目，我们有几个实际的堆栈示例：
三句话解释堆栈：
push
and pop
. Push
Adding elements to the top of the array, and Pop
remove them from the same location.Last In，First Out
", that is:, LIFO
last in first out.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
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:
unshift
and pop
."Fist In，first out"
namely: FIFO
first in first out.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(); } }
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:
Advantages of linked lists:
Application scenarios of linked lists:
Linked lists are useful on both the client and the server.
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.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.The core operations of singly linked lists are:
push（value）
-Add a node at the end/head of the linked listpop（）
-Delete a node from the end/head of the linked listget（index）
-Return the node at the specified indexdelete（index）
-Delete the node at the specified indexisEmpty（）
-Return true or false according to the length of the listprint（）
-Return the visible representation of the linked listclass 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())
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.head = null; this.tail = null; } //Various operation methods //... }
Append & AppendAt
: Add a node at the end/specified position of the linked listappend( 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 listremove( 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 listreverse(){ 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 listtraverse( 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; }
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.
The common tree classification is as follows, among which we can master the binary search tree.
Binary Search Tree
AVL Tree
Red-Black Tree
Segment Tree
-with min/max/sum range queries examplesFenwick Tree
( Binary Indexed Tree
)DOM
tree. Every web page has a tree data structure.Vue
And React
is Virtual DOM
also a tree.BinarySearchTree
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:
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) {...} //...
insertNode
& insert
: Insert a new child node/nodeinsertNode(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) } }
removeNode
& remove
: Remove child nodes/nodesremoveNode(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) } }
findMinNode
.: Get the minimum value of the child nodefindMinNode(root) { if (!root.left) { return root } else { return this.findMinNode(root.left) } }
searchNode
& search
: Find child nodes/nodessearchNode(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)) } }
Pre-Order
: Preorder traversalpreOrder(root) { if (!root) { return'Tree is empty' } else { console.log(root.value) this.preOrder(root.left) this.preOrder(root.right) } }
In-Order
: Mid-order traversalinOrder(root) { if (!root) { return'Tree is empty' } else { this.inOrder(root.left) console.log(root.value) this.inOrder(root.right) } }
Post-Order
: Post-order traversalpostOrder(root) { if (!root) { return'Tree is empty' } else { this.postOrder(root.left) this.postOrder(root.right) console.log(root.value) } }
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
In the following scenarios, you have used graphs:
Google
Baidu.LBS
map services, such as high moral, Google Maps.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.Google
The search algorithm uses graphs to determine the relevance of search results.Graphs can be said to be one of the most widely used data structures. There are graphs everywhere in real scenes.
Diagrams are used to represent, find, analyze and optimize the connections between elements (houses, airports, locations, users, articles, etc.).
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
example, the direct connection between two stations in a subway station is an edge.|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
Graphs are classified according to the characteristics of their edges (connections).
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
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".
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 famous Dijkstra
algorithm is to use these weights by finding the shortest or optimal route between the nodes in the network to optimize routing.
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
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
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() {} }
addVertex
.: Add verticesaddVertex(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'] }
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`; } }
print
：Print the picture ( Graph
)print() { for (let [key, value] of this.AdjList) { console.log(key, value); } }
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:
BFS
algorithm .DFS
BFS
The focus on the queue, but DFS
the focus is recursive. This is their essential difference.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:
'A'
)visited
object: .q
the array will be used as a queue.（visited = {'A': true}）
（q = ['A']）
Inside the loop:
q
and store it in a variable.（let current = q.pop()）
current
current
edges. （let arr = this.AdjList.get(current)）
.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) } } } }
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:
dfs(startingNode)
.let visited = this.createVisitedObject()
.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.
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:
O(k)
, k is the length of the stringFor 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
You can use it whenever you want to match the prefix with a possible complete value Trie
.
In reality, it is mostly used in:
Can also be used in:
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() {} }
addWord
.: Create a nodeaddWord(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); }
predictWord
.: Predict the wordThat 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; }
logAllWords
.: Print all nodeslogAllWords() { console.log('------ all nodes in the dictionary tree-----------') console.log(this.predictWord('')); }
logAllWords
By calling on an empty string predictWord
to printTrie
all nodes.
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?
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
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]]]};
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 both examples, students and books are divided into a unique number.
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.
Specific steps are as follows:
O(1)
access the element time.The specific implementation is divided into two steps:
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
).
To achieve a good hashing mechanism, the following basic requirements are required:
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.
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.
O(n)
time (where n is the number of strings).How to optimize this hash function?
Pay attention to the similarities and differences of these strings
{"Abcdef", "bcdefa", "cdefab", "defabc"}
a，b，c，d，e
and f
composedLet's try different hash functions.
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).
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) {...} //... }
isPrime
.: Judgment of prime numbersisPrime( num) { for(let i = 2, s = Math.sqrt(num); i <= s; i++) if(num% i === 0) return false; return num !== 1; }
computeHash|findPrime
.: Hash function generationcomputeHash( 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; }
Put
.: Insert valueput( item) { let key = this.computeHash( item ); let node = new Node(item) if (this.table[key]) { node.next = this.table[key] } this.table[key] = node }
Remove
.: Delete valueremove( 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; } } } }
contains
.: Judgment containscontains(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; }
Size&IsEmpty
：Judging the length or emptysize( 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 }
Traverse
.: Traversetraverse( 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
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:
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!
huab119
454274033@qq.com
If you need to repost it to the official account, just call me to add the whitelist.