lodash源码阅读四：difference

参考资料

github仓库地址

源码拷贝仓库地址(阅读的源码版本)

中文文档

英文文档

difference(array, [values1, values2…])

difference 创建一个具有新数组，数组中的每个元素都是只存在于 array 数组，而不存在于其他数组。

在 difference 方法中存在许多辅助方法和数据结构。

数据结构

Hash

Hash 对象实例化时传入一个数组，数组的元素是一个由键值对为元素组成的键值对数组。
键值对数组的第一个元素为键名，第二个元素为键值

Hash 对象的实例方法有 set get has delete clear

/** Used to stand-in for `undefined` hash values. */
const HASH_UNDEFINED = '__lodash_hash_undefined__'

// Hash 对象
// 实例化 Hash 对象是传入一个数组，数组的元素是一个由键值对为元素组成的键值对数组。
// 键值对数组的第一个元素为键名，第二个元素为键值
// 实例化 Hash 对象时创建实例属性：__data__ 和 size 属性
// 实例化时将传入数组中的键值对添加到 __data__ 对象中，并计算出总的键值对数量赋值给 size 属性
// Hash 对象的实例方法有 set get has delete clear
class Hash {

  /**
   * Creates a hash object.
   *
   * @private
   * @constructor
   * @param {Array} [entries] The key-value pairs to cache.
   */
  constructor(entries) {
    let index = -1
    const length = entries == null ? 0 : entries.length

    this.clear() // 初始化 __data__ 和 size 属性
    while (++index < length) {
      // 循环遍历取出键值对，并设置到 __data__ 对象中
      const entry = entries[index]
      this.set(entry[0], entry[1])
    }
  }

  /**
   * Removes all key-value entries from the hash.
   *
   * @memberOf Hash
   */
  clear() {
    // 清空 __data__ 对象，size 归零
    this.__data__ = Object.create(null)
    this.size = 0
  }

  /**
   * Removes `key` and its value from the hash.
   *
   * @memberOf Hash
   * @param {string} key The key of the value to remove.
   * @returns {boolean} Returns `true` if the entry was removed, else `false`.
   */
  delete(key) {
    // 删除键值对
    const result = this.has(key) && delete this.__data__[key]
    this.size -= result ? 1 : 0
    return result
  }

  /**
   * Gets the hash value for `key`.
   *
   * @memberOf Hash
   * @param {string} key The key of the value to get.
   * @returns {*} Returns the entry value.
   */
  get(key) {
    // 获取键值对
    const data = this.__data__
    const result = data[key]
    return result === HASH_UNDEFINED ? undefined : result
  }

  /**
   * Checks if a hash value for `key` exists.
   *
   * @memberOf Hash
   * @param {string} key The key of the entry to check.
   * @returns {boolean} Returns `true` if an entry for `key` exists, else `false`.
   */
  has(key) {
    // 判断是否含有某一键值对
    const data = this.__data__
    return data[key] !== undefined
  }

  /**
   * Sets the hash `key` to `value`.
   *
   * @memberOf Hash
   * @param {string} key The key of the value to set.
   * @param {*} value The value to set.
   * @returns {Object} Returns the hash instance.
   */
  set(key, value) {
    // 设置键值对
    const data = this.__data__
    this.size += this.has(key) ? 0 : 1
    data[key] = value === undefined ? HASH_UNDEFINED : value
    return this
  }
}

export default Hash
复制代码

MapCache

MapCache 和 Hash 相似，同样是接受一个键值对数组作为参数实例化对象。但是 MapCache 接受的键值对，键名可能是一个对象或者数组，也可能是一个普通的数据类型 (string, boolean, number, symbol)

MapCache 实例化时传入的键值对的键名类型有多种，MapCache 在保存键值对时根据键名类型进行区分存取

如果键名是对象类型，则用 Map 数据类型存取键值对

如果键名不是对象类型，则用 Hash 数据结构来存取键值对

import Hash from './Hash.js'

