This series also does not have any tricks, is to complete the usual interview some handwriting functions, test these simple implementation of the advantage is that you can see the basic coding level, and take a short time, a more comprehensive view of your code strength. Generally, there are not many boundary conditions, so that the interview time is not enough, the investigation is not comprehensive.

If you don’t know or are not clear about the API, just ask the interviewer directly, how to use the API under Google anyone can immediately understand the knowledge also can’t see the level. The key is in the implementation process, and your coding status, habits, clarity of thought and so on.

Note that it is a simple implementation, not a complete implementation. It is important to have clear concepts and clear implementation ideas. It is recommended to write pseudo-code first, and then implement specific functions.

Before we write these two scripts, we need to understand what is a shallow copy and a deep copy, and what is the difference between them.

Again, you need to start with the more basic distinction between base and reference types

Variable types in JS are divided into basic types and reference types. Object values store reference addresses, so different from the immutable property of basic type values, object values are mutable. And they are stored in different locations, base type value => stack memory, reference type => in both stack memory and heap memory

The stack memory holds the variable identifier and pointer to the object in the heap memory, or the address of the object in the heap memory.

Deep copy and shallow copy differ by reference type.

  • Shallow copy: Creates a new object with an exact copy of the original object property values. If the property isBasic types ofThe copy isBasic typevalueIf the property isReference typesThe copy isMemory address, soIf one object changes this address, it affects the other object.
A shallow copy a reference type directly refer to the same address Mutual influence obj [String] [Number] [Object] [Array] | | | | | copy | | heap area address 1 heap area 2 | | | | | cloneObj [String] [Number] [Object] [Object]Copy the code
  • Deep copy: To make a full copy of an object out of memory, clearing one out of heap memoryThe new memory location holds the new object, so new and old objectsEach other.
Create a new address deep copy a reference type pile area Each other obj [String] [Number] [Object] [Array] | | | | | copy | | heap area address 1 heap area 2 | | | cloneObj [String] [Number] [Object] [Object] (stack area directly deposit value) | | heap area address 3 pile zone 4Copy the code

Once you understand the concept clearly and accurately, you can start implementing it.

6. ShallowClone

Simple handwriting implementation

implementation

Shallow copy is very simple, in fact

const a = {
  b: 'b1'.c: {
      c1: 100}},function shallowClone(source) {
    const target = {};
    for (const i in source) {
        if(source.hasOwnProperty(i)) { target[i] = source[i]; }}return target;
}

const sCopyA = shallowClone(a);

sCopyA.b = 'b2'
sCopyA.c.c1 = 'change';

console.log(a)      // { b: 'b1', c: { c1: 'change' } }
console.log(sCopyA) // { b: 'b2', c: { c1: 'change' } }
Copy the code

We can see that the c property refers to the same memory address in both objects, and it affects each other.

7. DeepClone

Simple handwriting implementation

Deep copy is simply shallow copy + recursion

const a = {
  b: 'b1'.c: {
      c1: 100}},function deepClone(source) {
    var target = {};
    for(var i in source) {
        if (source.hasOwnProperty(i)) {
            if (typeof source[i] === 'object') {
                // Continue recursion if it is still an object (reference type)
                target[i] = deepClone(source[i]);
            } else{ target[i] = source[i]; }}}return target;
}

const dCopyA = deepClone(a);

dCopyA.b = 'b2'
dCopyA.c.c1 = 'change';

console.log(a)      // { b: 'b1', c: { c1: 100 } }
console.log(dCopyA) // { b: 'b2', c: { c1: 'change' } }
Copy the code

Add a reduce notation

var a = {
    a1: 1.a2: {
        b1: 1.b2: {
            c1: 1}}}let isObject = (target) = > {
    return Object.prototype.toString.call(target) === '[object Object]'
}

let deepCloneReduce = (source) = > {
    // Object.keys does not contain properties on the prototype chain
    const keys = Object.keys(source)
    return keys.reduce((acc, cur) = > {
        const value = source[cur]
        if (isObject(value)) {
            return {
                ...acc,
                [cur]: deepCloneReduce(value)
            }
        } else {
            return {
                ...acc,
                [cur]: value
            }
        }
    }, {})
}

