爱囡囡，爱前端

0%

lodash源码解析：baseDifference、map

发表于 分类于 ， ， ，

本来是按顺序分析difference方法的，但是一连串下来的引用文件实在是太多了。所以本篇先分析difference方法的中的一个内置的私有方法baseDifference，顺带用到了 lodash 的map方法。

上篇文章先讨论了宽松相等和真值判断。同样，本篇先讨论严格相等比较，再分析一个问题，什么情况下 value !== value 为真？

严格相等

在 ECMA262 规范中，严格相等比较的原文如下：

Strict Equality Comparison

The comparison x === y, where x and y are values, produces true or false. Such a comparison is performed as follows:

  1. If Type(x) is different from Type(y), return false.
  2. If Type(x) is Number or BigInt, then
    1. Return ! Type(x)::equal(x, y).
  3. Return ! SameValueNonNumeric(x, y).

NOTE: This algorithm differs from the SameValue Algorithm in its treatment of signed zeroes and NaNs.

2.1 步中用的 T::equal ( x, y )语法：

Number::equal ( x, y )

  1. If x is NaN, return false.
  2. If y is NaN, return false.
  3. If x is the same Number value as y, return true.
  4. If x is +0 and y is -0, return true.
  5. If x is -0 and y is +0, return true.
  6. Return false.

BigInt::equal ( x, y )

The abstract operation BigInt::equal with two arguments x and y of type BigInt returns true if x and y have the same [mathematical integer](http://www.ecma-international.org/ecma-262/11.0/index.html#mathematical integer) value and false otherwise.

3 步中用的 SameValueNonNumeric ( x, y )语法：

SameValueNonNumeric ( x, y )

The internal comparison abstract operation SameValueNonNumeric(x, y), where neither x nor y are numeric type values, produces true or false. Such a comparison is performed as follows:

  1. Assert: Type(x) is not Number or BigInt.
  2. Assert: Type(x) is the same as Type(y).
  3. If Type(x) is Undefined, return true.
  4. If Type(x) is Null, return true.
  5. If Type(x) is String, then
    1. If x and y are exactly the same sequence of code units (same length and same code units at corresponding indices), return true; otherwise, return false.
  6. If Type(x) is Boolean, then
    1. If x and y are both true or both false, return true; otherwise, return false.
  7. If Type(x) is Symbol, then
    1. If x and y are both the same Symbol value, return true; otherwise, return false.
  8. If x and y are the same Object value, return true. Otherwise, return false.

整个规范是用一种独特的约定写的，所以把原文翻译下便于理解。

严格相等比较：

Strict Equality Comparison

比较 x === y（其中 x 和 y 是值），产生 true 或 false。该比较的执行步骤如下：

  1. 如果 x 的类型与 y 的类型不同，返回 false。
  2. 如果 x 的类型是 Number 或者 BigInt，
    1. Return ! Type(x)::equal(x, y).返回
  3. 返回 ! SameValueNonNumeric(x, y)的结果。

注意： 该算法与 SameValue 算法的区别在于对有符号零值和 NaN 的处理。

2.1 步中用的 T::equal ( x, y )语法：

Number::equal ( x, y )

  1. 如果 x 是 NaN，返回 false
  2. 如果 y 是 NaN，返回 fasle
  3. 如果 x 与 y 是相同的数字类型值，返回 true。
  4. 如果 x 为 +0 且 y 为-0，返回 true。
  5. 如果 x 为-0 且 y 为+0.返回 true
  6. 返回 false

BigInt::equal ( x, y )

如果 x 和 y 具有相同的数学整数值，则带有两个 BigInt 类型参数 x 和 y 的抽象操作 BigInt::equal 将返回 true，否则返回 false。

3 步中用的 SameValueNonNumeric ( x, y )语法：

SameValueNonNumeric(x, y)

内部比较抽象操作 SameValueNonNumeric(x, y)（其中 x 和 y 都不是数字类型值），产生 true 或 false。
该比较的执行步骤如下：

  1. 断言：x 的类型不是 Number 或 BigInt。
  2. 断言： x 的类型与 y 的类型相同。
  3. 如果 x 的类型为 Undefined，返回 true。
  4. 如果 x 的类型为 Null，返回 true。
  5. 如果 x 的类型为 String，
    1. 如果 x 和 y 是完全相同的代码单元序列（具有相同的长度并且在相同索引处有相同的代码单元），则返回 true；否则，返回 false。
  6. 如果 x 的类型为 Boolean，
    1. 如果 x 和 y 都为 true 或都为 false，返回 true；否则，返回 false。
  7. 如果 x 的类型为 Symbol，
    1. 如果 x 和 y 是相同的 Symbol 类型值，返回 true；否则，返回 false。
  8. 如果 x 和 y 为相同的 Object 类型值，返回 true；否则，返回 false。

回归到最初的问题，什么情况下 value !== value 为真？换言之，什么情况下value === value 为假？

  1. value和value本身肯定是相同的类型，跳过。
  2. 如果value为Number类型，
    1. value为NaN，返回false，所以NaN满足条件。
    2. Number类型的其他相同值都返回true，跳过。
  3. 如果value为BigInt类型，相同值都返回ture，跳过。
  4. 进入SameValueNonNumeric ( x, y )语法，Undefined、Null、String、Boolean、Symbol、Object类型相同值的严格相等比较都返回true，跳过。

分析完毕，所以只有 NaN !== NaN这一种情况满足value !== value 为真！

引用私有方法

Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/** 用于代替`undefined`的哈希值 */
const HASH_UNDEFINED = '__lodash_hash_undefined__';

class Hash {
  /**
   * 创建一个哈希对象。
   * 在原型链上有存、取、删、检查、清空五种方法。
   *
   * @private
   * @constructor
   * @param {Array} [entries] 准备缓存的键值对。
   */
  constructor(entries) {
    // 在构造函数里初始化index和length
    let index = -1;
    const length = entries == null ? 0 : entries.length;
    // 清空后挨个缓存
    this.clear();
    while (++index < length) {
      const entry = entries[index];
      this.set(entry[0], entry[1]);
    }
  }

  /**
   * 从哈希中删除所有键值
   *
   * @memberOf Hash
   */
  clear() {
    // 重新初始化
    // 将this.__data__原型设为了null，为的是能获得一个干净的字典
    // 可参考https://juejin.im/post/5acd8ced6fb9a028d444ee4e
    this.__data__ = Object.create(null);
    this.size = 0;
  }

  /**
   * 从哈希中删除键和对应的值
   *
   * @memberOf Hash
   * @param {string} key 准备删除值的键。
   * @returns {boolean} 如果键值删除成功，则返回true，否则返回false。
   */
  delete(key) {
    // 如果对应 value 存在就删掉
    const result = this.has(key) && delete this.__data__[key];
    // 删除成功就size-=1
    this.size -= result ? 1 : 0;
    return result;
  }

  /**
   * 获取哈希中对应键的值
   *
   * @memberOf Hash
   * @param {string} key 准备获取值的键
   * @returns {*} 返回键值对
   */
  get(key) {
    const data = this.__data__;
    const result = data[key];
    // 取值的时候再把HASH_UNDEFINED转为undefined
    return result === HASH_UNDEFINED ? undefined : result;
  }

  /**
   * 检查哈希中键对应的值是否存在
   *
   * @memberOf Hash
   * @param {string} key 准备去检查的键
   * @returns {boolean} 如果检查的键对应的值存在则返回true，否则返回false
   */
  has(key) {
    const data = this.__data__;
    // 此时，如果值为HASH_UNDEFINED是可以返回true的
    return data[key] !== undefined;
  }

  /**
   * 设置哈希中的键对应的值
   *
   * @memberOf Hash
   * @param {string} key 准备去设置值的键
   * @param {*} value 打算设置成的值
   * @returns {Object} 返回这个哈希实例
   */
  set(key, value) {
    const data = this.__data__;
    // key已经存在就size += 0，key不存在就size += 1
    this.size += this.has(key) ? 0 : 1;
    // HASH_UNDEFINED在这里用上了，这里是为了让check检查的时候能返回true
    data[key] = value === undefined ? HASH_UNDEFINED : value;
    // 返回哈希实例
    return this;
  }
}

export default Hash;

MapCache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import Hash from './Hash.js';
// 可参考https://juejin.im/post/5c8cb622e51d454e0b5e0c76

/**
 * 获取map的数据
 *
 * @private
 * @param {Object} map 需要查询的map
 * @param {string} key 引用的键
 * @returns {*} 返回map的数据
 */
function getMapData({ __data__ }, key) {
  const data = __data__;
  // 首先检查key是否适合作为键
  return isKeyable(key)
    ? // 如果适合，看看是不是string，是string就用string，否则用hash
      data[typeof key === 'string' ? 'string' : 'hash']
    : // 不适合就用map
      data.map;
}

/**
 * 检查value是否适合作为唯一的对象键。
 *
 * @private
 * @param {*} value 要检查的值
 * @returns {boolean} 如果目标适合作为唯一的对象键则返回true，否则返回false。
 */
function isKeyable(value) {
  const type = typeof value;
  // 如果typeof返回值为string、number、symbol、boolean且内容不为__proto__时，返回true
  // 如果typeof返回值不为string、number、symbol、boolean且内容为null时，返回true
  // 其余都为false
  return type === 'string' ||
    type === 'number' ||
    type === 'symbol' ||
    type === 'boolean'
    ? value !== '__proto__'
    : value === null;
}

class MapCache {
  /**
   * 创建一个map缓存对象来存储键值对
   *
   * @private
   * @constructor
   * @param {Array} [entries] 要缓存的键值对
   */
  constructor(entries) {
    // 在构造函数里初始化index和length
    let index = -1;
    const length = entries == null ? 0 : entries.length;
    // 清空后挨个缓存
    this.clear();
    while (++index < length) {
      const entry = entries[index];
      this.set(entry[0], entry[1]);
    }
  }

  /**
   * 从map里删除所有键值对
   *
   * @memberOf MapCache
   */
  clear() {
    // 重新初始化
    this.size = 0;
    this.__data__ = {
      hash: new Hash(),
      map: new Map(),
      string: new Hash(),
    };
  }

  /**
   * 从map里删除键和他对应的值
   *
   * @memberOf MapCache
   * @param {string} key 需要从map里删除值的键
   * @returns {boolean} 如果删除成功则返回true，否则返回false
   */
  delete(key) {
    // 使用确定类型实例的delete方法删除
    const result = getMapData(this, key)['delete'](key);
    this.size -= result ? 1 : 0;
    return result;
  }

  /**
   * 获取map中键对应的值
   *
   * @memberOf MapCache
   * @param {string} key 需要获取值的键
   * @returns {*} 返回对应的值
   */
  get(key) {
    return getMapData(this, key).get(key);
  }

  /**
   * 检查map中键对应的值是否存在
   *
   * @memberOf MapCache
   * @param {string} key 准备去检查的键
   * @returns {boolean} 如果检查的键对应的值存在则返回true，否则返回false
   */
  has(key) {
    // 使用确定类型实例的has方法检查
    return getMapData(this, key).has(key);
  }

  /**
   * 设置map中的键对应的值
   *
   * @memberOf MapCache
   * @param {string} key 准备去设置值的键
   * @param {*} value 打算设置成的值
   * @returns {Object} 返回这个mapCache实例
   */
  set(key, value) {
    // 使用确定类型实例的set方法设置值
    const data = getMapData(this, key);
    const size = data.size;

    data.set(key, value);
    this.size += data.size == size ? 0 : 1;
    return this;
  }
}

export default MapCache;

SetCache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import MapCache from './MapCache.js';

/** 用于代替`undefined`的哈希值 */
const HASH_UNDEFINED = '__lodash_hash_undefined__';

class SetCache {
  /**
   * 创建一个数组缓存对象以存储唯一值。
   *
   * @private
   * @constructor
   * @param {Array} [values] 需要缓存的值
   */
  constructor(values) {
    // 在构造函数里初始化index和length
    let index = -1;
    const length = values == null ? 0 : values.length;
    // 挨个存到this.__data__中
    this.__data__ = new MapCache();
    while (++index < length) {
      this.add(values[index]);
    }
  }

  /**
   * 向数组缓存中添加值
   *
   * @memberOf SetCache
   * @alias push
   * @param {*} value 需要缓存的值
   * @returns {Object} 返回缓存实例
   */
  add(value) {
    this.__data__.set(value, HASH_UNDEFINED);
    return this;
  }

  /**
   * 检查数组缓存中是否存在值
   *
   * @memberOf SetCache
   * @param {*} value 需要搜索的值
   * @returns {boolean} 如果value存在则返回true，否则返回false
   */
  has(value) {
    return this.__data__.has(value);
  }
}

// 最后在原型链上把push指向了add方法
SetCache.prototype.push = SetCache.prototype.add;

export default SetCache;

baseIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * `findIndex` 和 `findLastIndex`的实现基础
 *
 * @private
 * @param {Array} array 打算检索的数组
 * @param {Function} predicate 每次迭代时调用的函数
 * @param {number} fromIndex 起始处的索引位置
 * @param {boolean} [fromRight] 指定是否从右向左迭代
 * @returns {number} 返回找到元素的 索引值（index），否则返回 -1。
 */
function baseFindIndex(array, predicate, fromIndex, fromRight) {
  // 取到array.length
  const { length } = array;
  // 如果从左向右，起始索引位置就是fromIndex - 1；如果从右向左，起始索引位置是 fromIndex + 1。
  // 目的是迭代时能把fromIndex包进去。
  let index = fromIndex + (fromRight ? 1 : -1);

  // 迭代时，从左向右则index递增，从右向左则index递减
  while (fromRight ? index-- : ++index < length) {
    // 在这里定义了predicate函数的参数(item, index, array)，找到了想要的元素则返回true
    if (predicate(array[index], index, array)) {
      // 返回想寻找元素的索引
      return index;
    }
  }
  // 所有的元素都不匹配，就返回 -1。
  return -1;
}

export default baseFindIndex;

baseIsNaN

正是在这里用到了前文中只有NaN !== NaN为真的讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * isNaN的实现基础，不支持对象形式的数字。
 *
 * @private
 * @param {*} value 要检查的值
 * @returns {boolean} 如果value是NaN则返回true，否则返回false。
 */
function baseIsNaN(value) {
  // 只有NaN !== NaN
  return value !== value;
}

export default baseIsNaN;

strictIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * indexOf的一个特定版本，对value执行严格相等比较，即 ===。
 *
 * @private
 * @param {Array} array 要检查的数组
 * @param {*} value 要搜索的值
 * @param {number} fromIndex 搜索开始位置处的索引
 * @returns {number} 返回匹配值的索引，否则返回-1
 */
function strictIndexOf(array, value, fromIndex) {
  // 把fromIndex位置处的值包含进来
  let index = fromIndex - 1;
  // 取到array.length
  const { length } = array;

  // 迭代
  while (++index < length) {
    // 比较时使用===
    if (array[index] === value) {
      // 返回搜索到的索引
      return index;
    }
  }
  // 返回-1
  return -1;
}

export default strictIndexOf;

baseIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import baseFindIndex from './baseFindIndex.js';
import baseIsNaN from './baseIsNaN.js';
import strictIndexOf from './strictIndexOf.js';

/**
 * indexOf的基础实现，不使用fromIndex边界检查
 *
 * @private
 * @param {Array} array 要检查的数组
 * @param {*} value 要搜索的值
 * @param {number} fromIndex 搜索开始位置的索引
 * @returns {number} 返回匹配值的索引，否则返回-1
 */
function baseIndexOf(array, value, fromIndex) {
  // value为NaN的时候，调用baseFindIndex；value不为NaN的时候，调用strictIndexOf
  return value === value
    ? strictIndexOf(array, value, fromIndex)
    : baseFindIndex(array, baseIsNaN, fromIndex);
}

export default baseIndexOf;

arrayIncludes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import baseIndexOf from './baseIndexOf.js';

/**
 * 数组`includes`方法的的特殊版本，不支持指定开始搜索位置的索引。
 *
 * @private
 * @param {Array} [array] 要检查的数组
 * @param {*} target 要搜索的值
 * @returns {boolean} 如果搜索到了目标则返回true，否则返回false。
 */
function arrayIncludes(array, value) {
  // 初始化length
  const length = array == null ? 0 : array.length;
  // 当length不为0且能搜到value时，返回true，否则返回false。
  return !!length && baseIndexOf(array, value, 0) > -1;
}

export default arrayIncludes;

arrayIncludesWith

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 此函数与`arrayIncludes`相似，但会接受一个比较器（comparator）函数参数
 *
 * @private
 * @param {Array} [array] 要检查的数组
 * @param {*} target 要搜索的值
 * @param {Function} comparator 每个元素调用的比较器函数
 * @returns {boolean} 如果检索到目标则返回true，否则返回false
 */
function arrayIncludesWith(array, target, comparator) {
  // 如果array参数为undefined或null，返回false
  if (array == null) {
    return false;
  }

  // 迭代
  for (const value of array) {
    // 每次迭代调用比较器
    if (comparator(target, value)) {
      // comparator返回true的时候，就返回true
      return true;
    }
  }
  // 没检索到，返回false
  return false;
}

export default arrayIncludesWith;

cacheHas

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 检查缓存中键对应的值是否存在
 *
 * @private
 * @param {Object} cache 需要查询的缓存
 * @param {string} key 需要查询的键
 * @returns {boolean} 如果检查的键对应的值存在则返回true，否则返回false
 */
function cacheHas(cache, key) {
  return cache.has(key);
}

export default cacheHas;

map、baseDifference

map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 通过调用迭代函数（iteratee）遍历数数组中的每一个元素来创建一个新数组
 * 迭代函数有三个参数: (value, index, array)
 *
 * @since 5.0.0
 * @category Array
 * @param {Array} array 被迭代的数组
 * @param {Function} iteratee 每次迭代时调用的函数
 * @returns {Array} 返回新的映射后的数组
 * @example
 *
 * function square(n) {
 *   return n * n
 * }
 *
 * map([4, 8], square)
 * // => [16, 64]
 */
function map(array, iteratee) {
  // 初始化index、length和result
  let index = -1;
  const length = array == null ? 0 : array.length;
  const result = new Array(length);

  // 迭代
  while (++index < length) {
    // 把迭代函数返回的结果挨个赋值给新数组的对应位置
    result[index] = iteratee(array[index], index, array);
  }
  // 返回新数组
  return result;
}

export default map;

baseDifference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import SetCache from './SetCache.js';
import arrayIncludes from './arrayIncludes.js';
import arrayIncludesWith from './arrayIncludesWith.js';
import map from '../map.js';
import cacheHas from './cacheHas.js';

/** 当数组长度达到以下大小，则进行大数组优化，当前是200 */
const LARGE_ARRAY_SIZE = 200;

/**
 * 类`difference`方法的基本实现，不支持排除多个数组。
 *
 * @private
 * @param {Array} array 要检查的数组
 * @param {Array} values 需要排除的数组
 * @param {Function} [iteratee] 每个元素调用的迭代函数
 * @param {Function} [comparator] 每个元素调用的比较器函数
 * @returns {Array} 返回过滤后的新数组
 */
function baseDifference(array, values, iteratee, comparator) {
  // 初始化设置
  // includes默认使用arrayIncludes
  let includes = arrayIncludes;
  let isCommon = true;
  const result = [];
  const valuesLength = values.length;

  // 空数组直接返回[]
  if (!array.length) {
    return result;
  }
  // 当迭代函数存在时，
  if (iteratee) {
    // 将value的每一项都调用迭代函数
    values = map(values, (value) => iteratee(value));
  }
  // 当比较器函数存在时，
  if (comparator) {
    // includes切换为arrayIncludesWith
    includes = arrayIncludesWith;
    isCommon = false;
  }
  // 当比较器函数不存在但是数组过长时（进行了优化）
  else if (values.length >= LARGE_ARRAY_SIZE) {
    // includes切换为cacheHas
    includes = cacheHas;
    isCommon = false;
    // value使用SetCache封装
    values = new SetCache(values);
  }
  // continue跳到此处
  outer: for (let value of array) {
    // 如果有迭代函数，则每一项都调用迭代函数返回computed
    const computed = iteratee == null ? value : iteratee(value);

    value = comparator || value !== 0 ? value : 0;
    // 如果是普通通用数组，且该项不为NaN
    if (isCommon && computed === computed) {
      let valuesIndex = valuesLength;
      // 内层循环进行比较
      while (valuesIndex--) {
        if (values[valuesIndex] === computed) {
          // 查到相同项就跳出本层循环，就不执行push了
          continue outer;
        }
      }
      // 没查到相同项，就push到新数组
      result.push(value);
    }
    // 如果不是普通通用数组，就去挨个执行includes函数（可能为cacheHas或arrayIncludesWith）
    else if (!includes(values, computed, comparator)) {
      // 当不重复的时候，就把本项push到新数组
      result.push(value);
    }
  }
  // 最后返回结果
  return result;
}

export default baseDifference;

原生实现

map

我觉得 map 也不用太多说了，毕竟Array.prototype.map是原生实现了的。

1
2
3
4
5
6
7
// 原生实现
var array1 = [1, 2, 3];
var array2 = array1.map(function (value, index) {
  return value * 2;
});
console.log(array2);
// output: [2, 4, 6]

总结

lodash 中，实现一个baseDifference方法之所以这么复杂，一是因为它支撑了三个方法的实现difference、differenceBy、differenceWith，二是因为lodash对 length 大于200的数组进行了优化，使用一种对象缓存的方式模拟了数组的增删查改。

👆 全文结束，棒槌时间到 👇