/**
 * Gets the data for `map`.
 *
 * @private
 * @param {Object} map The map to query.
 * @param {string} key The reference key.
 * @returns {*} Returns the map data.
 */
function getMapData({ __data__ }, key) {
  // 传入两个参数， mapCache 对象和 key
  // 获取对应 key 类型的 map 数据
  // 如果 key 是 string 类型，返回 mapCache.__data__.string
  // 如果 key 是 number，boolean 或者是 symbol 类型，返回 mapCache.__data__.hash
  // 如果 key 不是以上类型，返回 mapCache.__data__.map
  const data = __data__
  return isKeyable(key)
    ? data[typeof key === 'string' ? 'string' : 'hash']
    : data.map
}

/**
 * Checks if `value` is suitable for use as unique object key.
 *
 * @private
 * @param {*} value The value to check.
 * @returns {boolean} Returns `true` if `value` is suitable, else `false`.
 */
function isKeyable(value) {
  // 判断传入的 value 是否能够作为对象的属性名
  // string number boolean symbol 类型
  // 并且值不能为 ‘__proto__’
  // 或者值为 null 也可以
  const type = typeof value
  return (type === 'string' || type === 'number' || type === 'symbol' || type === 'boolean')
    ? (value !== '__proto__')
    : (value === null)
}

// 将传入的键值对保存起来
// 传入的键值对中，键名可能是一个对象或者数组，也可能是一个普通的数据类型 (string, boolean, number, symbol)
class MapCache {
  /**
   * Creates a map cache object to store key-value pairs.
   *
   * @private
   * @constructor
   * @param {Array} [entries] The key-value pairs to cache.
   */
  constructor(entries) {
    let index = -1
    const length = entries == null ? 0 : entries.length

    this.clear() // 初始化 __data__ 和 size 属性
    while (++index < length) {
      const entry = entries[index]
      this.set(entry[0], entry[1])
    }
  }

  /**
   * Removes all key-value entries from the map.
   *
   * @memberOf MapCache
   */
  clear() {
    this.size = 0
    this.__data__ = {
      'hash': new Hash, // 键名为 string 类型的键值对仓库
      'map': new Map, // 键名为 boolean, number, symbol 类型的键值对仓库
      'string': new Hash // map 实例 键名可能为 对象，数组等数据类型
    }
  }

  /**
   * Removes `key` and its value from the map.
   *
   * @memberOf MapCache
   * @param {string} key The key of the value to remove.
   * @returns {boolean} Returns `true` if the entry was removed, else `false`.
   */
  delete(key) {
    // 删除键名为 key 的键值对
    const result = getMapData(this, key)['delete'](key)
    this.size -= result ? 1 : 0
    return result
  }

  /**
   * Gets the map value for `key`.
   *
   * @memberOf MapCache
   * @param {string} key The key of the value to get.
   * @returns {*} Returns the entry value.
   */
  get(key) {
    // 获取键名为 key 的键值
    return getMapData(this, key).get(key)
  }

  /**
   * Checks if a map value for `key` exists.
   *
   * @memberOf MapCache
   * @param {string} key The key of the entry to check.
   * @returns {boolean} Returns `true` if an entry for `key` exists, else `false`.
   */
  has(key) {
    // 判断是否含有键名为 key 的键值对
    return getMapData(this, key).has(key)
  }

  /**
   * Sets the map `key` to `value`.
   *
   * @memberOf MapCache
   * @param {string} key The key of the value to set.
   * @param {*} value The value to set.
   * @returns {Object} Returns the map cache instance.
   */
  set(key, value) {
    // 根据键名的类型获取对应的数据仓库
    const data = getMapData(this, key)
    // 数据的大小
    const size = data.size

    // 设置键值对
    data.set(key, value)
    // 判断数据的大小是否有发生变化更新 size 属性
    this.size += data.size == size ? 0 : 1
    // 返回实例
    return this
  }
}

export default MapCache
复制代码

SetCache

SetCache 实例化时接收一个数组，将数组中的元素循环遍历存储起来。

SetCache 对象只有两个实例方法：add 和 has