let b = deepCloneReduce(a)
b.a1 = 8
b.a2.b1 = 'change1'
b.a2.b2.c1 = 'change2'

console.log(a)   // { a1: 1, a2: { b1: 1, b2: { c1: 1 } } }
console.log(b)   // { a1: 8, a2: { b1: 'change1', b2: { c1: 'change2' } } }
Copy the code

In-depth discussion

But is it really that simple? If we’re on our way to becoming an expert, we need to think a little bit more and tell the interviewer that there are a lot of problems with this approach before they even ask you. Show how much thought you’ve put into the question.

This is zhihu on the deep copy implementation of a discussion can be interested in understanding

Let me just list a few

  • Parameter is not checked, returns if it is not an object.
  • typeofDetermine if the object’s logic is not rigorous enough
  • Lack ofFunction, Array, Set, Map, WeakSet, WeakMapSuch as compatible
  • A circular reference
  • Reference is missing
  • Recursive overstack overflow
  • Performance issues with large (width, depth) data
  • .

We’ll just go over the first couple of little things

Check whether object, compatible array

var a = {
    a1: 1.a2: {
        b1: 1.b2: {
            c1: 1}},a3: [1.2.3]}let isObject = (target) = > {
    return Object.prototype.toString.call(target) === '[object Object]'
}

function deepClone(source) {
    // Check parameters
    if(! isObject(source)) {return source;
    }
    // Determine array type initialization
    let target = Array.isArray(source) ? [] : {};

    for(let key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = deepClone(source[key]); // Notice here
            } else{ target[key] = source[key]; }}}return target;
}

let b = deepClone(a)

console.log(a)  // { a1: 1, a2: { b1: 1, b2: { c1: 1 } }, a3: [ 1, 2, 3 ] }
console.log(b)  // { a1: 1, a2: { b1: 1, b2: { c1: 1 } }, a3: [ 1, 2, 3 ] }
Copy the code

Let’s pick a few key points to discuss

Excessive stack overflow

Let’s first discuss how to avoid the problem of stack overflow, also known as stack burst. This is mainly due to recursive writing, so if you use iterative writing, this problem will not be solved.

In fact, it is a variant of the iterative implementation of binary tree traversal, not binary, using a stack to complete traversal, in fact, recursive problems can be achieved by stack + iteration.

var a = {
    a1: 1.a2: {
        b1: 1.b2: {
            c1: 1}}}// This method is more accurate
let isObject = (target) = > {
    return Object.prototype.toString.call(target) === '[object Object]'
}

// The iterative deepClone method is actually a tree traversal
let deepCloneIteration = (source) = > {
    // Check the parameters
    if(! isObject(source)) {return source
    }

    let root = {}

    const stack = []
    // Start node root with children as source
    // Then assign the value directly to the element if the initial judgment is root
    stack.push({
        parent: root,
        keyName: 'root'.children: source
    })

    while (stack.length > 0) {
        // Push out the top element
        let curNode = stack.pop()
        // Lists the parent, keyName, and child nodes of the current node
        let parent = curNode.parent
        let keyName = curNode.keyName
        let children = curNode.children

        // Initialize the assignment target
        let target = {};
        if (keyName === 'root') {
            // If keyName is root, copy it directly to the parent element
            target = parent
        } else {
            // Otherwise copy to children corresponding to keyName
            target = parent[keyName] = {};
        }
        // Let's iterate through its children
        for(let k in children) {
            if (children.hasOwnProperty(k)) {
                // If the child is an object, it is pushed into the next loop, otherwise it is directly assigned
                if (isObject(children[k])) {
                    stack.push({
                        parent: target,
                        keyName: k,
                        children: children[k]
                    })
                } else {
                    target[k] = children[k]
                }
            }
        }
    }

    return root
}

