Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JavaScript 中是如何比较两个元素是否 "相同" 的 #5

Open
lessfish opened this issue May 25, 2016 · 46 comments
Open

JavaScript 中是如何比较两个元素是否 "相同" 的 #5

lessfish opened this issue May 25, 2016 · 46 comments

Comments

@lessfish
Copy link
Owner

Why underscore

最近开始看 underscore.js 源码,并将 underscore.js 源码解读 放在了我的 2016 计划中。

阅读一些著名框架类库的源码,就好像和一个个大师对话,你会学到很多。为什么是 underscore?最主要的原因是 underscore 简短精悍(约 1.5k 行),封装了 100 多个有用的方法,耦合度低,非常适合逐个方法阅读,适合楼主这样的 JavaScript 初学者。从中,你不仅可以学到用 void 0 代替 undefined 避免 undefined 被重写等一些小技巧 ,也可以学到变量类型判断、函数节流&函数去抖等常用的方法,还可以学到很多浏览器兼容的 hack,更可以学到作者的整体设计思路以及 API 设计的原理(向后兼容)。

之后楼主会写一系列的文章跟大家分享在源码阅读中学习到的知识。

欢迎围观~ (如果有兴趣,欢迎 star & watch~)您的关注是楼主继续写作的动力

_.isEqual

本文跟大家聊聊 JavaScript 中如何判断两个参数 "相同",即 underscore 源码中的 _.isEqual 方法。这个方法可以说是 underscore 源码中实现最复杂的方法(用了百来行),几乎没有之一。

那么,我说的 "相同" 到底是什么意思?举个栗子,1new Number(1) 被认为是 equal,[1][1] 被认为是 equal(尽管它们的引用并不相同),当然,两个引用相同的对象肯定是 equal 的了。

那么,如何设计这个 _.isEqual 函数呢?我们跟着 underscore 源码,一步步来看它的实现。后文中均假设比较的两个参数为 a 和 b。

首先我们判断 a === b,为 true 的情况有两种,其一是 a 和 b 都是基本类型,那么就是两个基本类型的值相同,其二就是两个引用类型,那么就是引用类型的引用相同。那么如果 a === b 为 true,是否就是说 a 和 b 是 equal 的呢?事实上,99% 的情况是这样的,还得考虑 0 和 -0 这个 special case,0 === -0 为 true,而 0 和 -0 被认为是 unequal,至于原因,可以参考 http://wiki.ecmascript.org/doku.php?id=harmony:egal。

这部分代码可以这样表示:

// Identical objects are equal. `0 === -0`, but they aren't identical.
// See the [Harmony `egal` proposal](http://wiki.ecmascript.org/doku.php?id=harmony:egal).
// a === b 时
// 需要注意 `0 === -0` 这个 special case
// 0 和 -0 不相同
// 至于原因可以参考上面的链接
if (a === b) return a !== 0 || 1 / a === 1 / b;

接下去的情况,也就是 a !== b 的情况了。

如果 a 和 b 中有一个是 null 或者 undefined,那么可以特判下,不用继续比较了。源码实现:

// A strict comparison is necessary because `null == undefined`.
// 如果 a 和 b 有一个为 null(或者 undefined)
// 判断 a === b
if (a == null || b == null) return a === b;

个人觉得这里写的有点多余,因为根据上面的判断过滤,a === b 肯定是返回 false 的。

ok,我们继续,接下来我们可以先根据 a 和 b 的类型来判断,如果类型不一样,那么就没必要继续判断了。如何获取变量类型?没错,就是神奇的 Object.prototype.toString.call

如果类型是 RegExp 和 String,我们可以将 a 和 b 分别转为字符串进行比较(如果是 String 就已经是字符串了),举个栗子:

var a = /a/;
var b = new RegExp("a");

console.log(_.isEqual(a, b));  // => true

其实它在 underscore 内部是这样判断的:

var a = /a/;
var b = new RegExp("a");

var _a = '' + a; // => /a/
var _b = '' + b; // => /a/

console.log(_a === _b); // => true

如果是 Number 类型呢?这里又有个 special case,就是 NaN!这里规定,NaN 仅和 NaN 相同,与别的 Number 类型均 unequal。这里我们将引用类型均转为基本类型,看如下代码:

var a = new Number(1);
console.log(+a); // 1

没错,加个 + 就解决了,其他的不难理解,都在注释里了。

// `NaN`s are equivalent, but non-reflexive.
// Object(NaN) is equivalent to NaN
// 如果 +a !== +a 
// 那么 a 就是 NaN
// 判断 b 是否也是 NaN 即可
if (+a !== +a) return +b !== +b;