import MapCache from './MapCache.js'

/** Used to stand-in for `undefined` hash values. */
const HASH_UNDEFINED = '__lodash_hash_undefined__'

class SetCache {

  /**
   * Creates an array cache object to store unique values.
   *
   * @private
   * @constructor
   * @param {Array} [values] The values to cache.
   */
  constructor(values) {
    let index = -1
    const length = values == null ? 0 : values.length

    this.__data__ = new MapCache //  实例化 MapCache 赋值给 __data__ 属性
    while (++index < length) {
      // 循环遍历数组将值添加到 __data__ 属性中
      this.add(values[index])
    }
  }

  /**
   * Adds `value` to the array cache.
   *
   * @memberOf SetCache
   * @alias push
   * @param {*} value The value to cache.
   * @returns {Object} Returns the cache instance.
   */
  add(value) {
    // 用 value 作为键名，HASH_UNDEFINED 作为键值添加到 MapCache 对象中
    this.__data__.set(value, HASH_UNDEFINED)
    // 返回当前实例
    return this
  }

  /**
   * Checks if `value` is in the array cache.
   *
   * @memberOf SetCache
   * @param {*} value The value to search for.
   * @returns {boolean} Returns `true` if `value` is found, else `false`.
   */
  has(value) {
    // 返回当前实例是否有 value
    return this.__data__.has(value)
  }
}

// 添加实例方法 push 并且赋值为 add
SetCache.prototype.push = SetCache.prototype.add

export default SetCache
复制代码

cacheHas(cache, key)

判断 cache 中是否存有某个 key 值。适用于 SetCache，MapCache 等数据结构

/**
 * Checks if a `cache` value for `key` exists.
 *
 * @private
 * @param {Object} cache The cache to query.
 * @param {string} key The key of the entry to check.
 * @returns {boolean} Returns `true` if an entry for `key` exists, else `false`.
 */
function cacheHas(cache, key) {
  return cache.has(key)
}

export default cacheHas
复制代码

辅助方法

baseFlatten & isArrayLikeObject

baseFlatten & isArrayLikeObject 方法就请看上一篇笔记 lodash源码阅读三

baseIsNaN(value)

baseIsNaN 返回 value 是否是 NaN

/**
 * The base implementation of `isNaN` without support for number objects.
 *
 * @private
 * @param {*} value The value to check.
 * @returns {boolean} Returns `true` if `value` is `NaN`, else `false`.
 */
function baseIsNaN(value) {
  return value !== value
}

export default baseIsNaN
复制代码

value !== value 什么情况下为 true。在 ECMA262 规范中，只有 NaN !== NaN 这一种情况满足。

ECMA262规范

详细的讲解可以看林景宜的记事本的这篇文章

baseFindIndex(array, predicate, fromIndex, fromRight)

baseFindIndex 返回在数组 array 中，能通过 predicate 函数的校验的元素的索引值。

其中 fromIndex 为开始遍历元素的索引，fromRight 则表示查找方向是向左还是向右

/**
 * The base implementation of `findIndex` and `findLastIndex`.
 *
 * @private
 * @param {Array} array The array to inspect.
 * @param {Function} predicate The function invoked per iteration.
 * @param {number} fromIndex The index to search from.
 * @param {boolean} [fromRight] Specify iterating from right to left.
 * @returns {number} Returns the index of the matched value, else `-1`.
 */
function baseFindIndex(array, predicate, fromIndex, fromRight) {
  // 获取数组的长度，根据查找方向确定开始查找的位置索引
  const { length } = array
  let index = fromIndex + (fromRight ? 1 : -1)

  // 根据查找方向开始开始遍历，调用 predicate 函数，传入遍历到的数组元素，索引值和数组
  // 如果 predicate 返回值为 true ，结束遍历并返回当前索引
  while ((fromRight ? index-- : ++index < length)) {
    if (predicate(array[index], index, array)) {
      return index
    }
  }
  // 遍历结束后没有满足 predicate 函数索引，返回 -1
  return -1
}

