Write a Better Deep Clone Function in JavaScript

When your interviewers ask you this question, they actually want to examine your following knowledge.

bitfish
bitfish
Jan 21 · 9 min read
Image for post
Image for post
Photo by Shahadat Rahman on Unsplash

There are many articles about deep clone on the Internet, but to be honest, as an interviewer, I think many code implementations are not qualified. Now I’ll show you how to answer this question from the perspective of the interviewer.

Ask yourself three questions before reading this:

  • Do you really understand what does deep clone means?
  • In the eyes of the interviewer, what kind of deep clone function is qualified?
  • How to write a better deep clone function?

This article takes you step-by-step through the process of creating a better deep clone function.

Definition of deep clone and shallow clone

Although deep clone has been discussed many times, many readers are still not familiar with the concept, so I will introduce it again.

Shallow clone duplicate as little as possible. A shallow clone of a collection is a copy of the collection structure, not the elements. With a shallow clone, two collections now share the individual elements.

Deep clone duplicates everything. A deep clone of a collection is two collections with all of the elements in the original collection duplicated.

Shallow clone:

Image for post
Image for post

Deep Clone:

Image for post
Image for post

Now let’s cut to the chase:

Beggar’s version

Without using a third-party library, the most common way we want to copy an object deeply is by using this method.

JSON.parse(JSON.stringify(target));

This approach is very simple and can be used in most applications, but it still has some drawbacks, such as copy functions, circular references, and so on.

Obviously, you can’t pass the interview by simply saying that. Next, let’s manually implement a deep copy function.

Basic version

If it’s a shallow clone, we can easily write the following code:

Creates a new object, traverses through the target object to be cloned, then adds the properties of the target object to be cloned, and returns.

If it’s a deep clone, we can use recursion to solve the problem and rewrite the code a little bit, considering that the target object we’re copying has no idea how deep it is:

  • If it is of the primitive data type, no further copy is required and we can return it directly
  • If it is a reference type, then we can create a new object, traverse the target object that needs to be cloned, and add the properties of the target object that needs to be cloned to the new object in turn after performing a deep copy

It’s easy to understand that if there are deeper objects that can be recursed until the property is of the original type, then we’re done with a simple deep copy:

Then we can test this function.

const target = {
field1: 1,
field2: undefined,
field3: 'value',
field4: {
child: 'child',
child2: {
child2: 'child2'
}
}
};
Image for post
Image for post

This is a deep copy of the most basic version of the code that allows you to show the interviewer that you can solve the problem recursively. But clearly it has a lot of flaws, such as not considering arrays.

Consider Arrays

In the previous version, we only considered normal objects for our initialization, so we just need to change the initialization code a little bit to make it compatible with arrays:

Then add a new test.

const target = {
field1: 1,
field2: undefined,
field3: {
child: 'child'
},
field4: [2, 4, 8]
};
Image for post
Image for post

Okay, no problem. Our code is one small step closer to great.

Circular reference

If we perform the following test case:

const target2 = {
field1: 1,
field2: undefined,
field3: {
child: 'child'
},
field4: [2, 4, 8]
};
target2.target2 = target2;

You can see the following results:

Image for post
Image for post

Obviously, a stack memory overflow is caused by recursion into an infinite loop.

The reason for this is that the object above has a circular reference, in which the properties of the object refer directly or indirectly to itself:

Image for post
Image for post

To solve the circular reference problem, we can create an extra storage space to store the relationship between the current object and the copied objects. When we need to copy the current object, we first go to the storage space to find out if we have copied this object, return if yes, and continue copying if no, this deftly resolves the circular reference problem.

This storage space, need to be able to store data in the form of key-value, and the key can be a reference type, so we can choose Map.

To execute the test case above:

Image for post
Image for post

As you can see, execution is error-free.

Improve code by WeakMap

Next, we can use a WeakMap instead of Map to make code better.

function clone(target, map = new WeakMap()) {
// ...
};

Why would we do that? Here’s what WeakMap does:

The WeakMap object is a collection of key/value pairs in which the keys are weakly referenced. The keys must be objects and the values can be arbitrary values.

Then what is a weak reference?

In computer programming, a weak reference is a reference that does not protect the referenced object from collection by a garbage collector, unlike a strong reference. An object referenced only by weak references — meaning “every chain of references that reaches the object includes at least one weak reference as a link” — is considered weakly reachable, and can be treated as unreachable and so may be collected at any time. Some garbage-collected languages feature or support various levels of weak references, such as C#, Java, Lisp, OCaml, Perl, Python and PHP since the version.