// An `egal` comparison is performed for other numeric values.
// 排除了 NaN 干扰
// 还要考虑 0 的干扰
// 用 +a 将 Number() 形式转为基本类型
// 如果 a 为 0,判断 1 / +a === 1 / b
// 否则判断 +a === +b
return +a === 0 ? 1 / +a === 1 / b : +a === +b;

// 如果 a 为 Number 类型
// 要注意 NaN 这个 special number
// NaN 和 NaN 被认为 equal

接下来我们看 Date 和 Boolean 两个类型。跟 Number 类型相似,它们也可以用 + 转化为基本类型的数字!看下面代码:

var a = new Date();
var b = true;
var c = new Boolean(false);

console.log(+a); // 1464180857222
console.log(+b); // 1
console.log(+c); // 0

非常简单,其实 +new Date() (或者也可以写成 +new Date)获取的正是当前时间和 1970 年 1 月 1 日 0 点的毫秒数(millisecond),可能你听说过时间戳,其实时间戳就是这个数据除以 1000,也就是秒数。在用 canvas 做动画时,我经常用 +new Date 来当时间戳。

so,如果 a 和 b 均是 Date 类型或者 Boolean 类型,我们可以用 +a === +b 来判断是否 equal。

程序接着走,我们接着看,似乎还有两类重要的类型没有判断?没错,Array 和 Object!underscore 对此采用递归方法展开来比较。

还是举个栗子吧,举例比较直观。

假设 a,b 如下:

var a = {name: "hanzichi", loveCity: [{cityName: "hangzhou", province: "zhenjiang"}], age: 30};
var b = {name: "hanzichi", loveCity: [{cityName: "hangzhou", province: "zhenjiang"}], age: 25};

首先 a,b 是对象,我们可以分别比较其键值对,如果有一个键值对不同(或者说一个键值对 a 和 b 有一个没有),则 a 和 b unequal。如果是数组呢?那就一个一个元素比较喽。因为数组可能嵌套对象,对象的 value 又可能是数组,所以这里用了递归。

还是以上面的例子,我们可以把它拆成三次比较,分别比较三个 key 的 value 值是否相同。对于 loveCity 这个 key 的 value,因为其 value 又是个数组,所以我们将这个 value 传入比较函数,通过这个比较的结果,来判断最后的比较结果。递归就是这样,可以将大的东西,拆成一个个小的,根据小的结果,来汇总得到大的结果。

最后,给出代码位置。关于 _.isEqual 方法的源码,大家可以参考 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L1094-L1190

@mercer08
Copy link

mercer08 commented May 31, 2016

var a =1,b=2;
if (a === b) return a !== 0 || 1 / a === 1 / b;

上面代码在chrome中报错,报错信息

VM546:1 Uncaught SyntaxError: Illegal return statement(…)

我放在jshint里试一下没有报语法错误啊,还望指点一下

@lengxing
Copy link

@2lei return 只能在function内部有效

@lessfish
Copy link
Owner Author

楼上正解~

@EdwardZZZ
Copy link

if (a == null || b == null) return a === b;
个人觉得这里写的有点多余,因为根据上面的判断过滤,a === b 肯定是返回 false 的。

如果a == null && b == null , a === b 返回是true吧?

@lessfish
Copy link
Owner Author

lessfish commented Jun 8, 2016

@EdwardZZZ a,b 都为 null,那就直接执行 if (a === b) return a !== 0 || 1 / a === 1 / b; 了吧?

@EdwardZZZ
Copy link

@hanzichi 对,看断片了,忘记前面的了

@zhanyuzhang
Copy link

zhanyuzhang commented Jun 15, 2016

源码中有这么一段:if (typeof a != 'object' || typeof b != 'object') return false;,就是说如果a和b都是函数类型就直接返回false?但是个人觉得两个函数也可以有相等的情况啊!

@lessfish
Copy link
Owner Author

@zhanyuzhang 看源码的确是这样,个人觉得比较两个函数是否相等没啥实用价值,可能设计的时候就忽略掉了

@NeilZhou00
Copy link

@zhanyuzhang 如果a或是b是Function的话,typeof出来的结果是‘function’,不是'object'。

@qingzhu1224
Copy link

f (a == null || b == null) return a === b;
个人觉得这里写的有点多余,因为根据上面的判断过滤,a === b 肯定是返回 false 的。