export default baseFindIndex
复制代码

strictIndexOf(array, value, fromIndex)

从 fromIndex 开始从左到右遍历 array 中的元素，找到与 value 严格相等(===)的元素的索引并返回。如果不存在这样的元素，返回 -1

/**
 * A specialized version of `indexOf` which performs strict equality
 * comparisons of values, i.e. `===`.
 *
 * @private
 * @param {Array} array The array to inspect.
 * @param {*} value The value to search for.
 * @param {number} fromIndex The index to search from.
 * @returns {number} Returns the index of the matched value, else `-1`.
 */
function strictIndexOf(array, value, fromIndex) {
  // 获取开始遍历的索引值和数组的长度
  let index = fromIndex - 1
  const { length } = array

  // 遍历数组，将元素和 value 做严格相等对比。如果严格相等，返回索引值
  while (++index < length) {
    if (array[index] === value) {
      return index
    }
  }
  // 遍历结束，返回 -1
  return -1
}

export default strictIndexOf
复制代码

baseIndexOf(array, value, fromIndex)

从 fromIndex 位置开始遍历查找 array 中 value 的索引值，如果不存在返回 -1

import baseFindIndex from './baseFindIndex.js'
import baseIsNaN from './baseIsNaN.js'
import strictIndexOf from './strictIndexOf.js'

/**
 * The base implementation of `indexOf` without `fromIndex` bounds checks.
 *
 * @private
 * @param {Array} array The array to inspect.
 * @param {*} value The value to search for.
 * @param {number} fromIndex The index to search from.
 * @returns {number} Returns the index of the matched value, else `-1`.
 */
function baseIndexOf(array, value, fromIndex) {
  // 如果 value 是 NaN，使用 baseFindIndex 方法查找索引，如果不是，使用 strictIndexOf 方法查找索引
  return value === value
    ? strictIndexOf(array, value, fromIndex)
    : baseFindIndex(array, baseIsNaN, fromIndex)
}

export default baseIndexOf
复制代码

arrayIncludes(array, value)

判断数组 array 中是否有 value 元素

import baseIndexOf from './baseIndexOf.js'

/**
 * A specialized version of `includes` for arrays without support for
 * specifying an index to search from.
 *
 * @private
 * @param {Array} [array] The array to inspect.
 * @param {*} target The value to search for.
 * @returns {boolean} Returns `true` if `target` is found, else `false`.
 */
function arrayIncludes(array, value) {
  const length = array == null ? 0 : array.length
  // 判断数组的长度是否大于 0 并且 array 中 value 的索引大于 -1
  return !!length && baseIndexOf(array, value, 0) > -1
}

export default arrayIncludes
复制代码

arrayIncludesWith(array, target, comparator)

类似 arrayInclude 的方法，arrayIncludesWith 参数中多一个 comparator 对比函数，在遍历 array 数组的时候会和 target 一起传入得到对比结果

/**
 * This function is like `arrayIncludes` except that it accepts a comparator.
 *
 * @private
 * @param {Array} [array] The array to inspect.
 * @param {*} target The value to search for.
 * @param {Function} comparator The comparator invoked per element.
 * @returns {boolean} Returns `true` if `target` is found, else `false`.
 */
function arrayIncludesWith(array, target, comparator) {
  if (array == null) {
    return false
  }

  for (const value of array) {
    // 遍历 array 和 target 一起传入 comparator 函数得到对比结果
    // 如果结果为 true，返回结果
    if (comparator(target, value)) {
      return true
    }
  }
  // 遍历结束后，没有满足 target 和 comparator 对比的元素
  // 返回 false
  return false
}

export default arrayIncludesWith
复制代码

difference 的实现

difference(array, values)

difference 可以接收多个数组作为参数，返回一个新的数组，数组中的元素为函数第一个参数中的存在而其他参数不存在的元素

import baseDifference from './.internal/baseDifference.js'
import baseFlatten from './.internal/baseFlatten.js'
import isArrayLikeObject from './isArrayLikeObject.js'