When we create an object by const obj = {}, which creates a strongly referenced object by default. And we have to manually put obj = null in order for it to be released by the garbage collection mechanism. But if it’s a weakly referenced object, the garbage collection mechanism will automatically help us release it.

For example: If we use a Map, then there is a strong reference relationship between objects:

let obj = { name : 'Jon Snow'}const target = new Map();target.set(obj,'a man from Game of Thrones');obj = null;

Even though we manually releasedobj, target still has a strong reference to obj, so its memory can not be released.

And we can switch it to WeakMap:

let obj = { name : 'Jon Snow'}const target = new WeakMap();target.set(obj,'a man from Game of Thrones');obj = null;

If it is a WeakMap, target and obj have a weak reference relationship. obj will be free up in the next time the garbage collection mechanism is executed.

Imagine that if we were copying a very large object, using Map would cause a very large memory drain, and we would need to manually clear the Map’s properties to free that memory and WeakMap will help us finesse that problem.

Before, many people didn’t understand what WeakMap and weak reference means. Through this example, I hope to help you understand the above two concepts.

To be able to think about circular references, you’ve shown the interviewer that you’re thinking about the whole thing. And if you can solve the problem with a WeakMap, and clearly explain to the interviewer why you’re doing it, then your code should be qualified in the eyes of the interviewer.

Performance optimization

In the code above, we use for in to iterate through arrays and objects. In fact, for in is very inefficient when traversing. Let’s compare the performance of the three common loops for, while, and for in:

Image for post
Image for post

As you can see, while works best, so we can figure out a way to change the for in traversal to a while traversal.

First, let’s use while to implement a tool function that can traverse arrays.

function forEach(array, iteratee) {
let index = -1;
const length = array.length;
while (++index < length) {
iteratee(array[index], index);
}
return array;
}

This function takes two parameters, one is an array, and the other is a callback function that processes the elements in the array. And the callback function receives two parameters: value and index.

Next, rewrite our clone function: when traversing an array, use forEach to directly traverse it; when traversing an object, use Object.keys to retrieve all the keys of the object for traversal:

And we can make a performance test:

const target = {
field1: 1,
field2: undefined,
field3: {
child: 'child'
},
field4: [2, 4, 8],
f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: {} } } } } } } } } } } },
};
target.target = target;console.time();
const result = clone1(target);
console.timeEnd();
console.time();
const result2 = clone2(target);
console.timeEnd();

(In order to avoid your misunderstanding and make it convenient for you to copy the code, I wrote the relevant functions again.)

Results:

Image for post
Image for post

Obviously, our performance optimizations are effective.

Other data types

In the above code, we have only considered the normal objects and array objects, and in fact, all the reference types are far more than these two.

An object may be an array, function, map, etc. They are different when we try to deep clone. If we want to get the specific type of object, what should we do?

The ECMAScript has the following rules:

Image for post
Image for post
From EcmaScript

For different objects, different results will be returned when calling Object.prototype.toString.

Image for post
Image for post
From Chrome‘s Console
Image for post
Image for post

Moreover, the return value of Object.prototype.toString() is always in the format of ‘[object + ‘tag +‘] ’. If we only want the middle tag, We can delete characters on both sides by regular expression or String.prototype.slice().

So we can write this function:

For any specific types, we simply divide them into two categories:

  • Types that can continue traversing, such as Map, Set.
  • Types that can not continue traversing, such as Functions.

We should write different code for them.

Types that can continue traversing

Normal objects and array objects are data types that can be traversed continuously. We have talked about them before. In addition, Map and Set can continue to traverse. We will only discuss these four situations here. As for other situations, you can explore by yourself.

The traversal of Map and Set are very simple. They both provide the forEach method to traverse. So we just need to modify the previous code little.

For convenience, I also wrote the test case in the above code, and the following is the running result of the above code.

Image for post
Image for post

Types that can not continue traversing

Other data types, such as Boolean, Number, String, Date, and Error, are not traversable by themselves, so we can directly use their constructors and raw data to create a new object.

Conclusion

Here is the final code and test:

Image for post
Image for post

As you can see, there is much hidden knowledge in deep clone. Only when you think deeply and comprehensively can you stand out from many interviewers.

JavaScript In Plain English

New JavaScript + Web Development articles every day.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store