如何判断一个js对象是否存在循环引用
这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助
一、背景
在前端JSON.stringfy
是我们常用的一个方法,可以将一个对象序列化。 例如将如下对象序列化
const person = { name: 'kalory', age:18} JSON.stringfy(person) // 结果 '{"name":"kalory","age":18}' 将一个数组序列化 const arr = [1,2,3,4,5] // 结果 '[1,2,3,4,5]' const persons = [{ name: 'kalory', age:18},{ name: 'jack', age:48}] // 结果 '[{"name":"kalory","age":18},{"name":"jack","age":48}]'
我们发现上面对象是可以使用JSON.stringfy序列化的。
- 但是如果一个对象存在循环引用,序列化会报错,如下
person
对象的owner
属性指向了自己,存在循环引用
const person = { name: 'kalory', age:18} person.onwer = person
我们对上面这个对象进行JSON.stringfy,结果如下,会报错:
我们发现他说不能转化一个“圈结构体为JSON”,是因为这个对象的owner属性指向了自己。在转化的时候会变成死循环。
- 那么我们如果判断一个对象有没有环呢?
二、实现
2.1 思路
我们判断一个对象有没有循环引用,我们其实并不需要在乎对象的key是什么,只需要判断对象的value
。如果value
是引用数据类型的时候,有没有指向对象的某一值。
所以我们可以先使用Object.values()
拿到对象所有values
,然后定义一个cache
变量用来存储values
中的引用数据类型,然后遍历values
。
如果cache
中存在,那么说明这个对象有环 return true
,如果不存在并且是引用数据类型,那么我们就加入cache。当values
遍历完都没有reutrn
那么说明没有环return false
2.2 递归实现
function existCircular(obj) { let cache = new Set(); function helper(obj) { let values = Object.values(obj); for (let i = 0; i < values.length; i++) { if (cache.has(values[i])) { return true; } // 不是引用数据类型,直接跳过 if(typeof values[i] !== 'object' || values[i] === null) continue cache.add(values[i]); let flag = helper(values[i]); // 如果 flag 是 false, 那么继续遍历,如果是 true,说明已经存在环了, 直接 return true if (flag) { return true; } } return false; } return helper(obj); } // 测试 const person = { name: 'kalory', age:18} person.onwer = person existCircular(person) // true
2.3 BFS实现
const existCircularBFS = (obj) => { let cache = new Set(); let values = [obj]; while(values.length) { const item = values.shift() if (cache.has(item)) { return true; } // 基本数据类型跳过 if(typeof item !== 'object' || item === null) continue cache.add(item); // 主要这里 Object.values 拿到的是一个数组,我们需要展开push到values // 如果直接 push Object.values(item) 会造成死循话 values.push(...Object.values(item)) } return false; }