这个应该不是多余的,a===b确实返回是false,但是不能执行“if (a === b) return a !== 0 || 1 / a === 1 / b;”,eq()函数并没有返回值(return xxx),所以“f (a == null || b == null) return a === b;”还是必要的...

@lessfish
Copy link
Owner Author

@qingzhu1224

我的意思是 if (a == null || b == null) return a === b; 可以写成 if (a == null || b == null) return false; 因为如果 a === btrue,前面就 return 掉了。

而且 eq 函数是有返回值的,返回布尔值。

@aircloud
Copy link

aircloud commented Nov 15, 2016

能否问下源码中这一段是做什么的:

    while (length--) {
      // Linear search. Performance is inversely proportional to the number of
      // unique nested structures.
      if (aStack[length] === a) return bStack[length] === b;
    }

个人认为不会出现(aStack[length] === a)的情况啊?

@lessfish
Copy link
Owner Author

@aircloud 这段和上面一段我都看的云里雾里,也没有过分解读,递归一笔带过了 .. (其实是看不大懂)

@ahonn
Copy link

ahonn commented Nov 21, 2016

if (a == null || b == null) return a === b; 的确应该是直接 return false.
这里 a === b 的返回值一定是 false,否则这行代码也就不会执行了。所以当 a == null || b == null为 true 的时候 a b 其中的一个变量的值会是 null 或者 undefined,但不管如何 a b 都是不可能是相同的值。

早上跑去 underscore 提了个 issue,结果也是觉得应该改成 false。

@lessfish
Copy link
Owner Author

@ahonn 看到你的 pr 被 merge 了,看来我想的没错!Good job !

@Bubbfish
Copy link

image
NaN不等于NaN啊

@lessfish
Copy link
Owner Author

lessfish commented Jan 13, 2017

@Bubbfish underscore 中认为 _.isEqual(NaN, NaN)true,这也比较符合我们理想中对 equal 的期待

@Bubbfish
Copy link

@hanzichi 哦哦,这样啊,谢谢

@mqyqingfeng
Copy link

看到楼主注释的源码 isEqual 函数有对 aCtor instanceof aCtor 的疑惑,这个应该是用来判断是否是 Object 构造函数,因为:

Object instanceof Object // true

@mjylfz
Copy link

mjylfz commented Aug 3, 2017

这个可以比较两个数组相等吗

@mqyqingfeng
Copy link

@mjylfz 当然可以啦~

@Klaus1995
Copy link

看了isEqual部分的源码,有几个问题。
1.aCtor instanceof aCtor
据我所知,这句能返回true的只有内置的Object和Function构造函数,而能走到这步判断的话,a和b只能是狭义上的object了,所以这个判断条件是为了排除不同frame间object构造函数Object不同的情况,也正如 @mjylfz说的一样。
而除了上面那种情况后,其他对象只要构造函数不同就认为这两个对象unequal。
可能这是作者的思路,因为从前面的判断可以看出作者认为function类型的话除了指针相同(a=b=function(){})这种情况是equal的,其他情况都认为是unequal,哪怕是a=function(){},b=function(){}这种情况也被认为是unequal的。
所以,只要构造函数不同就认为这两个对象不equal,因为不同的frame里是不能拿到同一个变量指针的,也就不存在楼主提的不同frame下构造函数相同的情况。

      if (aCtor !== bCtor && !(_.isFunction(aCtor) && aCtor instanceof aCtor &&
                               _.isFunction(bCtor) && bCtor instanceof bCtor)
                          && ('constructor' in a && 'constructor' in b)) {
        return false;
      }

这个地方有三个判断条件,第一个是判断constructor属性值不等,没有争议,第二个是判断上面提到的不同frame间Object构造函数不同的情况,也没有争议(_.isFunction是为了保证instanceof调用合法,不是function的话js执行会报错),但是第三个'constructor' in a && 'constructor' in b我就不理解了,我认为这个判断条件没有意义。
如果a和b都没有constructor属性(不管是不是继承的),那么aCtor一定等于bCtor因为都是undefined,第一个判断条件就一定是false,不会执行到第三个判断条件(&&短路);而如果a和b只有其中一个有constructor属性,那么这两个狭义上的对象的key-value对肯定是不相同的,已经可以判断出是unequal了。
所以我不是很懂为什么要写第三个判断条件。

@Klaus1995
Copy link

2.对于调用栈的那部分我不太理解

    aStack = aStack || [];
    bStack = bStack || [];

    var length = aStack.length;

    while (length--) {
      // Linear search. Performance is inversely proportional to the number of
      // unique nested structures.
      if (aStack[length] === a) return bStack[length] === b;
    }

    // Add the first object to the stack of traversed objects.
    aStack.push(a);
    bStack.push(b);

