JavaScript data structure and algorithm (I)
Preface: This article mainly explains and discusses the common data structures in programming languages, and uses JavaScript for encapsulation, because as we all know, JavaScript is a weak type language, not only does not have type detection, but also some practical and efficient data structures such as stack and queue are not encapsulated, So let's talk about data structure.
1, Stack
- Stack is a first in and last out data structure, that is, if a data enters the container first, it can often be really taken out later.
- You can see that the Stack entry and Stack entry are the same channel, which leads to the phenomenon of first in and last out. Therefore, we can encapsulate a data structure that can only use push and pop methods based on an array. We take a more suitable name Stack
class Stack<T>{
private stack: Array<T> = []
constructor() {
this.stack = []
}
// Stack pressing
public push(element: T): Array<T> {
this.stack.push(element)
return this.stack
}
// Pop stack
public pop(): T | null {
if (!this.stack.length) return null
return this.stack.pop()
}
// Get stack top element
public getTop(): T {
return this.stack[this.stack.length - 1]
}
// Gets the length of the stack
public getSize(): number {
return this.stack.length
}
// Is it empty
public isEmpty(): boolean {
return this.stack.length === 0
}
}
- We use TS to simply encapsulate the stack. The stack has getSize, gettop, isempty, pop, push and other methods, which can and can only be used to operate the stack.
- Use it together!
2, Queue
- If you understand the stack, the queue is particularly easy to understand. This is a first in first out data structure. The event task queue of javascript is based on the data structure of queue.
- OK, I know the queue. Let's use a picture to describe it!
- The above is the graphical description of the Queue. It can be observed that the incoming Queue and the outgoing Queue are opposite, and the following principles are followed. The incoming Queue port cannot take elements, and the outgoing Queue port cannot add elements. No matter the stack or Queue, it is not allowed to insert elements from the middle. After understanding these principles, we continue to encapsulate the Queue based on JavaScript arrays, and then we take a nice name Queue
/ Encapsulate the queue
class Queue<T>{
private queue: Array<T> = []
constructor() {
this.queue = []
}
// Enter queue
public in(ele: T): Array<T> {
this.queue.push(ele)
return this.queue
}
// Out of queue
public out(): T {
return this.queue.shift()
}
// Get queue length
public getSize(): number {
return this.queue.length
}
// Is it empty
public isEmpty(): boolean {
return this.isEmpty.length === 0
}
public getFirst(): T {
return this.queue[0]
}
}
3, Hash table
- Before understanding the hash table, let's first understand a requirement. If we need to quickly find a data, for example, help me find Zhang San's phone, you can save let arr = ['15242536253', '15874585692']
- If you know in advance that Zhang San's phone has a subscript of 0, you can get the corresponding phone number directly through arr[0]. If so, that would be great, but the reality is cruel. In reality, it often won't be like this. We often don't know the subscript. We only know that we want to find Zhang San's phone, so we have to save and search in this way
let arr = [
{ name:'Zhang San' , tel: '15242536253' },
{ name:'Li Si' ,tel :'15874585692' }
]
function findTel(name){
return (arr.find(item=>item.name === name)).tel
}
let target = findTel('Zhang San')
- Did you find that, in fact, this search seems to be OK, but it seems not perfect, because it still needs to traverse, traverse each, and then find the one that matches. Can we find a structure that can input a Zhang San, and then help us find the phone number without any traversal! Some friends may react immediately. Then I can use objects, but now I want to tell you that objects cannot be used. As for the reasons, we will explain later, but now please remember that objects cannot be used, okay, Think about it at this time!
- Provide an idea. Since the array can find the corresponding elements immediately through the subscript, we may still be based on the array, which means that we need to convert strings like Zhang San into subscripts. I naively thought this TM was possible, but it's really possible!
- How? We need a function, which we call the hash function, This function can convert any string to a number (that is, subscript). We can require that the number must be in a certain range. If this function can be written, can we turn Zhang San into a subscript? When creating this array, we will put the phone number at the subscript generated by the hash function, so the process should be like this.
- When creating: Zhang San - hash function - > 2 - > [null, null, '15245236253']
- When searching: enter Zhang San -- > to obtain subscript 2 -- >
- Although this seems to be a good solution, the revolution has not been successful. Our hash function has not been written yet. How to write it!
- There is an idea that we can use that each character actually has a unique code. For example, each letter has its own unique code
Therefore, we can at least express any character as a numerical value. However, since the array position cannot be repeated, we must try our best to maintain the uniqueness of each generated numerical value. If we simply add it, it will not work, because it is too easy for multiple different characters to correspond to the same numerical value. In order to avoid this situation, We can use Horner's law.
let hashCode = 0
// Horner's law
for (var i = 0; i < string.length; i++) {
hashCode = 37 * hashCode + string.charCodeAt(i)
}
console.log(hashCode)
- Interested students can check this information, which will not be described in detail here. In short, this law can keep the hash Code generated by any character in one-to-one correspondence with the character as much as possible,
- But the problem is that the hash Code is too large. A lot of space saved in the array is wasted. What should we do? We can reduce it. That's the surplus
// Question: how to write this function
// All the text information is encoded into numbers, and then the large numbers are reduced by taking the remainder, and finally the smaller numbers are obtained.
// Design your own hash function
function hashFunc(string, size) {
let hashCode = 0
// Horner's law
for (var i = 0; i < string.length; i++) {
hashCode = 37 * hashCode + string.charCodeAt(i)
}
console.log(hashCode)
return hashCode % size
}
-
But even so, there will still be problems. No matter how hard we try, there will certainly be conflicts, that is, some different characters are mapped to the same position in the array. At this time, there will be a big topic, that is, conflict resolution!
-
In fact, there are many ways to solve conflicts, but here I introduce a common and easy to understand way, that is, the linked list method. In essence, we can understand it this way,
-
Although there are conflicts, the number of conflicts should be relatively small, so we can temporarily use a two-dimensional array to represent it, that is, a certain position of the main array also uses the array to store multiple conflicting elements, which have the same position.
-
This structure is called hash table (also called hash table)
-
It is said that facebook's database is stored in such a data structure. Have you found that in this way, we can directly map a character into a subscript position, so that the search speed will be very fast. Even in case of conflict, we only need to traverse the conflicting elements, Because a good hash table will make the whole hash table distributed evenly as much as possible and have as few conflicts as possible!
-
Let's look at arrays. If you really save a large number of arrays into arrays, it doesn't take a long time to traverse one by one, and it wastes performance.
-
It's time to answer why we don't use objects. Partners familiar with objects may know that it's easy to use objects to meet this requirement. Then why don't we use objects! Then I will tell you that javascript is actually based on the hash table to implement objects. All objects have such a search speed and do not need to search according to the subscript. In fact, it is also based on the hash table. So next, please remember that objects don't appear as they should!
It's time to implement the hash table! Cheer up and look at the code! Promise me to read it. If you have any questions, you can also send private letters and communicate together!
class HashTable {
constructor(size = 7) {
this.storage = []
this.size = size
this.count = 0
}
hashFunc(string, size) {
let hashCode = 0
// Horner's law
for (var i = 0; i < string.length; i++) {
hashCode = 37 * hashCode + string.charCodeAt(i)
}
return hashCode % size
}
put(key, value) {
let index = this.hashFunc(key, this.size)
if (!this.storage[index]) {
// Description is empty
let butket = [{ key, value }]
this.storage[index] = butket
this.count++
} else {
let obj = this.storage[index].find(ele => {
return ele.key == key
});
if (obj) {
obj.value = value
} else {
this.storage[index].push({ key, value })
this.count++
}
}
}
get(key) {
let index = this.hashFunc(key, this.size)
if (!this.storage[index]) {
return null
} else {
let obj = this.storage[index].find(ele => {
return ele.key == key
})
return obj ? obj : null
}
}
remove(key) {
if (!get(key)) {
return false
} else {
let index = this.storage[index].findIndex(ele => {
return ele.key == key
})
this.storage[index].splice(index, 1)
this.count--
return true
}
}
isEmpty() {
return this.count === 0
}
count() {
return this.count
}
// Capacity expansion
resize(newSize) {
let oldStorage = this.storage
this.storage = []
oldStorage.forEach(item => {
if (item && item.length > 0) {
item.forEach(e => {
this.put(e, key, e.value)
})
}
})
}
isPrime(num) {
for (var i = 2; i < num; i++) {
if (num % i === 0) {
return false
}
}
return true
}
getPrime(num) {
while (!this.isPrime(num)) {
num++
}
return num
}
}
Congratulations, after reading the hash table encapsulation, you can go to have a big meal and reward yourself!
4, Dictionary
- If I say that there is actually a dictionary data type in javascript, would you doubt it! In fact, there are. That is the Map type. In fact, there are dictionaries in many languages. The mapping relationship between standard key value pairs is still relatively simple. We don't encapsulate it. If you are interested, you must study the difference between Map and Object! This is still more important.
let map = new Map()
map.set('a' , 1)
map.get('a') // 1
5, Assemble
- In addition, there is another data type, which is very important. It represents a data type that will not be repeated, that is, set. Set is a special existence. He especially wants array, but it has a good feature that internal elements will never be repeated. In many languages, there is such a type in Javascript, that is, set. In order to understand its essence, let's encapsulate it!
class Set {
constructor() {
this.box = {}
this.length = 0
}
add(element) {
if (this.has(element)) {
return false
}
if (typeof element === 'object') {
let key = JSON.stringify(element)
this.box[key] = element
this.length++
} else {
this.box[element] = element
this.length++
}
}
has(element) {
if (typeof element === 'object') {
let key = JSON.stringify(element)
return this.box.hasOwnProperty(key)
} else {
return this.box.hasOwnProperty(element + '')
}
}
values() {
let values = []
for (var key in this.box) {
values.push(this.box[key])
}
return values
}
clone() {
let copy = new Set()
for (var key in this.box) {
copy.add(this.box[key])
}
return copy
}
clear() {
this.box = {}
}
size() {
return this.length
}
isEmpty() {
return this.length === 0
}
remove(element) {
if (!this.has(element)) {
return null
} else {
element = typeof element === 'object' ? JSON.stringify(element) : element
delete this.box[element]
}
}
union(set) {
// Just understand and find the union
if (!(set instanceof Set)) {
return console.warn('no Set type')
} else {
let copy = this.clone()
for (var key in set.box) {
copy.add(set.box[key])
}
return copy
}
}
intersection(set) {
// Understand and find the intersection
if (!(set instanceof Set)) {
return console.warn('no Set type')
} else {
let newset = new Set()
let resorse = set.box
for (var key in resorse) {
if (this.has(resorse[key])) {
newset.add(resorse[key])
}
}
return newset
}
}
diff(set) {
// Just understand and find the difference set
let copy = this.clone()
let intersection = this.intersection(set)
for (var key in intersection.box) {
copy.remove(intersection.box[key])
}
return copy
}
childOf(set) {
if (set.length < this.length) {
return false
} else {
return this.values().every(item => {
return set.has(item)
})
}
}
}
6, Linked list
- Next is a very good topic. I suggest you look at it when you are full!
- What is a linked list? It is like a train. Each element has at least two attributes. One attribute holds the current value and the other holds the reference to the next element. In this way, the string by string data structure composed of elements is a linked list! Last picture, feel it!
How about seconds? Yes, this is the linked list, but the above is actually a one-way linked list, that is, the previous node can point to the next node, but the next node does not point to the previous node. If the next node can point to the previous node, a two-way linked list is formed!
- After understanding the classification of linked lists, we will start encapsulation. It is worth noting that at this time, we are not based on arrays. We want to create a new data structure. We give this class a nice name List
class Node {
constructor(value, next) {
this.value = value
this.next = next
}
next() {
console.log('asdf')
return this.next.value
}
}
class List {
constructor() {
this.length = 0
this.head = null
}
// a b c d e f
append(element) {
const newNode = new Node(element, null)
this.length++
if (!this.head) {
this.head = newNode
} else {
//
let current = this.head
while (current.next) {
current = current.next
}
current.next = newNode
}
return this
}
toString() {
let str = ''
let current = this.head
while (current.next) {
str += current.value + "-"
current = current.next
}
str += current.value
return str
}
insert(position, element) {
if (this.length === 0) {
this.head = element
} else {
if (position > this.length || position < 0) {
return false
} else {
const newNode = new Node(element, null)
let current = null
let tmp = ''
for (var i = 0; i < position; i++) {
current = this.head.next
}
tmp = current.next
current.next = newNode
newNode.next = tmp
}
}
this.length++
}
get(position = 0) {
if (position > this.length || position < 0) {
return null
}
let current = this.head
for (var i = 0; i < position; i++) {
current = current.next
}
return current
}
indexOf(element) {
let index = 0
let current = this.head
for (var i = 0; i < this.length; i++) {
if (element === current.value) {
return index
}
current = current.next
index++
}
return -1
}
update(position, element) {
if (position > this.length || position < 0) {
return false
} else {
let current = this.head
let prev = null
for (var i = 0; i < position; i++) {
prev = current
current = current.next
}
const newNode = new Node(element, current.next)
prev.next = newNode
}
}
removeAt(position) {
if (position > this.length || position < 0) {
return null
} else if (position === 0) {
this.head = this.head.next
} else {
let current = this.head
let prev = null
for (var i = 0; i < position; i++) {
prev = current
current = current.next
}
prev.next = current.next
this.length--
return current
}
}
remove(element) {
this.length--
let index = this.indexOf(element)
return this.removeAt(index)
}
isEmpty() {
return this.length === 0
}
size() {
return this.length
}
}
-
In this way, we can also use linked lists in javascript in the future. Some friends have questions. Don't we already have arrays? Why do we have linked lists? Why do we do so many fancy things! Yes, I also had this question before. In fact, from the perspective of function, as long as the linked list can do it, the array can also do it. However, one thing we need to pay attention to is that they may consume different performance when dealing with the same business demand scenario. That's why we need to study it.
-
At present, we can conclude that linked lists are more suitable for insert and delete operations, especially inserting elements in the middle. Because the linked list only needs to change the pointer.
-
Arrays are more suitable for finding operations based on subscripts, so you don't have to traverse. However, the linked list needs to traverse one by one from the first to find any element.