let b = deepCloneIteration(a)
b.a1 = 8
b.a2.b1 = 'change1'
b.a2.b2.c1 = 'change2'

console.log(a)   // { a1: 1, a2: { b1: 1, b2: { c1: 1 } } }
console.log(b)   // { a1: 8, a2: { b1: 'change1', b2: { c1: 'change2' } } }
Copy the code

With iterative deepClone, there is no recursive deep-stack overflow problem.

Circular reference problem

The following is the circular reference problem, first a brief explanation of circular reference

let a = {}
a.a = a

console.log(deepClone(a)) // RangeError: Maximum call stack size exceeded
Copy the code

This is a circular reference, which simply means that an object’s attributes refer to itself indirectly or directly, and as long as the reference is looped, it will never be duplicated.

A little bit more about lost references

let ref = {r: 1};
let a = {a1: ref, a2: ref};
let c = JSON.parse(JSON.stringify(a));

console.log(a.a1 === a.a2) // true
console.log(c.a1 === c.a2) // false

// After copying, when ref changes, a1 and A2 references do not point to the same place, so they do not change
a.a1.r = 100
c.a1.r = 100
console.log(a) // { a1: { r: 100 }, a2: { r: 100 } }
console.log(c) // { a1: { r: 100 }, a2: { r: 1 } }
Copy the code

Note that it’s not that it’s wrong to lose a reference, but it depends on the requirements, sometimes it’s necessary to keep a reference, sometimes it’s not necessary to keep a reference, most things are not binary problems, but multiple problems, the world is not black and white, it’s constantly changing.

Another JSON. Parse (JSON. Stringify ()); This method is usually used to determine the format of the data is good, using tools to solve the problem quickly, but also can do loop detection. Clone does not clone the function pointer inside the clone object, where the function is not copied.

The solution is cyclic detection. You can set up an array or hash table to store objects that have been copied. When detecting that the current object exists, you can fetch the value and return it.

let isObject = (target) = > {
    return Object.prototype.toString.call(target) === '[object Object]'
}

// Array, Map, WeakMap are ok
function deepClone(source, hash = new WeakMap(a)) {

    if(! isObject(source)) {return source; 
    }
    
    // If the object already exists, return it
    if (hash.has(source)) {
        return hash.get(source);
    }
    
    var target = Array.isArray(source) ? [] : {};
    // Otherwise save it in the hashmap
    hash.set(source, target);
    
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                // Pass the hash table recursively
                target[key] = deepClone(source[key], hash);
            } else{ target[key] = source[key]; }}}return target;
}

// Circular reference resolution
let a = {}
a.a = a

let b = deepClone(a)

console.log(a) // { a: [Circular] } 
console.log(b) // { a: [Circular] }

// Reference loss resolved
let ref = {r: 1};
let d = {a1: ref, a2: ref};
let e = deepClone(d)

console.log(e.a1 === e.a2) // true
Copy the code

If WeakMap is selected, it is recommended to understand the difference between strong and weak references.

MDN WeakMap In contrast, WeakMap holds a “weak reference” to each key object, which means garbage collection works correctly when no other reference exists. The structure of the native WeakMap is special and efficient, and the key it uses for mapping is valid only if it is not reclaimed.

Other ways: Circular-JSON-ES6 is a library that addresses circular references

Lodash’s cloneDeep can also be used directly in projects, saving time and effort.

This series is not suitable to write too much, too detailed, do not write, may be later on [core concepts].

Off-topic: When I was writing this article, I somehow remembered a previous project of satellite fault analysis system. I suddenly missed staying up late to develop and solve various situations of complex data problems with my friends. I am very happy to meet you ^-^, and WE will see you in the future

In addition, we recommend another series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithms disassembly series remember to like ha

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference

  • Yanhaijing.com/javascript/…
  • www.zhihu.com/question/47…
  • Lodash.com/docs#cloneD…
  • Github.com/yyx990803/c…
  • Juejin. Cn/post / 684490…
  • Juejin. Cn/post / 684490…