对于这部分代码,我理解的就是:
对于深层嵌套的对象比较,可以把这种对象看做一棵树,而这段代码会把目前操作分支推入调用栈里,栈顶是目前正在判断的对象,栈底是根对象。
而这棵树的最顶端一定是基本类型值判断equal(因为引用类型值会被继续递归)。如果判断不等则整个isEqual方法返回false,栈被销毁;如果返回true,则返回到栈顶的对象的判断,如果对象equal,则该对象退栈,返回到上一个对象分叉点。
代码块中的while语句把栈遍历了一遍判断aStack[length] === a,而代码能执行到这已经确定a是一个引用类型值,用全等判断会返回true只有对象指针相同的情况。
如果这句判断返回true,就证明目前操作的对象和它所在分支的上端某对象指针相同,这不就是一个循环吗?a的某一个属性的值为a对象?据我所知js好像没有形成循环的情况,所以这句结果一定会是false,所以执行这句的意义在哪?所以进一步思考创建这个栈的意义是什么?我觉得不用栈直接递归就可以了。
望解答。。。

@ahonn
Copy link

ahonn commented Aug 10, 2017

@Klaus1995 当然有,对象的属性引用自身
image

@Klaus1995
Copy link

@ahonn 原来是这样,那这么做就很有意义了,防止无限递归。谢谢解答

@mqyqingfeng
Copy link

@Klaus1995 关于第一个问题,给你举个例子:

var attrs = Object.create(null);
attrs.name = "Bob";
eq(attrs, {name: "Bob"}); // ???

你会发现,在 underscore 中,一个有构造函数,一个没有构造函数,但是这两个对象是“相等”的,之所以判断 'constructor' in a 就是为了处理这种情况。

@lessfish
Copy link
Owner Author

@mqyqingfeng 我都快忘光了 - - 看到你最近有在看,感谢帮忙解答

@mqyqingfeng
Copy link

@hanzichi 楼主客气了,我从楼主的系列文章中受益颇多,也希望能帮忙解答一些问题~

@Klaus1995
Copy link

@mqyqingfeng 所以underscore里面对‘equal’的定义是这样的:
1.如果两个对象是由构造函数new出来的,那么两个对象的构造函数不同,他俩就是unequal的
2.如果只有一个是由构造函数new出来的,那么两个对象的构造函数虽然不同,但是会忽略掉这个因素,继续接下来的递归展开比较,如果递归成功则是equal的,就是你所举的例子
3.如果两个对象都不是构造函数的实例,则直接递归展开比较,也会忽略掉构造函数这个比较因素(因为都没有)
另外:我们定义的对象会默认调用内置的Object构造函数,所以想要建一个没有构造函数的对象,只能用Object.create(null)这个方法
这是我的理解,你觉得对吗?

@mqyqingfeng
Copy link

@Klaus1995 正是如此,不过要想建立一个没有构造函数的对象, Object.create({value: 1}) 之类的也是可以的,所以在 underscore 中

    var a = Object.create({value: 1})
    var b = Object.create({value: 2})
   console.log(_.isEqual(a, b)) // true

@Klaus1995
Copy link

@mqyqingfeng 但是这样的话会有另外一个问题:
我们目前能访问到一个对象的constructor属性是因为这个对象的原型对象上有这个属性,所以我们访问的时候会去原型对象上查找并返回,但是有一种情况是这个对象实例上自带的constructor属性,这样就会覆盖掉原型对象上的constructor属性(虽然原型对象上的constructor属性也能重写,跟这种情况差不多一样),这种情况下就会有问题,举个例子就是:
image

@mqyqingfeng
Copy link

@Klaus1995 是的,就是会有这个问题

@Klaus1995
Copy link

@mqyqingfeng 所以这个算是bug还是什么?就算你那种例子也会有这个问题,道理是一样的。
image

@mqyqingfeng
Copy link

mqyqingfeng commented Aug 11, 2017

@Klaus1995 是的,这就是个 bug,你可以到 underscore 去提一个 issue,不过在实际开发中,也不会遇到这样的问题吧~

@Klaus1995
Copy link

@mqyqingfeng
我是说我把你那个例子里Object.create()函数里面的对象稍微改了下就会出问题,你原来的例子结果还是true
用非ECMASCRIPT标准里面的__proto__属性来代替constructor属性来判断可以避免这个问题,只是不太清楚兼容性,毕竟不是标准里的,但是很多浏览器内置已经实现了