/**
 * Creates an array of `array` values not included in the other given arrays
 * using [`SameValueZero`](http://ecma-international.org/ecma-262/7.0/#sec-samevaluezero)
 * for equality comparisons. The order and references of result values are
 * determined by the first array.
 *
 * **Note:** Unlike `pullAll`, this method returns a new array.
 *
 * @since 0.1.0
 * @category Array
 * @param {Array} array The array to inspect.
 * @param {...Array} [values] The values to exclude.
 * @returns {Array} Returns the new array of filtered values.
 * @see union, unionBy, unionWith, without, xor, xorBy, xorWith,
 * @example
 *
 * difference([2, 1], [2, 3])
 * // => [1]
 */
function difference(array, ...values) {
  // 返回一个数组
  // 如果 array 是一个类数组对象，通过 baseDifference 得到结果并返回。否则返回空数组
  return isArrayLikeObject(array)
    // 通过 baseFlatten 将 values 中的所有类数组对象的元素组成一个新的数组
    ? baseDifference(array, baseFlatten(values, 1, isArrayLikeObject, true)) 
    : []
}

export default difference
复制代码

baseDifference(array, values, iteratee, comparator)

baseDifference 返回一个新的数组，数组中的元素是 array 中存在而 values 中不存在的元素。

参数中 iteratee 函数是对 array 和 values 元素做处理的函数，comparator 是自定义 array 和 values 元素的对比函数

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'

/** Used as the size to enable large array optimizations. */
// 限制数组的最大长度
const LARGE_ARRAY_SIZE = 200

/**
 * The base implementation of methods like `difference` without support
 * for excluding multiple arrays.
 *
 * @private
 * @param {Array} array The array to inspect.
 * @param {Array} values The values to exclude.
 * @param {Function} [iteratee] The iteratee invoked per element.
 * @param {Function} [comparator] The comparator invoked per element.
 * @returns {Array} Returns the new array of filtered values.
 */
function baseDifference(array, values, iteratee, comparator) {
  // 初始化 includes 遍历函数为 arrayIncludes
  let includes = arrayIncludes
  // 初始化 isCommon 为 true
  // 如果有传入 comparator 函数或者 values 的长度超过限制数组限制长度的大小
  // isCommon 就会被修改为 false，同时 includes 会被修改为相对应的值
  let isCommon = true
  const result = []
  const valuesLength = values.length

  if (!array.length) {
    // array 长度为 0，返回空数组
    return result
  }
  if (iteratee) {
    // 如果传入了 iteratee，将 values 处理生成新的数组
    values = map(values, (value) => iteratee(value))
  }
  if (comparator) {
    // 如果传入了 comparator，将 includes 设置为 arrayIncludesWith
    includes = arrayIncludesWith
    isCommon = false
  }
  else if (values.length >= LARGE_ARRAY_SIZE) {
    // 如果 values 的长度超过限制大小
    // 将 includes 设置为 cacheHas
    // values 转换为 SetCache 数据
    includes = cacheHas
    isCommon = false
    values = new SetCache(values)
  }
  outer:
  for (let value of array) {
    // 遍历 array
    // 将 value 通过 iteratee 处理
    const computed = iteratee == null ? value : iteratee(value)

    value = (comparator || value !== 0) ? value : 0
    if (isCommon && computed === computed) {
      // isCommon 为 true 并且 computed 不为 NaN
      let valuesIndex = valuesLength
      while (valuesIndex--) {
        // 遍历 values 和 computed 做对比
        if (values[valuesIndex] === computed) {
          // 如果 values 中存在 computed，继续 array 的遍历
          continue outer
        }
      }
      // 如果 values 不存在 computed，将 value 添加到 result
      result.push(value)
    }
    else if (!includes(values, computed, comparator)) {
      // isCommon 为 false，调用 includes 判断 computed 是否存在 values 中。如果不存在，将 value 添加到 result
      result.push(value)
    }
  }
  // 返回 result
  return result
}

export default baseDifference
复制代码