@rookiePrgrmer
Copy link

请教楼主一个问题。

// An egal comparison is performed for other numeric values.
// 排除了 NaN 干扰
// 还要考虑 0 的干扰
// 用 +a 将 Number() 形式转为基本类型
// 如果 a 为 0,判断 1 / +a === 1 / b
// 否则判断 +a === +b
return +a === 0 ? 1 / +a === 1 / b : +a === +b;

这部分代码一直不太理解。
到底0的干扰指的什么干扰呢?

@mqyqingfeng
Copy link

@rookiePrgrmer

default

@rookiePrgrmer
Copy link

@mqyqingfeng,你好,非常感谢你的回答,你的排版非常漂亮,而且回答得细致全面。

0和-0的区别我是知道的,但是在underscore的eq方法一开始就已经对此进行了判断了,也就是下面这段代码:

// Identical objects are equal. 0 === -0, but they aren't identical.
// See the Harmony egal proposal.
// a === b 时
// 需要注意 0 === -0 这个 special case
// 0 和 -0 不相同
// 至于原因可以参考上面的链接
if (a === b) return a !== 0 || 1 / a === 1 / b;

然后,在下面,又出现了这样的代码:
return +a === 0 ? 1 / +a === 1 / b : +a === +b;
楼主说是要排除0的干扰,既然第一行已经判断过了,为什么这里还要再次判断?

@mqyqingfeng
Copy link

@rookiePrgrmer 用于判断 Number(+0) 和 Number(-0)

@jyzwf
Copy link

jyzwf commented Jan 9, 2018

@mqyqingfeng

return +a === 0 ? 1 / +a === 1 / b : +a === +b;

上面当 +a === 0 时,为什么 1 / +a === 1 / b 一个前面有 + ,一个没有呢?

此外,最新的 underscore 里面加入了 如下的判断:

case '[object Symbol]':
                return SymbolProto.valueOf.call(a) === SymbolProto.valueOf.call(b);

image

这里是否是一种判断失误 呢?

最后还有一部分就是上面提到的调用栈的问题:

aStack = aStack || [];
        bStack = bStack || [];

        var length = aStack.length;
        while (length--) { // 逐个比较其值    第一次时 length = 0 这里不会执行
           // aStack[length] === a   
           // aStack[length] 这里难道不是空吗?不应该是 length - 1?
            if (aStack[length] === a) return bStack[length] === b
        }

        aStack.push(a)
        bStack.push(b)

谢谢解答^_^

@mqyqingfeng
Copy link

@jyzwf 我查了下起源的 PR,在 jashkenas/underscore@1dd1133?diff=unified

并没有讲到更改的原因,我个人觉得即便改成 + ,也是没有什么影响的。

第二个问题 Symbol 表示独一无二的值,即便 Symbol(1) 和 Symbol(1) 也是不一样的,结果是应该 false 吧

第三个问题在 while(length--) 的时候,length 的值就已经减去了 1

@jyzwf
Copy link

jyzwf commented Jan 11, 2018

@mqyqingfeng 谢谢你的回答,
第二个问题我以为他是将 Symbol(1) 和 Symbol(1) 视为相等的,,
第三个问题是我脑子突然短路了,,哈哈,
再次谢谢你哈^_^

@freedomme
Copy link

@hanzichi
这里我们将引用类型均转为基本类型,看如下代码:
var a = new Number(1);
console.log(+a); // 1
没错,加个 + 就解决了,其他的不难理解,都在注释里了。

+a 这里就是 引用类型均转为基本类型 ? 请教 这个出处是js基本语法吗?

@wangdabaoqq
Copy link

wangdabaoqq commented Jul 16, 2018

@freedomme +不就是一种隐式类型转换吗?

@XieJiSS
Copy link

XieJiSS commented Mar 9, 2019

@freedomme

+a 这里就是 引用类型均转为基本类型 ? 请教 这个出处是 js 基本语法吗?

这个语句

+variable

会尝试将 variable 转换为数字:

$ node
> +'1'
1
> +'0x0a'
10
> +'1e10'
10000000000
> +'-2'
-2
> +'[]'
NaN
> +'-0'
-0
> 

@shaomingquan
Copy link

shaomingquan commented Mar 26, 2019

关于两个stack。广度有限遍历,用stack缓存所有上层及同层已处理节点,对于当前节点a,如果a在缓存中,则a被循环嵌套,那么判断在同样位置b节点是否也被循环嵌套。存在嵌套必须return,不return会死循环。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests