2019-08-02

JavaScript

2 小时读完 (大约 17702 个字)

JavaScript 中一些常用方法的实现

算是一些手写 API，常用方法的一些汇总，反正就是面试可能涉及到的一些手写功能可能都会有所涉及，不仅仅只是为了面试所用，也算是在这里做下汇总记录，方便以后可以快速查询（可以直接参考左边目录）

once/debounce/thorttle

once 方法实现比较简单，一般来说有两种实现方式，方法一，利用闭包的特性，传递参数，执行完一次以后就自动解除绑定

function once(dom, event, callback) {
  var handle = function () {
    callback()
    dom.removeEventListener(event, handle)
  }
  dom.addEventListener(event, handle)
}

第二种方式是定义一个局部变量，用来标记函数是否已经调用

const once = (fn) => {
  let done = false
  return function () {
    done ? undefined : ((done = true), fn.apply(this, arguments))
  }
}

防抖和节流可以使用一个现实中常见的例子来进行举例，比如使用电梯运送策略来说明这两个方法，比如每天上班大厦底下的电梯，把电梯完成一次运送，类比为一次函数的执行和响应，假设电梯有两种运行策略 throttle 和 debounce ，超时设定为 15 秒，不考虑容量限制

throttle 策略的电梯，保证如果电梯第一个人进来后，15 秒后准时运送一次，不等待，如果没有人，则待机
debounce 策略的电梯，如果电梯里有人进来，等待 15 秒，如果有人进来，15 秒等待重新计时，直到 15 秒超时，开始运送

下面的实现方式只是两者最为基本的实现方式，这里我们只为展示其原理，关于它们两者更为完善的实现以及一些内部的原理可以参考我们之前整理过的函数防抖和节流

function debounce(fn, wait) {
  var timer
  return function () {
    var that = this, args = arguments
    clearTimeout(timer)
    timer = setTimeout(function () {
      fn.apply(that, args)
    }, wait)
  }
}

// 使用
window.onscroll = debounce(function () {
  console.log('debounce')
}, 1000)

function throttle(fn, wait) {
  var prev = 0
  return function () {
    var now = +new Date()
    if (now - prev >= wait) {
      fn.apply(this, arguments)
      prev = now
    }
  }
}

// 使用
var throtteScroll = throttle(function () {
  console.log('throtte')
}, 1000)

window.onscroll = throtteScroll

call/apply/bind

call 和 apply 更为具体的应用可以参考 JavaScript 中的 call 和 apply，主要包括

两者的区别
call 和 apply 的第一个参数
原理
实现
call 和 apply 哪个速度更快一些

实现如下

Function.prototype.call = function (context, ...args) {
  if (context === null || context === undefined) {
    context = window
  } else {
    context = Object(context)
  }
  let fn = Symbol()
  context[fn] = this
  let result = context[fn](...args)
  delete context[fn]
  return result
}


Function.prototype.apply = function (context) {
  if (context === null || context === undefined) {
    context = window
  } else {
    context = Object(context)
  }
  let fn = Symbol()
  context[fn] = this
  let result = arguments[1] ? context[fn](...arguments[1]) : context[fn]()
  delete context[fn]
  return result
}

// 如果为了更为完善的话，可以针对 apply 的第二个参数（类数组对象）来进行判断一下
const args = arguments[1]
let result
if (args) {
  if (!Array.isArray(args) && !isArrayLike(args)) {
    throw new TypeError(`second parameter needs to be an array or class array object`)
  } else {
    args = Array.from(args)
    result = context[fn](...args)
  }
} else {
  result = context[fn]()
}

function isArrayLike(o) {
  if (o &&                                 // o 不是 null、undefined 等
    typeof o === 'object' &&               // o 是对象
    isFinite(o.length) &&                  // o.length 是有限数值
    o.length >= 0 &&                       // o.length 为非负值
    o.length === Math.floor(o.length) &&   // o.length 是整数
    o.length < 4294967296)                 // o.length < 2^32
    return true
  else
    return false
}

bind 更为详细的实现可见 Function.prototype.bind()，主要包括

基本语法
使用 bind 绑定参数表
理解 bind
bind 与 currying
bind 与 new
bind 实现

ES5 当中实现

if (!Function.prototype.bind) {
  Function.prototype.bind = function (oThis) {
    if (typeof this !== 'function') {
      throw new TypeError('Function.prototype.bind - what is trying to be bound is not callable')
    }
    var aArgs = Array.prototype.slice.call(arguments, 1), fToBind = this, fNOP = function () { },
      fBound = function () {
        return fToBind.apply(this instanceof fNOP
          ? this
          : oThis, aArgs.concat(Array.prototype.slice.call(arguments)))
      }
    fNOP.prototype = this.prototype
    fBound.prototype = new fNOP()
    return fBound
  }
}

ES6 当中实现

Function.prototype.myBind = function (oThis, ...args) {
  const thisFn = this
  let fToBind = function (...params) {
    const context = this instanceof fToBind ? this : Object(oThis)
    return thisFn.apply(context, ...args, ...params)
  }
  fToBind.prototype = Object.create(thisFn.prototype)
  return fToBind
}

原生 API

new

要想手动实现 new 操作符，首先我们需要知道 new 的过程当中发生了什么，主要有以下几步

创建一个全新的对象，并继承其构造函数的 prototype，这一步是为了继承构造函数原型上的属性和方法
执行构造函数，方法内的 this 被指定为该新实例，也就是使 this 指向新创建的对象，这一步是为了执行构造函数内的赋值操作
通过 new 创建的每个对象将最终被 Prototype 链接到这个函数的 prototype 对象上
返回新实例（如果函数没有返回对象类型 Object（包含 Functoin，Array，Date，RegExg，Error），那么 new 表达式中的函数调用将返回该对象引用）

/* new Constructor */
function new (f) {
  var n = { '__prop__': f.prototype }         /* step1 */
  return function () {
    f.apply(n, arguments)                     /* step2 */
    return n                                  /* step3 */
  }
}

但是 __proto__ 这个属性是一个非标准属性，所以我们也可以采用下面这种方式

function myNew(foo, ...args) {
  let obj = Object.create(foo.prototype)      // 创建对象，相当于 o.__proto__ = func.prototype
  let result = foo.apply(obj, args)           // 改变 this 指向，把结果付给 result
  return result && result instanceof Object   // 判断 result 的类型是不是对象
    ? result                                  // 如果是，则返回 result
    : obj                                     // 否则返回构造函数的执行结果
}

我们可以来测试一下

function Foo(name) {
  this.name = name
}
const newObj = myNew(Foo, 'zhangsan')

console.log(newObj)                           // Foo {name: 'zhangsan'}
console.log(newObj instanceof Foo)            // true

Promise

具体实现过程可以参考 JavaScript 中 Promise 的实现，这里只展示最终代码

const isFunction = variable => typeof variable === 'function'

// 定义 Promise 的三种状态常量
const PENDING = 'PENDING'
const FULFILLED = 'FULFILLED'
const REJECTED = 'REJECTED'

class MyPromise {

  constructor(handle) {
    if (!isFunction(handle)) throw new Error('MyPromise must accept a function as a parameter')

    this._status = PENDING      // 添加状态
    this._value = undefined     // 添加状态
    this._fulfilledQueues = []  // 添加成功回调函数队列
    this._rejectedQueues = []   // 添加失败回调函数队列

    try {
      handle(this._resolve.bind(this), this._reject.bind(this))
    } catch (err) {
      this._reject(err)
    }
  }

  _resolve(val) {
    const run = () => {
      if (this._status !== PENDING) return
      // 依次执行成功队列中的函数，并清空队列
      const runFulfilled = (value) => {
        let cb
        while (cb = this._fulfilledQueues.shift()) {
          cb(value)
        }
      }
      // 依次执行失败队列中的函数，并清空队列
      const runRejected = (error) => {
        let cb
        while (cb = this._rejectedQueues.shift()) {
          cb(error)
        }
      }

      // 如果 resolve 的参数为 Promise 对象，则必须等待该 Promise 对象状态改变后
      // 当前 Promsie 的状态才会改变，且状态取决于参数 Promsie 对象的状态
      if (val instanceof MyPromise) {
        val.then(value => {
          this._value = value
          this._status = FULFILLED
          runFulfilled(value)
        }, err => {
          this._value = err
          this._status = REJECTED
          runRejected(err)
        })
      } else {
        this._value = val
        this._status = FULFILLED
        runFulfilled(val)
      }
    }

    // 为了支持同步的 Promise，这里采用异步调用
    setTimeout(run, 0)
  }

  _reject(err) {
    if (this._status !== PENDING) return
    // 依次执行失败队列中的函数，并清空队列
    const run = () => {
      this._status = REJECTED
      this._value = err
      let cb
      while (cb = this._rejectedQueues.shift()) {
        cb(err)
      }
    }
    // 为了支持同步的 Promise，这里采用异步调用
    setTimeout(run, 0)
  }

  then(onFulfilled, onRejected) {
    const { _value, _status } = this
    // 返回一个新的 Promise 对象
    return new MyPromise((onFulfilledNext, onRejectedNext) => {
      // 封装一个成功时执行的函数
      let fulfilled = value => {
        try {
          if (!isFunction(onFulfilled)) {
            onFulfilledNext(value)
          } else {
            let res = onFulfilled(value)
            if (res instanceof MyPromise) {
              // 如果当前回调函数返回 MyPromise 对象，必须等待其状态改变后在执行下一个回调
              res.then(onFulfilledNext, onRejectedNext)
            } else {
              // 否则会将返回结果直接作为参数，传入下一个 then 的回调函数，并立即执行下一个 then 的回调函数
              onFulfilledNext(res)
            }
          }
        } catch (err) {
          // 如果函数执行出错，新的 Promise 对象的状态为失败
          onRejectedNext(err)
        }
      }
      // 封装一个失败时执行的函数
      let rejected = error => {
        try {
          if (!isFunction(onRejected)) {
            onRejectedNext(error)
          } else {
            let res = onRejected(error)
            if (res instanceof MyPromise) {
              // 如果当前回调函数返回 MyPromise 对象，必须等待其状态改变后在执行下一个回调
              res.then(onFulfilledNext, onRejectedNext)
            } else {
              // 否则会将返回结果直接作为参数，传入下一个 then 的回调函数，并立即执行下一个 then 的回调函数
              onFulfilledNext(res)
            }
          }
        } catch (err) {
          // 如果函数执行出错，新的 Promise 对象的状态为失败
          onRejectedNext(err)
        }
      }
      switch (_status) {
        // 当状态为 pending 时，将 then 方法回调函数加入执行队列等待执行
        case PENDING:
          this._fulfilledQueues.push(fulfilled)
          this._rejectedQueues.push(rejected)
          break
        // 当状态已经改变时，立即执行对应的回调函数
        case FULFILLED:
          fulfilled(_value)
          break
        case REJECTED:
          rejected(_value)
          break
      }
    })
  }

  catch(onRejected) {
    return this.then(undefined, onRejected)
  }

  static resolve(value) {
    // 如果参数是 MyPromise 实例，直接返回这个实例
    if (value instanceof MyPromise) return value
    return new MyPromise(resolve => resolve(value))
  }

  static reject(value) {
    return new MyPromise((resolve, reject) => reject(value))
  }

  static all(list) {
    return new MyPromise((resolve, reject) => {
      // 返回值的集合
      let values = []
      let count = 0
      for (let [i, p] of list.entries()) {
        // 数组参数如果不是 MyPromise 实例，先调用 MyPromise.resolve
        this.resolve(p).then(res => {
          values[i] = res
          count++
          // 所有状态都变成 fulfilled 时返回的 MyPromise 状态就变成 fulfilled
          if (count === list.length) resolve(values)
        }, err => {
          // 有一个被 rejected 时返回的 MyPromise 状态就变成 rejected
          reject(err)
        })
      }
    })
  }

  static race(list) {
    return new MyPromise((resolve, reject) => {
      for (let p of list) {
        // 只要有一个实例率先改变状态，新的 MyPromise 的状态就跟着改变
        this.resolve(p).then(res => {
          resolve(res)
        }, err => {
          reject(err)
        })
      }
    })
  }

  finally(cb) {
    return this.then(
      value => MyPromise.resolve(cb()).then(() => value),
      reason => MyPromise.resolve(cb()).then(() => { throw reason })
    )
  }
}

Object.create()

关于 Object.create() 的详细用法可以参考 Object.create()，在了解过它的具体原理后，我们不难可以手动的来进行实现

if (!Object.create) {
  Object.create = function (o) {
    function F() { }
    F.prototype = o
    return new F()
  }
}

instanceof

核心原理就是原型链的向上查找，比如我们有 left 和 right 两个变量，首先判断 left 的 __proto__ 是不是等于 right.prototype，如果不等于再往上寻找 left.__proto__.__proto__ 直到 __proto__ 为 null

function myInstanceof(left, right) {
  if (typeof left !== 'object' || left === null) return false   // 基本数据类型直接返回 false
  let proto = Object.getPrototypeOf(left)                       // 获取参数的原型对象
  while (true) {
    if (proto == null) return false                             // 查找到尽头，还没找到，返回 false
    if (proto == right.prototype) return true                   // 找到相同的原型对象，返回 true
    proto = Object.getPrototypeOf(proto)
  }
}

'111' instanceof String                  // false
new String('111') instanceof String      // true

myInstanceof('111', String)              // false
myInstanceof(new String('111'), String)  // true

getOwnPropertyNames

需要注意的是，获取不到不可枚举的属性

if (typeof Object.getOwnPropertyNames !== 'function') {
  Object.getOwnPropertyNames = function (o) {
    if (o !== Object(o)) throw TypeError('Object.getOwnPropertyNames called on non-object')
    var props = [], p
    for (p in o) {
      if (Object.prototype.hasOwnProperty.call(o, p)) {
        props.push(p)
      }
    }
    return props
  }
}

map

这里我们根据规范当中的 Array.prototype.map(callbackfn[, thisArg]) 来模拟进行实现，如下图所示

Array.prototype.map = function (callbackFn, thisArg) {

  // 处理数组类型异常
  if (this === null || this === undefined) {                                
    throw new TypeError(`Cannot read property 'map' of null or undefined`)
  }

  // 处理回调类型异常
  if (Object.prototype.toString.call(callbackfn) != '[object Function]') {  
    throw new TypeError(callbackfn + ' is not a function')
  }

  let O = Object(this)                                    // 先转换为对象
  let T = thisArg
  let len = O.length >>> 0
  let A = new Array(len)
  for (let k = 0; k < len; k++) {
    if (k in O) {                                         // 如果没有找到就不处理，这样可以有效处理稀疏数组的情况
      let kValue = O[k]
      let mappedValue = callbackfn.call(T, KValue, k, O)  // 依次传入 this，当前项，当前索引，整个数组
      A[k] = mappedValue
    }
  }

  return A
}

关于上面的 length >>> 0，字面上的意思是指『右移 0 位』，但实际上是把前面的空位用 0 填充，这里的作用是保证 len 为数字且为整数，下面是 V8 源码当中的实现，可以对比一下

function ArrayMap(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this, 'Array.prototype.map')
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = TO_OBJECT(this)
  var length = TO_LENGTH(array.length)
  if (!IS_CALLABLE(f)) throw %make_type_error(kCalledNonCallable, f)
  var result = ArraySpeciesCreate(array, length)
  for (var i = 0; i < length; i++) {
    if (i in array) {
      var element = array[i]
      %CreateDataProperty(result, i, %_Call(f, receiver, element, i, array))
    }
  }
  return result
}

reduce

这里我们根据规范当中的 Array.prototype.reduce(callbackfn[, initialValue]) 来模拟进行实现，如下图所示

这里有两个比较重要的地方需要注意

初始值不传怎么处理
回调函数的参数有哪些，返回值如何处理

Array.prototype.reduce = function (callbackfn, initialValue) {
  if (this === null || this === undefined) {
    throw new TypeError(`Cannot read property 'reduce' of null or undefined`)
  }
  if (Object.prototype.toString.call(callbackfn) != '[object Function]') {
    throw new TypeError(callbackfn + ' is not a function')
  }
  let O = Object(this)
  let len = O.length >>> 0
  let k = 0
  let accumulator = initialValue
  if (accumulator === undefined) {
    for (; k < len; k++) {
      // 通过原型链查找跳过空项
      if (k in O) {
        accumulator = O[k]
        k++
        break
      }
    }
  }
  // 表示数组全为空
  if (k === len && accumulator === undefined) throw new Error(`Each element of the array is empty`)
  for (; k < len; k++) {
    if (k in O) {
      // 这里是核心
      accumulator = callbackfn.call(undefined, accumulator, O[k], k, O)
    }
  }
  return accumulator
}

下面是 V8 源码当中的实现，可以对比一下

function ArrayReduce(callback, current) {
  CHECK_OBJECT_COERCIBLE(this, 'Array.prototype.reduce')
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = TO_OBJECT(this)
  var length = TO_LENGTH(array.length)
  return InnerArrayReduce(callback, current, array, length, arguments.length)
}

function InnerArrayReduce(callback, current, array, length, argumentsLength) {
  if (!IS_CALLABLE(callback)) {
    throw %make_type_error(kCalledNonCallable, callback)
  }
  var i = 0
  find_initial: if (argumentsLength < 2) {
    for (; i < length; i++) {
      if (i in array) {
        current = array[i++]
        break find_initial
      }
    }
    throw %make_type_error(kReduceNoInitial)
  }
  for (; i < length; i++) {
    if (i in array) {
      var element = array[i]
      current = callback(current, element, i, array)
    }
  }
  return current
}

push 和 pop

因为这两个方法的实现十分类似，所以我们放到一起来进行介绍，还是和上面一样，我们先来看看规范当中的定义，见 Array.prototype.push() 和 Array.prototype.pop()，如下图所示

我们先来看看 push 的实现，其中的 2 ** 53 - 1 为 JavaScript 当中能表示的最大正整数

Array.prototype.push = function (...items) {
  let O = Object(this)
  let len = this.length >>> 0
  let argCount = items.length >>> 0
  if (len + argCount > 2 ** 53 - 1) {
    throw new TypeError(`The number of array is over the max value restricted`)
  }
  for (let i = 0; i < argCount; i++) {
    O[len + i] = items[i]
  }
  let newLength = len + argCount
  O.length = newLength
  return newLength
}

下面再来看看 pop 方法

Array.prototype.pop = function () {
  let O = Object(this)
  let len = this.length >>> 0
  if (len === 0) {
    O.length = 0
    return undefined
  }
  len--
  let value = O[len]
  delete O[len]
  O.length = len
  return value
}

filte

Array.prototype.filter(callbackfn[, thisArg]) 在规范当中的定义如下图所示

实现如下

Array.prototype.filter = function (callbackfn, thisArg) {
  if (this === null || this === undefined) {
    throw new TypeError(`Cannot read property 'filter' of null or undefined`)
  }
  if (Object.prototype.toString.call(callbackfn) != '[object Function]') {
    throw new TypeError(callbackfn + ' is not a function')
  }
  let O = Object(this)
  let len = O.length >>> 0
  let resLen = 0
  let res = []
  for (let i = 0; i < len; i++) {
    if (i in O) {
      let element = O[i]
      if (callbackfn.call(thisArg, O[i], i, O)) {
        res[resLen++] = element
      }
    }
  }
  return res
}

数组原生 API

这部分内容主要是源自于平时收集整理以及参考了一些这篇文章当中的内容整合而成，而且在实现方式上我们也不再去扩展 Array 构造函数上的方法了，直接使用函数的形式来进行实现，主要目的也是为了简单的了解其内部实现原理，当然只是功能上的实现，对于一些边界条件并没有考虑的十分完善，比较完善的方式可以参考上文当中依据规范所整理的相关方法的实现

forEach

这里需要注意的一点是，forEach 方法默认返回 undefined

function forEach(array, callback) {
  for (let i = 0; i < array.length; i++) {
    const value = array[i]
    callback(value, i, array)
  }
}

// 1 2 3
forEach([1, 2, 3], res => console.log(res))

map

与 forEach 方法不同的是，map 方法会给原数组中的每个元素都按顺序调用一次 callback 函数，callback 每次执行后的返回值（包括 undefined）组合起来形成一个新数组

function map(array, callback) {
  const result = []
  for (let i = 0; i < array.length; i++) {
    result[i] = callback(array[i], i, array)
  }

  return result
}

// [1, 4, 9]
map([1, 2, 3], res => res ** 2)

filter

过滤回调返回为 false 的值，每个值都保存在一个新的数组中，然后返回，这里用到了我们在下面将会介绍的 push 方法

function push(array, ...values) {
  const { length: arrayLength } = array
  const { length: valuesLength } = values
  for (let i = 0; i < valuesLength; i++) {
    array[arrayLength + i] = values[i]
  }
  return array.length
}

function filter(array, callback) {
  const result = []
  for (let i = 0; i < array.length; i++) {
    const value = array[i]
    if (callback(value, i, array)) {
      push(result, value)
    }
  }
  return result
}

// [2, 3]
filter([1, 2, 3], res => res >= 2)

reduce

reduce() 方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值，该方法接受四个参数

初始值（或者上一次回调函数的返回值）
当前元素值
当前索引
调用 reduce() 的数组

function reduce(array, callback, initValue) {
  if (array.length === 0) throw new Error(`Uncaught TypeError: Reduce of empty array`)
  for (let i = 0; i < array.length; i++) {
    if (typeof initValue === 'undefined') {
      initValue = callback(array[i], array[i + 1], i + 1, array)
      ++i
    } else {
      initValue = callback(initValue, array[i], i, array)
    }
  }
  return initValue
}

// 10
reduce([1, 2, 3, 4], (prev, next) => prev += next)

// 20
reduce([1, 2, 3, 4], (prev, next) => prev += next, 10)

// 5
reduce([1, 2, 3, 4], (prev, next, i, array) => {
  if (i === array.length - 1) {
    return (prev + next) / 2
  }
  return prev + next
})

每次迭代，reduce 方法都将回调的结果保存在我们的累加器（initValue）中，然后在下一个迭代中使用

这里有几个需要注意的地方，一个是 ++i 这一步操作，因为当没有传递初始值的时候，当我们手动赋予初始值的时候，为了不重复计算初始元素，将 i 指向下一步，另外就是如果数组为空，是会抛出 TypeError

findIndex

findIndex 方法对数组中的每个数组索引执行一次 callback 函数，直到找到第一个 callback 函数返回真实值（强制为 true）的值，如果找到这样的元素，findIndex 会立即返回该元素的索引，如果回调从不返回真值，或者数组的 length 为 0，则返回 -1

function findIndex(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (callback(array[i], i, array)) {
      return i
    }
  }
  return -1
}

// 1
findIndex(['a', 'b', 'c'], res => res === 'b')

find

其实 find 与 findIndex 的唯一区别在于它返回的是实际值，而不是索引，而我们之前已经实现了 findIndex 方法，所以稍微调整一下就行，注意现在的返回值是 undefined 了

function find(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (callback(array[i], i, array)) {
      return array[i]
    }
  }
  return undefined
}

// b
find(['a', 'b', 'c'], res => res === 'b')

// undefined
find(['a', 'b', 'c'], res => res === 'd')

indexOf

indexOf 是获取给定值索引的另一种方法，这里我们可以直接使用前面实现的 findIndex

function findIndex(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (callback(array[i], i, array)) {
      return i
    }
  }
  return -1
}

function indexOf(array, searchedValue) {
  return findIndex(array, value => value === searchedValue)
}

indexOf([1, 2, 3], 2)

lastIndexOf

lastIndexOf 的工作方式与 indexOf 相同，只是 lastIndexOf 方法返回的是指定元素在数组中的最后一个的索引，如果不存在同样返回 -1

function lastIndexOf(array, searchedValue) {
  for (let i = array.length - 1; i > -1; i--) {
    if (array[i] === searchedValue) {
      return i
    }
  }
  return -1
}

// 2
lastIndexOf([2, 3, 2], 2)

every

every() 方法测试一个数组内的所有元素是否都能通过某个指定函数的测试，它返回一个布尔值

function every(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (!callback(array[i], i, array)) {
      return false
    }
  }
  return true
}

// false
every([1, 2, 3], res => res === 2)

// true
every([1, 2, 3], res => res > 0)

我们为数组当中的每个值都执行回调，如果在任何时候返回 false，则退出循环，并且整个方法返回false，如果循环终止而没有进入到 if 语句里面，则说明条件都成立，返回 true

some

some 方法与 every 刚好相反，即只要其中一个为 true 就会返回 true

function some(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (callback(array[i], i, array)) {
      return true
    }
  }
  return false
}

// true
some([1, 2, 3], res => res === 2)

includes

includes 方法的工作方式类似于 some 方法，但是 includes 不使用回调，而是提供一个参数值来比较元素，所以我们可以借住上面实现的 some 方法来进行实现

function some(array, callback) {
  for (let i = 0; i < array.length; i++) {
    if (callback(array[i], i, array)) {
      return true
    }
  }
  return false
}

function includes(array, searchedValue) {
  return some(array, val => val === searchedValue)
}

// true
includes([1, 2, 3], 2)

// false
includes([1, 2, 3], 4)

concat

concat() 方法用于合并两个或多个数组，此方法不会更改现有数组，而是返回一个新数组，同样这里我们也使用到了 push 方法

function push(array, ...values) {
  const { length: arrayLength } = array
  const { length: valuesLength } = values
  for (let i = 0; i < valuesLength; i++) {
    array[arrayLength + i] = values[i]
  }
  return array.length
}

function concat(array, ...values) {
  const result = [...array]
  for (let i = 0; i < values.length; i++) {
    if (Array.isArray(values[i])) {
      push(result, ...values[i])
    } else {
      push(result, values[i])
    }
  }
  return result
}

// [1, 2, 3, 4]
concat([1, 2, 3], 4)

// [1, 2, 3, 4, 5, 6]
concat([1, 2, 3], [4, 5, 6])

concat 将数组作为第一个参数，并将未指定个数的值作为第二个参数，首先通过复制传入的数组创建 result 数组，然后遍历 values 检查需要添加的值是否是数组，如果是，则使用展开操作符将其值附加到结果数组中，否则就直接添加

join

join() 方法可以将数组转化为一个字符串，而元素是通过指定的分隔符进行分隔的

function join(array, joinWith) {
  if (array.length <= 1) return array[0] ? ('' + array[0]) : ''
  let result = array[0]
  for (let i = 1; i < array.length; i++) {
    result += joinWith + array[i]
  }
  return result
}

// '1-2-3'
join([1, 2, 3], '-')

// '1'
join([1], '-')

// ''
join([], '-')

reverse

reverse() 方法将数组中元素的位置颠倒，并返回该数组，该方法会改变原数组

function reverse(array) {
  const result = []
  const lastIndex = array.length - 1
  for (let i = lastIndex; i > -1; i--) {
    result[lastIndex - i] = array[i]
  }
  return result
}

// [3, 2, 1]
reverse([1, 2, 3])

我们首先定义一个空数组，并将数组的最后一个索引保存为变量（lastIndex），接着反向遍历数组，将每个值保存在结果 result 中的 [lastIndex - i] 的位置，然后返回 result 数组

如果不想计算保存位置的话也可以在反向遍历的过程当中将当前值 push 到 result 数组当中

push

这个方法我们在上面曾多次用到，它的实现方式很简单，只需要将要添加的元素依次放到数组的最后即可，不会改变原有数组元素的索引，返回值为当中数组的长度，这里需要注意的是，数组的长度每次都需要从新获取

function push(array, ...values) {
  const { length: arrayLength } = array
  const { length: valuesLength } = values
  for (let i = 0; i < valuesLength; i++) {
    array[arrayLength + i] = values[i]
  }
  return array.length
}

push([1, 2, 3], 4, 5)

unshift

unshift() 方法将一个或多个元素添加到数组的开头，并返回该数组的新长度，该方法会修改原有数组

function unshift(array, ...values) {
  const newArray = [...values, ...array]
  for (let i = 0; i < newArray.length; i++) {
    array[i] = newArray[i]
  }
  return newArray.length
}

unshift([1, 2, 3], 4)

shift

shift() 方法从数组中删除第一个元素，并返回该元素的值，此方法更改数组的长度

function shift(array) {
  const firstValue = array[0]
  for (let i = 1; i < array.length; i++) {
    array[i - 1] = array[i]
  }
  array.length = array.length - 1
  return firstValue
}

// 1
shift([1, 2, 3])

我们首先保存需要返回的第一个值，然后从位置 1 开始遍历数组，并且将遍历得到的值从 0 开始覆盖到原数组当中，完成遍历后，更新数组的长度并返回初始值

pop

pop() 方法会从数组中删除最后一个元素，并返回该元素的值，此方法更改数组的长度，这个方法实现起来比较容易，我们只需将元数组的长度减少 1，从而删除最后一个值

function pop(array) {
  const returnValue = array[array.length - 1]
  array.length = array.length - 1
  return returnValue
}

// 3
pop([1, 2, 3])

fill

fill() 方法用一个固定值填充一个数组中从起始索引到终止索引内的全部元素，但是不包括终止索引，所以这里的 last 为 array.length 而不是 array.length - 1

function fill(array, value, start = 0, last = array.length) {
  for (let i = start; i < last; i++) {
    array[i] = value
  }
  return array
}

// [5, 5, 5, 5]
fill([1, 2, 3, 4], 5)

// [1, 5, 3, 4]
fill([1, 2, 3, 4], 5, 1, 2)

节点遍历

// 原理就是遍历 elem 节点的前面，直到返回第一个 nodeType 为 1 的节点
function getRealPrev(elem) {
  var o = elem
  // 循环遍历，将循环的结果再次赋予 o，依次向上查询
  while (o = o.previousSibling) {
    if (o.nodeType == 1) {
      return o
    }
    return null
  }
}

// [1, 2, 3, 4, 5, 6, 7]
flatten([1, [2, 3, [4, [5, 6, 7]]]])

// 原理就是遍历 elem 节点的后面，直到返回第一个 nodeType 为 1 的节点
function getRealNext(elem) {
  var o = elem
  // 循环遍历，将循环的结果再次赋予 o，依次向下查询
  while (o = o.nextSibling) {
    if (o.nodeType == 1) {
      return o
    }
    return null
  }
}

// [1, 2, 3, 4, 5, 6, 7]
[...flatten([1, [2, 3, [4, [5, 6, 7]]]])]

prevAll

// 原理就是遍历 elem 节点的前面，直到返回第一个 nodeType 为 1 的节点
function getRealprevAll(elem) {
  var o = elem
  var result = []
  // 循环遍历，将循环的结果再次赋予 o，依次向上查询，如果不存在上一个节点，则会返回 null，便自动停止循环
  while (o = o.previousSibling) {
    if (o.nodeType == 1) {
      result.unshift(o)
    }
    return result
  }
}

nextAll

// 原理就是遍历 elem 节点的后面，直到返回第一个 nodeType 为 1 的节点
function getRealnextAll(elem) {
  var o = elem
  var result = []
  // 循环遍历，将循环的结果再次赋予 o，依次向下查询，如果不存在下一个节点，则会返回 null，便自动停止循环
  while (o = o.nextSibling) {
    if (o.nodeType == 1) {
      result.push(o)
    }
    return result
  }
}

常见工具函数

短横变驼峰

var f = function (s) {
  return s.replace(/-\w/g, function (x) {
    console.log(x)
    return x.slice(1).toUpperCase()
  })
}

f('border-right-color')

千位分隔符

function commafy(num) {
  return num && num
    .toString()
    // 也可以使用 /\B(?=(\d{3})+$)/g
    .replace(/(\d)(?=(\d{3})+\.)/g, function ($0, $1) {
      return $1 + ','
    })
}

commafy(1234567.90)

解析 URL

const getURLParameters = url =>
  (url.match(/([^?=&]+)(=([^&]*))/g) || []).reduce(
    (a, v) => ((a[v.slice(0, v.indexOf('='))] = v.slice(v.indexOf('=') + 1)), a),
    {}
  )

getURLParameters('https://www.baidu.com?id=123&name=zhangsan')

上面这个示例可以应对大多正常使用的情况，但是当然也会存在一些比较特殊的情况，比如下面这个 url

1	let url = 'http://www.example.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'

要求输出的结果是下面这样的

{ 
  user: 'anonymous',
  id: [123, 456],
  city: '北京',
  enabled: true,
}

具体规则为

重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
中文需解码
未指定值的 key 约定为 true

下面我们来看如何实现

function parseParam(url) {
  const paramsStr = /.+\?(.+)$/.exec(url)[1]              // 将 ? 后面的字符串取出来
  const paramsArr = paramsStr.split('&')                  // 将字符串以 & 分割后存到数组中
  let paramsObj = {}
  paramsArr.forEach(param => {                            // 将 params 存到对象中
    if (/=/.test(param)) {                                // 处理有 value 的参数
      let [key, val] = param.split('=')                   // 分割 key 和 value
      val = decodeURIComponent(val)                       // 解码
      val = /^\d+$/.test(val) ? parseFloat(val) : val     // 判断是否转为数字
      if (paramsObj.hasOwnProperty(key)) {                // 如果对象有 key，则添加一个值
        paramsObj[key] = [].concat(paramsObj[key], val)
      } else {                                            // 如果对象没有这个 key，创建 key 并设置值
        paramsObj[key] = val
      }
    } else {                                              // 处理没有 value 的参数
      paramsObj[param] = true
    }
  })
  return paramsObj                                        // 返回最终结果
}

数组去重

这里需要注意的是，我们默认传递的参数都是数组对象，所以也就省掉了针对入参的判断，在这里我们只关心核心实现部分

第一种，也是我们可能想到的最为直白的方式，那就是使用双层循环（while 也可），其缺点是其复杂度为 O(n^2)，如果数组过大，将会影响性能，但是它也有好处，就是兼容性好，原理是先定义一个包含原始数组第一个元素的数组，然后遍历原始数组，将原始数组中的每个元素与新数组中的每个元素进行比对，如果不重复则添加到新数组中，最后返回新数组

function unique(arr) {
  let res = [arr[0]]
  for (let i = 1; i < arr.length; i++) {
    let flag = true
    for (let j = 0; j < res.length; j++) {
      if (arr[i] === res[j]) {
        flag = false
        break
      }
    }
    if (flag) {
      res.push(arr[i])
    }
  }
  return res
}

第二种方法，使用 indexOf 或者 includes，因为原理是一样的，这里我们就以 indexOf 为例来进行介绍了，indexOf 的用法有两种

一种是首先定义一个空数组，然后调用 indexOf 方法对原来的数组进行遍历判断，如果元素不在新定义的数组中，则将其添加进去，最后将数组返回
第二种就是检测元素在数组中第一次出现的位置是否和元素现在的位置相等，如果不等则说明该元素是重复元素

// 第一种方式
function unique(arr) {
  let res = []
  for (let i = 0; i < arr.length; i++) {
    // 或者使用 if (!res.includes(arr[i])) { }
    if (res.indexOf(arr[i]) === -1) {
      res.push(arr[i])
    }
  }
  return res
}

// 第二种方式
function unique(arr) {
  return Array.prototype.filter.call(arr, function (item, index) {
    return arr.indexOf(item) === index
  })
}

第三种方法，使用 reduce，原理是利用 reduce 的累加原理，因为初始值为 []，所以在添加前先行判断，如果当前数组中没有该元素，再将其放入其中

function unique(arr) {
  return arr.reduce(function (pre, cur) {
    return pre.includes(cur) ? pre : [...pre, cur]
  }, [])
}

第四种方法，相邻元素去重，这种方法首先调用了数组的排序方法 sort()，相同的值就会被排在一起，然后我们就可以只判断当前元素与上一个元素是否相同，但是这个方法存在缺陷，即 sort() 排序的结果并非十分准确

function unique(arr) {
  arr = arr.sort()
  let res = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      res.push(arr[i])
    }
  }
  return res
}

第五种方法，利用对象属性去重，也就是所谓的对象键值对法，原理是遍历数组，将数组中的值设为对象的属性，并给该属性赋初始值 1，每出现一次，对应的属性值增加 1，这样属性值对应的就是该元素出现的次数了（这个方法也可以用来统计字符串出现的次数）

// 方式一
function unique(arr) {
  let res = [], obj = {}
  for (let i = 0; i < arr.length; i++) {
    if (!obj[arr[i]]) {
      res.push(arr[i])
      obj[arr[i]] = 1
    } else {
      obj[arr[i]]++
    }
  }
  return res
}

// 方式二，针对处理 [1, 2, 1, 1, '1'] 这样的数组，可以使用 typeof item + item 拼成字符串作为 key 值来避免这个问题
function unique(arr) {
  var obj = {}
  return arr.filter(function (item, index, array) {
    return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
  })
}

第六种方法，解构赋值去重，ES6 提供了新的数据结构 Set，它类似于数组，但是成员的值都是唯一的

// 利用 Set
var unique = arr => [...new Set(arr)]

// 也可以使用 Map，原理也是利用对象属性
function unique(arr) {
  const map = new Map()
  return arr.filter((a) => !map.has(a) && map.set(a, 1))
}

最后我们再来通过一个特殊的数组依次来看看上面各种方法处理后的结果，做一个简单的对比

1	var array = [1, 1, '1', '1', null, null, undefined, undefined, new String('1'), new String('1'), /a/, /a/, NaN, NaN]

针对上面的数组，上述去重方法结果如下，可以根据实际场景选择使用

方法	结果	说明
双重 `for` 循环	`[1, '1', null, undefined, String, String, /a/, /a/, NaN, NaN]`	对象和 `NaN` 不去重
单纯的 `indexOf`	`[1, '1', null, undefined, String, String, /a/, /a/, NaN, NaN]`	对象和 `NaN` 不去重
`reduce`	`[1, '1', null, undefined, String, String, /a/, /a/, NaN]`	对象不去重 `NaN` 去重
`filter` + `indexOf`	`[1, '1', null, undefined, String, String, /a/, /a/]`	对象不去重 `NaN` 会被忽略掉
相邻元素去重（`sort`）	`[/a/, /a/, '1', 1, String, 1, String, NaN, NaN, null, undefined]`	对象和 `NaN` 不去重数字 `1` 也不去重
对象键值对法	`[1, null, undefined, /a/, NaN]`	无法区分数字 `1` 和 `'1'`
优化后的对象键值对法	`[1, '1', null, undefined, String, /a/, NaN]`	全部去重
`Set` 和 `Map`	`[1, '1', null, undefined, String, String, /a/, /a/, NaN]`	对象不去重 `NaN` 去重

最后一种特殊情况，如果不是单纯的数组，而是数组对象的话，则可以使用 reduce 来进行处理

function unique(arr, initialValue, id) {
  let hash = {}
  return arr.reduce((item, next) => {
    hash[next.id] ? '' : hash[next.id] = true && item.push(next)
    return item
  }, initialValue)
}

let arr = [{ 'id': 1 }, { 'id': 2 }, { 'id': 2 }, { 'id': 3 }]
newArr = unique(arr, [], 'id')

数组扁平化

其实这个功能在 ES6 当中已经实现了，也就是 flat() 方法，它会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回，先来看看如何使用

// [1, 2, 3, 4]
[1, 2, [3, 4]].flat()

// [1, 2, 3, 4, [5, 6]]
[1, 2, [3, 4, [5, 6]]].flat()

// [1, 2, 3, 4, 5, 6]
[1, 2, [3, 4, [5, 6]]].flat(2)

// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]].flat(Infinity)

同时需要注意的是，flat() 方法会移除数组中的空项

1 2	// [1, 2, 4, 5] [1, 2, , 4, 5].flat()

我们先来看看带参数模式的如何实现，一种比较常见的方式是使用 reduce + concat

function flatten(arr, depth = 1) {
  return depth > 0
    ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatten(val, depth - 1) : val), [])
    : arr
}

// [1, 2, 3, 1, 2, 3, 4, 2, 3, 4]
flatten([1, 2, 3, [1, 2, 3, 4, [2, 3, 4]]], Infinity)

// [1, 2, 3, 1, 2, 3, 4, [2, 3, 4]]
flatten([1, 2, 3, [1, 2, 3, 4, [2, 3, 4]]], 1)

首先我们检查 depth 参数是否大于 0，如果不是，则直接返回该数组，否则调用 reduce 函数，利用 concat 方法将数组的每个值扁平，如果扁平一次后还是数组的话继续递归调用，这里需要注意的是我们每次递归都会递减 depth 参数，以免造成无限循环

另外还可以使用 forEach 和 for-of，不过原理是类似的，都是利用递归来进行扁平化处理

// forEach 遍历数组会自动跳过空元素
const eachFlat = (arr = [], depth = 1) => {
  const result = []                             // 缓存递归结果
  (function flat(arr, depth) {                  // 开始递归
    arr.forEach((item) => {                     // forEach 会自动去除数组空位
      if (Array.isArray(item) && depth > 0) {   // 控制递归深度
        flat(item, depth - 1)                   // 递归数组
      } else {
        result.push(item)                       // 缓存元素
      }
    })
  })(arr, depth)
  return result                                 // 返回递归结果
}

// for-of 循环不能去除数组空位，需要手动去除
const forFlat = (arr = [], depth = 1) => {
  const result = []
  (function flat(arr, depth) {
    for (let item of arr) {
      if (Array.isArray(item) && depth > 0) {
        flat(item, depth - 1)
      } else {
        item !== void 0 && result.push(item)    // 去除空元素，添加非 undefined 元素
      }
    }
  })(arr, depth)
  return result
}

不过在平常开发过程当中，更为常见的用法是直接将多维数组降维至一维数组，通常不会去考虑第二个参数，在这种情况下我们可以考虑使用下面几种比较简单的方式，首先来看一个比较局限的方法，如果数组当中的元素都是纯数字的话，那么我们可以考虑使用 toString() 方法，但是如果数组是 [1, '1', 2, '2'] 的话，这种方法就会产生错误的结果，所以使用的场景有限

function flatten(arr) {
  return arr.toString().split(',').map(item => Number(item))
}

// [1, 2, 3, 4, 5, 6, 7]
flatten([1, [2, 3, [4, [5, 6, 7]]]])

另外也可以使用和上面一样的递归方式，不过可以省略 reduce 而是借用 Array.some() 方法，代码十分简单

function flatten(arr) {
  while (arr.some(Array.isArray)) {
    arr = [].concat(...arr)
  }
  return arr
}

// [1, 2, 3, 4, 5, 6, 7]
flatten([1, [2, 3, [4, [5, 6, 7]]]])

第三种方式，可以使用使用堆栈达到无递归数组扁平化，但是需要注意的是深度的控制比较低效，因为需要检查每一个值的深度

function flatten(array) {
  const stack = [...array]
  const res = []
  while (stack.length) {
    const next = stack.pop()     // 使用 pop 从 stack 中取出并移除值
    if (Array.isArray(next)) {
      stack.push(...next)        // 使用 push 送回内层数组中的元素，不会改动原始输入
    } else {
      res.push(next)
    }
  }
  return res.reverse()           // 反转恢复原数组的顺序
}

// [1, 2, 3, 4, 5, 6, 7]
flatten([1, [2, 3, [4, [5, 6, 7]]]])

另外还可以使用 Generator 函数来进行实现，如下

function* flatten(array) {
  for (const item of array) {
    if (Array.isArray(item)) {
      yield* flatten(item)
    } else {
      yield item
    }
  }
}

// [1, 2, 3, 4, 5, 6, 7]
[...flatten([1, [2, 3, [4, [5, 6, 7]]]])]

最后我们再来看一种比较另类的方式，那就是使用正则进行匹配，原理就是将 [ 和 ] 替换成 ''，然后在还原为数组

const arr = [1, [2, 3, [4, [5, 6, 7]]]]

// [1, 2, 3, 4, 5, 6, 7]
JSON.parse(`[${JSON.stringify(arr).replace(/(\[|\])/g, '')}]`)

对象扁平化

目的是实现以键的路径扁平化对象，常见的解决方式是使用『递归』，主要步骤有以下几步

利用 Object.keys(obj) 联合 Array.prototype.reduce()，以每片叶子节点转换为扁平的路径节点
如果键的值是一个对象，则函数使用调用适当的自身 prefix 以创建路径 Object.assign()
否则，它将适当的前缀键值对添加到累加器对象
prefix 除非希望每个键都有一个前缀，否则应始终省略第二个参数

const flattenObject = (obj, prefix = '') =>
  Object.keys(obj).reduce((acc, k) => {
    const pre = prefix.length ? prefix + '.' : ''
    if (typeof obj[k] === 'object') Object.assign(acc, flattenObject(obj[k], pre + k))
    else acc[pre + k] = obj[k]
    return acc
  }, {})

// {a.b.c: 1, d: 1}
flattenObject({ a: { b: { c: 1 } }, d: 1 })

我们也可以以键的路径展开对象，也就是与上面执行相反的操作，通常用在 Tree 组件或复杂表单时取值比较方便

const unflattenObject = obj =>
  Object.keys(obj).reduce((acc, k) => {
    if (k.indexOf('.') !== -1) {
      const keys = k.split('.')
      Object.assign(
        acc,
        JSON.parse(
          '{' +
          keys.map((v, i) => (i !== keys.length - 1 ? `"${v}":{` : `"${v}":`)).join('') +
          obj[k] +
          '}'.repeat(keys.length)
        )
      )
    } else acc[k] = obj[k]
    return acc
  }, {})

// { a: { b: { c: 1 } }, d: 1 }
unflattenObject({ 'a.b.c': 1, d: 1 })

字符串去重

第一种方式，常规的 for 遍历

function unique1(str) {
  var newStr = ''
  var flag
  for (var i = 0; i < str.length; i++) {
    flag = 1
    for (var j = 0; j < newStr.length; j++) {
      if (str[i] == newStr[j]) {
        flag = 0
        break
      }
    }
    if (flag) newStr += str[i]
  }
  return newStr
}

第二种，使用 indexOf

function unique2(str) {
  var newStr = ''
  for (var i = 0; i < str.length; i++) {
    if (newStr.indexOf(str[i]) == -1) {
      newStr += str[i]
    }
  }
  return newStr
}

第三种，与上面第二种类似，不过判断方式换成了 search

function unique3(str) {
  var newStr = ''
  for (var i = 0; i < str.length; i++) {
    if (newStr.search(str[i]) == -1)
      newStr += str[i]

  }
  return newStr
}

第四种方式，利用对象属性，推荐使用这种方式

function unique4(str) {
  var obj = {}
  var newStr = ''
  for (var i = 0; i < str.length; i++) {
    if (!obj[str[i]]) {
      newStr += str[i]
      obj[str[i]] = 1
    }
  }
  return newStr
}

生成区间随机数，并排序

var arr = []

var randomNum = function (n, m) {
  return parseInt(Math.random() * (m - n) + n)
}

for (var i = 0; i < 20; i++) {
  arr.push(randomNum(40, 80))
}

// 排序
console.log(arr.sort(function (a, b) { return a - b }))

// 乱序
console.log(arr.sort(function () { return 0.5 - Math.random() }))

这里关于乱序需要说明一下，因为这里涉及到了 sort() 方法，所以上面的结果是存在一定误差的，我们可以来测试一下，比如下面这里例子，将 [1, 2, 3, 4, 5] 乱序 10 万次，计算乱序后的数组的最后一个元素是 1、2、3、4、5 的次数分别是多少

var times = [0, 0, 0, 0, 0]

for (var i = 0; i < 100000; i++) {
  let arr = [1, 2, 3, 4, 5]
  arr.sort(() => Math.random() - 0.5)
  times[arr[4] - 1]++
}

console.log(times)  // [25028, 6975, 21233, 18538, 28226]

根据结果我们可以发现，排序后的各元素明显分布不平均，所以说这样的算法是存在一定问题的，而具体原因就是因为 sort() 方法而导致的，但是在这里关于为什么会产生这样结果的原因我们就不详细展开了，具体可以参考 JavaScript 专题之解读 V8 排序源码这篇文章，在这里我们只来看看如何解决这样的问题

针对于乱序的问题，通常我们可以采用 Fisher-Yates 的算法来对数组中的元素进行随机选择，主要有以下两种方式

sampleSize，在指定数组中获取指定长度的随机数，它的原理是随机抽选对换位置（余下的只在剩余位置交换）

const sampleSize = ([...arr], n = 1) => {
  let m = arr.length
  while (m) {
    const i = Math.floor(Math.random() * m--);
    [arr[m], arr[i]] = [arr[i], arr[m]]
  }
  return arr.slice(0, n)
}

sampleSize([1, 2, 3], 2)  // [3, 1]
sampleSize([1, 2, 3], 4)  // [2, 3, 1]

shuffle，洗牌数组，它的原理是随机抽选，抽到一个出列一个

const shuffle = ([...arr]) => {
  let m = arr.length
  while (m) {
    const i = Math.floor(Math.random() * m--);
    [arr[m], arr[i]] = [arr[i], arr[m]]
  }
  return arr
}

// [2, 3, 1]
shuffle([1, 2, 3])

我们可以来测试一下

var times = 10000
var res = {}

for (var i = 0; i < times; i++) {
  var arr = shuffle([1, 2, 3])
  var key = JSON.stringify(arr)
  res[key] ? res[key]++ : res[key] = 1
}

// 转换成百分比
for (var key in res) {
  res[key] = res[key] / times * 100 + '%'
}

console.log(res)
// {
//   [1,2,3]: '16.12%',
//   [1,3,2]: '16.76%',
//   [2,1,3]: '16.78%',
//   [2,3,1]: '16.61%',
//   [3,1,2]: '16.57%',
//   [3,2,1]: '17.16%',
// }

取数组的并集，交集和差集

// 这里有一些需要注意的地方
// 如果两个数组 A 和 B 当中没有重复的元素，以下三种都是可以正常实现的
// 如果数组当中有重复的元素，需要使用 ES6 当中的 Set 数据结构
// 如果数组当中包含 NaN，可以考虑在结尾处添加 .filter(v => !isNaN(v)) 过滤掉即可
let a = [1, 2, 3, 4]
let b = [2, 3, 4, 5, 6]

// ES7 并集
a.concat(b.filter(v => !a.includes(v)))                                       // [1, 2, 3, 4]

// ES7 交集
a.filter(v => b.includes(v))                                                  // [2, 3]

// ES7 差集
a.concat(b).filter(v => !a.includes(v) || !b.includes(v))                     // [1, 4]

// ------------

let aSet = new Set(a)
let bSet = new Set(b)

// ES6 并集
Array.from(new Set(a.concat(b)))                                              // [1, 2, 3, 4]

// ES6 交集
Array.from(new Set(a.filter(v => bSet.has(v))))                               // [2, 3]

// ES6 差集
Array.from(new Set(a.concat(b).filter(v => !aSet.has(v) || !bSet.has(v))))    // [1, 4]

// ------------

// ES5 并集
a.concat(b.filter(v => a.indexOf(v) === -1))                                  // [1, 2, 3, 4]

// ES5 交集
a.filter(v => b.indexOf(v) !== -1)                                            // [2, 3]

// ES5 差集
a.filter(v => b.indexOf(v) === -1).concat(b.filter(v => a.indexOf(v) === -1))  // [1, 4]

字符串包含查找

虽然有 API 可以实现，但是我们这里使用最基本的遍历来实现，要求是判断字符串 a 是否被包含在字符串 b 中，并返回第一次出现的位置，如果找不到则返回 -1

function isContain(a, b) {
  for (let i in b) {
    if (a[0] === b[i]) {
      let tmp = true
      for (let j in a) {
        if (a[j] !== b[~~i + ~~j]) {
          tmp = false
        }
      }
      if (tmp) {
        return i
      }
    }
  }
  return - 1
}

var a = '355', b = '12354355'

// 5
isContain(a, b)

这里有一个需要注意的地方就是其中的 i 和 j 是字符串，所以需要我们将其转换为数字

统计数组中每一项出现的次数

1	[5, 5, 4, 3, 2, 1, 4, 5, 5, 4, 3, 2, 2, 1].reduce((ad, ap) => (ad[ap] = ++ad[ap] \|\| 1, ad), {})

寻找字符串中出现最多的字符和个数

function findLength(str, num = 0, char = '') {
  str.split('').sort().join('').replace(/(\w)\1+/g, ($0, $1) => {
    if (num < $0.length) {
      num = $0.length
      char = $1
    }
  })
  console.log(`字符最多的是${char}，出现了${num}次`)
}

findLength('abcabcabcbbccccc')

寻找字符串中出现次数最少的、并且首次出现位置最前的字符

要求实现一个算法，寻找字符串中出现次数最少的、并且首次出现位置最前的字符，如 cbaacfdeaebb，方法有很多种，我们一个一个来看

方法一，利用 hash table，缺点是 Object.keys() 不能保证顺序，所以存在风险

var o = [].reduce.call('cbaacfdeaebb', function (p, n) {
  return p[n] = (p[n] || 0) + 1, p
}, {})

var s = Object.keys(o).reduce(function (p, n) {
  return o[p] <= o[n] ? p : n
})

console.log(s, o[s])

方法二，引入了 index 来解决顺序问题

const all = 'cbaacfdeaebb'.split('')
  .reduce((all, ch, i) => {
    const m = all[ch] || (all[ch] = { ch: ch, index: i, count: 0 })
    m.count++
    return all
  }, {})

const theOne = Object.keys(all)
  .map(ch => all[ch])
  .reduce((min, t) => min.count === t.count
    ? (min.index > t.index ? t : min)
    : (min.count > t.count ? t : min))

console.log(`${theOne.ch}: ${theOne.count}`)

方法三，利用数组代替 hash table，解决了顺序问题，但是 Array.sort() 并不一定是稳定的，风险可能更大

function findFirstChar(string) {
  const desc = []

  [...string].forEach((char, index) => {
    const item = desc.find(item => item.char === char)
    item ? item.count++ : desc.push({ char, index, count: 1 })
  })

  return desc.sort((a, b) => a.count - b.count)[0]
}

方法四，使用 Object.values，但是目前还是草案

const less = (x, y) => (x.count <= y.count && x.first < y.first) ? x : y

function firstSingle(string) {
  let map = {}

  string.split('')
    .forEach((char, index) => {
      map[char] ? map[char].count++ : map[char] = { count: 1, first: index, char }
    })

  return Object.values(map).reduce(less).char
}

方法五，代码简短，但是执行效率不是很高

var str = 'cbaacfdeaebb'

var result = [...new Set(str)]
  .map(el => ({ el, len: str.split(el).length }))
  .reduce((a, e) => (a.len > e.len ? e : a))
  .el

生成指定长度数组

比如生成指定内容为 [0, 1, 2, 3 ... N - 1] 的数组

// 方法一，ES5
Array.apply(null, { length: N }).map(function (value, index) {
  return index
})

// 方法二，ES6
Array.from(new Array(N), (v, i) => i)

// 方法三
Array.from(Array(N).keys())

// 方法四
[...Array(N).keys()]

// 方法五
Object.keys(Array(N).join().split(',')).map(v => Number(v))

// 方法六
Object.keys(Array(N).fill()).map(v => Number(v))

// 方法七
Object.keys(Array.apply(null, { length: 100 })).map(v => Number(v))

// 方法八
Array(N).fill().map((v, i) => i)

// 方法九
Array.prototype.recursion = function (length) {
  if (this.length === length) {
    return this
  }
  this.push(this.length)
  this.recursion(length)
}

arr = []
arr.recursion(100)

动态规划

『动态规划』的特点就是通过全局规划，将大问题分割成小问题来取最优解，来看一个最少硬币找零的经典示例，在美国总共有以下面额的硬币，d1 = 1，d2 = 5，d3 = 10，d4 = 25，而如果我们需要找 36 美分的零钱的话，就可以用 1 个 25 美分、1 个 10 美分和 1 个便士（1 美分）

class MinCoinChange {
  constructor(coins) {
    this.coins = coins
    this.cache = {}
  }
  makeChange(amount) {
    if (!amount) return []
    if (this.cache[amount]) return this.cache[amount]
    let min = [], newMin, newAmount
    this.coins.forEach(coin => {
      newAmount = amount - coin
      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount)
      }
      if (newAmount >= 0 &&
        (newMin.length < min.length - 1 || !min.length) &&
        (newMin.length || !newAmount)) {
        min = [coin].concat(newMin)
      }
    })
    return (this.cache[amount] = min)
  }
}

const rninCoinChange = new MinCoinChange([1, 5, 10, 25])
rninCoinChange.makeChange(36)  // [1, 10, 25]

const minCoinChange2 = new MinCoinChange([1, 3, 4])
minCoinChange2.makeChange(6)   // [3, 3]

贪心算法

我们下面再来看看使用『贪心算法』来解决上面的找硬币问题

function MinCoinChange(coins) {
  var coins = coins
  this.makeChange = function (amount) {
    var change = [], total = 0
    for (var i = coins.length; i >= 0; i--) {
      var coin = coins[i]
      while (total + coin <= amount) {
        change.push(coin)
        total += coin
      }
    }
    return change
  }
}

var minCoinChange = new MinCoinChange([1, 5, 10, 25])

minCoinChange.makeChange(36)  // [25, 10, 1]
minCoinChange.makeChange(34)  // [25, 5, 1, 1, 1, 1]
minCoinChange.makeChange(6)   // [5, 1]

计算最长递增子序列

所谓的最长递增子序列就是给定一个数值序列，找到它的一个子序列，并且子序列中的值是递增的，子序列中的元素在原序列中不一定连续，比如给定的序列是 [0, 8, 4, 12, 2, 10]，那么它的最长递增子序列就是 [0, 2, 10]（也可以是 [0, 8, 10] 或 [0, 4, 12] 等，并不是唯一）

针对于这种情况，我们就可以利用上面提到的『动态规划』思想来进行求解，可以参考下表，我们以该格子所对应的数字为开头的递增子序列的最大长度，至于如何计算一个格子中的值，规则很简单（假定从右往左），如下

1、拿该格子对应的数字 a 与其后面的所有格子对应的数字 b 进行比较，如果条件 a < b 成立，则用数字 b 对应格子中的值加 1，并将结果填充到数字 a 对应的格子中
2、只有当计算出来的值大于数字 a 所对应的格子中的值时，才需要更新格子中的数值

0	8	4	12	2	10
3	2	2	1	2	1

实现如下

const seq = [0, 8, 4, 12, 2, 10]

function lis(seq) {

  // 构建索引表
  const valueToMax = {}
  let len = seq.length
  for (let i = 0; i < len; i++) {
    valueToMax[seq[i]] = 1
  }

  let i = len - 1
  let last = seq[i]
  let prev = seq[i - 1]
  while (typeof prev !== 'undefined') {
    let j = i
    while (j < len) {
      last = seq[j]
      if (prev < last) {
        const currentMax = valueToMax[last] + 1
        valueToMax[prev] = valueToMax[prev] !== 1
          ? (valueToMax[prev] > currentMax ? valueToMax[prev] : currentMax)
          : currentMax
      }
      j++
    }
    i--
    last = seq[i]
    prev = seq[i - 1]
  }

  const lis = []
  i = 1
  while (--len >= 0) {
    const n = seq[len]
    if (valueToMax[n] === i) {
      i++
      lis.unshift(len)
    }
  }

  return lis
}

// 注意，结果是序列中的位置索引，比如下列输出结果是 [0, 4, 5]，对应到 seq 当中则为 [0, 2, 10]
console.log(lis(seq))

BF 和 KMP 算法

这两个算法也是数据结构当中涉及比较多的算法，更为具体的原理跟实现方式可见 BF 和 KMP 算法，我们在这里简单的总结一下，两者的区别如下

BF 算法，即暴力（Brute Force）算法，是普通的模式匹配算法，BF 算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配

若相等，则继续比较 S 的第二个字符和 T 的第二个字符
若不相等，则比较 S 的第二个字符和 T 的第一个字符，依次比较下去，直到得出最后的匹配结果

function indexOf(str, key) {
  let i = 0, j = 0

  // 为了简洁，没有判断当 str 剩余的字符少于 key 应该终止循环，因为这样会用到 length
  // 原理和上方是一样的，即 str[j] 和 key[i] 对比，如果一样那么 i 和 j 都加 1，否则 j 恢复到匹配时的下一个，i 恢复到 0
  while (key[i] !== undefined && str[j] !== undefined) {
    if (key[i] === str[j]) {
      i++
      j++
    } else {
      j = j - i + 1
      i = 0
    }
  }
  if (i === 0) return -1;
  return j - i
}

s = 'ABCDABCDABDE'
t = 'ABCDABD'
indexOf(s, t)

相较于 BF 算法，KMP 算法的主旨是尽量的减少指针的回溯从而使得性能得到提高（主要是文本串的指针，下面可以发现），我们先来看一下 KMP 算法的操作流程

假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j] ），都令 i++ 和 j++，然后继续匹配下一个字符
如果 j != -1，且当前字符匹配失败（即 S[i] != P[j] ），则令 i 不变，j = next[j]（此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next[j] 位）
换言之，将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处

function getNext(p) {
  let k = -1
  let j = 0
  let next = [-1]
  let pLen = p.length

  while (j < pLen - 1) {
    // p[k] 表示前缀，p[j] 表示后缀
    if (k == -1 || p[j] == p[k]) {
      ++j
      ++k
      // 在这里直接进行赋值操作也是可以的，但是保持一致，还是同 C 语言版本，在这里进行一下优化
      if (p[j] != p[k]) {
        next[j] = k
      } else {
        // 因为不能出现 p[j] = p[next[j]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
        next[j] = next[k]
      }
    } else {
      k = next[k]
    }
  }
  return next
}

function KMP(s, p) {
  let i = 0
  let j = 0

  let sLen = s.length
  let pLen = p.length

  let next = getNext(p)

  while (i < sLen && j < pLen) {
    // 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++
    if (j === -1 || s[i] === p[j]) {
      i++
      j++
    } else {
      // 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]
      // 这里就是与 BF 算法不同的地方，这里仅仅只用回退 j，而不用回退 i
      j = next[j]
    }
  }

  return j === pLen ? i - j : -1
}

s = 'ABCDABCDABDE'
t = 'ABCDABD'
KMP(s, t)  // 4

随机十六进制颜色

const randomHexColorCode = () => {
  let n = (Math.random() * 0xfffff * 1000000).toString(16)
  return '#' + n.slice(0, 6)
}

// "#e34155"
randomHexColorCode()

获取当前页面的滚动位置

const getScrollPosition = (el = window) => ({
  x: el.pageXOffset !== undefined ? el.pageXOffset : el.scrollLeft,
  y: el.pageYOffset !== undefined ? el.pageYOffset : el.scrollTop
})

// { x: 0, y: 200 }
getScrollPosition()

平滑滚动至顶部（回到顶部）

const scrollToTop = () => {
  const c = document.documentElement.scrollTop || document.body.scrollTop
  if (c > 0) {
    window.requestAnimationFrame(scrollToTop)
    window.scrollTo(0, c - c / 8)
  }
}

scrollToTop()

将表单元素转化为对象

const formToObject = form =>
  Array.from(new FormData(form)).reduce(
    (acc, [key, value]) => ({
      ...acc,
      [key]: value
    }),
    {}
  )

// { email: 'test@email.com', name: 'zhangsan' }
formToObject(document.querySelector('#form'))

获取对象指定的属性

const get = (from, ...selectors) =>
  [...selectors].map(s =>
    s
      .replace(/\[([^\[\]]*)\]/g, '.$1.')
      .split('.')
      .filter(t => t !== '')
      .reduce((prev, cur) => prev && prev[cur], from)
  )

const obj = { selector: { to: { val: 'val to select' } }, target: [1, 2, { a: 'test' }] }

// ['val to select', 1, 'test']
get(obj, 'selector.to.val', 'target[0]', 'target[2].a')

获取两个日期之间的差异（以天为单位）

const getDaysDiffBetweenDates = (dateInitial, dateFinal) =>
  Math.abs((dateFinal - dateInitial) / (1000 * 3600 * 24))

// 52
getDaysDiffBetweenDates(new Date('2020-12-13'), new Date('2020-10-22'))

将字符串复制到剪贴板

const copyToClipboard = (str) => {
  const el = document.createElement('textarea')
  el.value = str
  el.setAttribute('readonly', '')
  el.style.position = 'absolute'
  el.style.left = '-9999px'
  document.body.appendChild(el)
  const selected =
    document.getSelection().rangeCount > 0 ? document.getSelection().getRangeAt(0) : false
  el.select()
  document.execCommand('copy')
  document.body.removeChild(el)
  if (selected) {
    document.getSelection().removeAllRanges()
    document.getSelection().addRange(selected)
  }
}

copyToClipboard('test')

设计模式

工厂模式

又名静态工厂方法，就是创建对象，并赋予属性和方法，主要应用是抽取类相同的属性和方法封装到对象上

let UserFactory = function (role) {
  function User(opt) {
    this.name = opt.name
    this.viewPage = opt.viewPage
  }
  switch (role) {
    case 'superAdmin':
      return new User(superAdmin)
    case 'admin':
      return new User(admin)
    case 'user':
      return new User(user)
    default:
      throw new Error(`参数错误，可选参数为 superAdmin、admin、user`)
  }
}

let superAdmin = UserFactory('superAdmin')
let admin = UserFactory('admin')
let normalUser = UserFactory('user')

工厂方法模式

主要用于对产品类的抽象使其创建业务主要负责用于创建多类产品的实例，主要用于创建实例，也算是上面工厂方法的另外一种方式

var Factory = function (type, content) {
  if (this instanceof Factory) {
    var s = new this[type](content)
    return s
  } else {
    return new Factory(type, content)
  }
}

// 工厂原型中设置创建类型数据对象的属性
Factory.prototype = {
  test1: function (content) {
    console.log(content)
  },
  test2: function (content) {
    console.log(content)
  },
  test3: function (content) {
    console.log(content)
  },
}

Factory('test1', 'test1')

原型模式

主要用于设置函数的原型属性，通常用来实现继承

function Animal(name) {
  this.name = name || 'Animal'
  this.sleep = function () {
    console.log(this.name + '正在睡觉')
  }
}

Animal.prototype.eat = function (food) {
  console.log(this.name + '正在吃 ' + food)
}

function Cat() { }
Cat.prototype = new Animal()
Cat.prototype.name = 'cat'

var cat = new Cat()

cat.name         // cat
cat.eat('fish')  // cat 正在吃 fish
cat.sleep()      // cat 正在睡觉

cat instanceof Animal // true
cat instanceof Cat    // true

单例模式

其实简单来说，任意对象都是单例，无须特别处理，但是比较通用的用法是一个只允许被实例化一次的类，通常提供一个命名空间

let singleCase = function (name) {
  this.name = name
}

singleCase.prototype.getName = function () {
  return this.name
}

let getInstance = (function () {
  var instance = null
  return function (name) {
    if (!instance) {
      instance = new singleCase(name)
    }
    return instance
  }
})()

// true
getInstance('one') === getInstance('two')

下面这个则是一个更为通用的惰性单例

var getSingle = function (fn) {
  var result
  return function () {
    return result || (result = fn.apply(this, arguments))
  }
}

外观模式

也可译为门面模式，它为子系统中的一组接口提供一个一致的界面，比如在家要看电影，需要打开音响，再打开投影仪等，引入外观角色之后，只需要调用打开电影设备方法就可以了，它的作用是简化复杂接口和解耦和，屏蔽使用者对子系统的直接访问

这种方式其实我们在平常开发过程中经常使用，只是我们没有察觉而已，在形式上，外观模式在 JavaScript 中就类似于下面这样的

function a(x) {
  // do something
}
function b(y) {
  // do something
}

function ab(x, y) {
  a(x)
  b(y)
}

适配器模式

适配器模式是将一个接口转换成客户希望的另一个接口，使接口不兼容的那些类可以一起工作，我们在生活中就常常有使用适配器的场景，例如出境旅游插头插座不匹配，这时我们就需要使用转换插头，也就是适配器来帮我们解决问题

class Adaptee {
  test() {
    return '旧接口'
  }
}

class Target {
  constructor() {
    this.adaptee = new Adaptee()
  }
  test() {
    let info = this.adaptee.test()
    return `适配${info}`
  }
}

let target = new Target()
console.log(target.test())

装饰者模式

装饰器模式，可以理解为对类的一个包装，动态地拓展类的功能，ES7 的装饰器语法以及 React 中的高阶组件（HOC）都是这一模式的实现，React-Redux 的 connect() 也运用了装饰器模式，这里以 ES7 的装饰器为例

function info(target) {
  target.prototype.name = '张三'
  target.prototype.age = 10
}

@info
class Man { }

let man = new Man()
man.name

桥接模式

桥接模式（Bridge）主要是将抽象部分与它的实现部分分离，使它们都可以独立地变化，通常用在事件监控上，我们先来看一段代码

addEvent(element, 'click', getBeerById)

function getBeerById(e) {
  var id = this.id
  asyncRequest('GET', 'beer.uri?id=' + id, function (resp) {
    // Callback response
    console.log('Requested Beer: ' + resp.responseText)
  })
}

上述代码，有个问题就是 getBeerById 必须要有浏览器的上下文才能使用，因为其内部使用了 this.id 这个属性，通常情况下，我们会将程序改造成如下形式

function getBeerById(id, callback) {
  // 通过 id 发送请求，然后返回数据
  asyncRequest('GET', 'beer.uri?id=' + id, function (resp) {
    // callback response
    callback(resp.responseText)
  })
}

现在看上去是不是实用多了，首先 id 可以随意传入，而且还提供了一个 callback 函数用于自定义处理函数，但是这个和桥接有什么关系呢？这就是下段代码所要体现的了

addEvent(element, 'click', getBeerByIdBridge)

function getBeerByIdBridge(e) {
  getBeerById(this.id, function (beer) {
    console.log('Requested Beer: ' + beer)
  })
}

这里的 getBeerByIdBridge 就是我们定义的桥，用于将抽象的 click 事件和 getBeerById 连接起来，同时将事件源的 id，以及自定义的 callback 函数作为参数传入到 getBeerById 函数当中

模版方法模式

简单来说，所谓的模版方法模式（Template Method）就是在父类中定义一组操作算法骨架，而将一些实现步骤延迟到子类中，使得子类可以不改变父类的算法结构的同时可重新定义算法中某些实现步骤

(function (window, undefined) {
  var logger = {
    log: function () {
      console.log(`log`)
    },
    init: function () {
      this.log()
    }
  }
  window.logger = logger
})(window)

var one = function () {
  logger.log = function () {
    console.log(`test`)
  }
  logger.init()
}

// test
one()

状态模式

状态模式是解决某些需求场景的最好方法，状态模式的关键是区分事物内部的状态，事物内部的状态的改变往往会带来事物的行为的改变，比如下面这个示例，在简单的多个状态之间切换的时候，这样的模式是非常清晰的

if (this.state === 'off') {
  console.log('开灯')
  this.state = 'on'
} else if (this.state === 'on') {
  console.log('关灯')
  this.state = 'off'
}

两个状态之间的切换，我们可以使用 if-else 的形式来进行切换，但是如果有多个状态的时候，这样的切换就会嵌套很多的条件判断语句，修改起来也是比较困难，所以这里我们就可以采用状态模式来对其进行一定程度上的重构

简单来说，就是把事物的每种状态都封装成单独的类，跟此状态相关的行为都被封装在这个类的内部，只要有交互行为，只需要在上下文中，把这个请求委托给当前的状态对象即可，该状态对象会负责渲染它自身的行为，首先我们先来封装状态

var OffLightState = function (light) {
  this.light = light
}

OffLightState.prototype.buttonWasPressed = function () {
  console.log('offLightState')                        // offLightState 对应的行为
  this.light.setState(this.light.weakLightState)      // 切换状态到 weakLightState
}

// WeakLightState
var WeakLightState = function (light) {
  this.light = light
}

WeakLightState.prototype.buttonWasPressed = function () {
  console.log('weakLightState')                       // weakLightState 对应的行为
  this.light.setState(this.light.strongLightState)    // 切换状态到 strongLightState
}

// StrongLightState
var StrongLightState = function (light) {
  this.light = light
}

StrongLightState.prototype.buttonWasPressed = function () {
  console.log('strongLightState')                     // strongLightState 对应的行为
  this.light.setState(this.light.offLightState)       // 切换状态到 offLightState
}

var Light = function () {
  this.offLightState = new OffLightState(this)
  this.weakLightState = new WeakLightState(this)
  this.strongLightState = new StrongLightState(this)
  this.button = null
}

Light.prototype.init = function () {
  var button = document.createElement('button'), self = this
  this.button = document.body.appendChild(button)
  this.button.innerHTML = '开关'
  // 设置当前状态
  this.currState = this.offLightState
  this.button.onclick = function () {
    self.currState.buttonWasPressed()
  }
}

Light.prototype.setState = function (newState) {
  // 设置下一个状态
  this.currState = newState
}

var light = new Light()

light.init()

我们在 Light 类中为每个状态类都创建一个状态对象，这样一来就可以很明显的看到电灯一共有多少个状态，当我们在使用的时候，也就是点击 button 的时候，通过 self.currState.buttonWasPressed() 将请求委托为当前的状态去执行

最后提供一个 setState 的方法，状态对象通过这个方法来切换 Light 对象的状态，状态对象的切换规律被定义在各个状态类中

策略模式

简单来说，策略模式指的是定义一系列的算法，并且把它们封装起来，但是策略模式不仅仅只封装算法，我们还可以对用来封装一系列的业务规则，只要这些业务规则目标一致，我们就可以使用策略模式来封装它们

var obj = {
  'A': function (salary) {
    return salary * 4
  },
  'B': function (salary) {
    return salary * 3
  },
  'C': function (salary) {
    return salary * 2
  }
}
var calculateBouns = function (level, salary) {
  return obj[level](salary)
}

// 40000
calculateBouns('A', 10000)

访问模式

访问者模式（Visitor Pattern）模式是行为型（Behavioral）设计模式，提供一个作用于某种对象结构上的各元素的操作方式，可以使我们在不改变元素结构的前提下，定义作用于元素的新操作，简单来说，如果系统的数据结构是比较稳定的，但其操作（算法）是易于变化的，那么使用访问者模式是个不错的选择，但是如果数据结构是易于变化的，则不适合使用访问者模式

访问者模式一共有五种角色

Vistor（抽象访问者），为该对象结构中具体元素角色声明一个访问操作接口
ConcreteVisitor（具体访问者），每个具体访问者都实现了 Vistor 中定义的操作
Element（抽象元素），定义了一个 accept 操作，以 Visitor 作为参数
ConcreteElement（具体元素），实现了 Element 中的 accept() 方法，调用 Vistor 的访问方法以便完成对一个元素的操作
ObjectStructure（对象结构），可以是组合模式，也可以是集合，一般能够枚举它包含的元素，通常会提供一个接口，允许 Vistor 访问它的元素

// 访问者
function Visitor() {
  this.visit = function (concreteElement) {
    concreteElement.doSomething()
  }
}

// 元素类
function ConceteElement() {
  this.doSomething = function () {
    console.log(`这是一个具体元素`)
  }
  this.accept = function (visitor) {
    visitor.visit(this)
  }
}

// Client
var ele = new ConceteElement()
var v = new Visitor()

ele.accept(v)

中介者模式

中介者是协调多个对象之间的交互（逻辑和行为）的对象，它根据其他对象和输入的动作（或不动作）来决定何时调用哪些对象，比如下面这个示例，其中的 publish() 和 subscribe() 方法都被暴露出来使用

var mediator = (function () {
  var topics = {}
  var subscribe = function (topic, fn) {
    if (!topics[topic]) {
      topics[topic] = []
    }
    topics[topic].push({ context: this, callback: fn })
    return this
  }
  var publish = function (topic) {
    var args
    if (!topics[topic]) {
      return false
    }
    args = Array.prototype.slice.call(arguments, 1)
    for (var i = 0, l = topics[topic].length; i < l; i++) {
      var subscription = topics[topic][i]
      subscription.callback.apply(subscription.context, args)
    }
    return this
  }
  return {
    publish: publish,
    subscribe: subscribe,
    installTo: function (obj) {
      obj.subscribe = subscribe
      obj.publish = publish
    }
  }
}())

代理模式

简单来说，就是新建个类调用老类的接口，包装一下，在 ES6 之前我们可以采用下面这种方式

function Person() { }

Person.prototype.sayName = function () {
  console.log('zhangsan')
}

Person.prototype.sayAge = function () {
  console.log(20)
}

function PersonProxy() {
  this.person = new Person()
  var that = this
  this.callMethod = function (functionName) {
    console.log('before proxy:', functionName)
    // 代理
    that.person[functionName]()
    console.log('after proxy:', functionName)
  }
}

var p = new PersonProxy()

p.callMethod('sayName')  // 代理调用 Person 的方法 sayName()
p.callMethod('sayAge')   // 代理调用 Person 的方法 sayAge()

另外在 ES6 当中提供了 Proxy 对象也可以用来实现代理，基本语法为

1	let x = new Proxy(target, handler)

target 是你要代理的对象，它可以是任何合法对象(数组，对象，函数等等)
handler 是你要自定义操作方法的一个集合
x 是一个被代理后的新对象，它拥有 target 的一切属性和方法，只不过其行为和结果是在 handler 中自定义的

所以在 ES6 之后，我们就可以考虑使用 Proxy

let obj = {
  a: 1,
  b: 2,
}

const p = new Proxy(obj, {
  get(target, key, value) {
    if (key === 'c') {
      return '我是自定义的一个结果'
    } else {
      return target[key]
    }
  },

  set(target, key, value) {
    if (value === 4) {
      target[key] = '我是自定义的一个结果'
    } else {
      target[key] = value
    }
  }
})

console.log(obj.a)    // 1
console.log(obj.c)    // undefined

console.log(p.a)      // 1
console.log(p.c)      // 我是自定义的一个结果

obj.name = 'zhangsan'
console.log(obj.name) // zhangsan

obj.age = 4
console.log(obj.age)  // 4

p.name = 'zhangsan'
console.log(p.name)   // zhangsan

p.age = 4
console.log(p.age)    // 我是自定义的一个结果

观察者模式

本质上也就是事件模式

// 被观察者
class Subject {
  constructor() {
    this.list = []
  }

  addListener(target) {
    this.list.push(target)
  }

  notify() {
    this.list.forEach(el => {
      el.say()
    })
  }
}

// 观察者
class Observer {
  constructor(name) {
    this.name = name
  }
  say() {
    console.log(this.name)
  }
}

const target = new Subject()
const person1 = new Observer('zhangsan')
const person2 = new Observer('lisi')

target.addListener(person1)
target.addListener(person2)

target.notify()

发布订阅模式

// 支持同步、异步管道化
var msghub = (function () {
  var listener = []
  return {
    on: function (type, cb, option) {
      listener[type] = listener[type] || []
      option = option || {}
      listener[type].push({
        cb: cb,
        priority: option.priority || 0
      })
    },
    fire: function (type, dataObj) {
      if (listener[type]) {
        let listenerArr = listener[type].sort((a, b) => b.priority - a.priority)
        (async function iter() {
          let val = dataObj
          for (const item of listenerArr) {
            val = await item.cb.call(null, val)
          }
        })()
      }
    }
  }
})()

常用方法 && 函数

事件模型（EventBus）

这个通常在面试的时候被问到的比较多，下面我们就来看看如何实现，先从最为基本的实现方式开始看起

class EventEmitter {
  constructor() {
    // 存储事件
    this.events = this.events || new Map()
  }

  // 监听事件
  addListener(type, fn) {
    if (!this.events.get(type)) {
      this.events.set(type, fn)
    }
  }

  // 触发事件
  emit(type) {
    let handle = this.events.get(type)
    handle.apply(this, [...arguments].slice(1))
  }
}

以上就是一个最为基本的架子，虽然实现了主要功能，但是没有处理异常场景和事件移除的相关处理，下面我们来看看如何完善它们

class EventEmitter {
  constructor() {
    if (this._events === undefined) {
      // 定义事件对象
      this._events = Object.create(null)
      this._eventsCount = 0
    }
  }

  emit(type, ...args) {
    const events = this._events
    const handler = events[type]
    // 判断相应 type 的执行函数是否为一个函数还是一个数组
    if (typeof handler === 'function') {
      Reflect.apply(handler, this, args)
    } else {
      const len = handler.length
      for (var i = 0; li < len; i++) {
        Reflect.apply(handler[i], this, args)
      }
    }
    return true
  }

  on(type, listener, prepend) {
    var events
    var existing
    events = this._events
    // 添加事件
    if (events.newListener !== undefined) {
      this.emit('namelessListener', type, listener)
      events = target._events
    }
    existing = events[type]
    // 判断相应的 type 的方法是否存在
    if (existing === undefined) {
      // 如果相应的 type 的方法不存在，则新增一个相应 type 的事件
      existing = events[type] = listener
      ++this._eventsCount
    } else {
      // 如果存在相应的 type 的方法，判断相应的 type 的方法是一个数组还是仅仅只是一个方法
      if (typeof existing === 'function') {
        // 如果仅仅是一个方法，则添加
        existing = events[type] = prepend ? [listener, existing] : [existing, listener]
      } else if (prepend) {
        existing.unshift(listener)
      } else {
        existing.push(listener)
      }
    }
    // 保证链式调用
    return this
  }

  removeListener(type, listener) {
    var list, events, position, i
    events = this._events
    list = events[type]
    // 如果相应的事件对象的属性值是一个函数，也就是说事件只被一个函数监听
    if (list === listener) {
      if (--this._eventsCount === 0) {
        this._events = Object.create(null)
      } else {
        delete events[type]
        // 如果存在对移除事件 removeListener 的监听函数，则触发 removeListener
        if (events.removeListener)
          this.emit('removeListener', type, listener)
      }
    } else if (typeof list !== 'function') {
      // 如果相应的事件对象属性值是一个函数数组
      // 遍历这个数组，找出 listener 对应的那个函数，在数组中的位置
      for (i = list.length - 1; i >= 0; i--) {
        if (list[i] === listener) {
          position = i
          break
        }
      }
      // 没有找到这个函数，则返回不做任何改动的对象
      if (position) {
        return this
      }
      // 如果数组的第一个函数才是所需要删除的对应 listener 函数，则直接移除
      if (position === 0) {
        list.shift()
      } else {
        list.splice(position, 1)
      }
      if (list.length === 1)
        events[type] = list[0]
      if (events.removeListener !== undefined)
        this.emit('removeListener', type, listener)
    }
    return this
  }
}

下面再来简单的测试一下

// 测试
var emitter = new EventEmitter()

emitter.on('event2', function (arg1, arg2) {
  console.log('get event2', arg1, arg2)
})

emitter.on('event1', function (arg1, arg2) {
  console.log('get event1', arg1, arg2)
})

console.log('emit event')

emitter.emit('event2', 'arg1', 'arg2')
emitter.emit('event1', 'arg1', 'arg2')

Ajax

var xhr = new XMLHttpRequest()

if (xhr) {
  xhr.open('GET', url)
  xhr.onreadystatechange = function () {
    if (xhr.readyState == 4 && xhr.status == 200) {
      console.log(xhr.responseText)
    }
  }
  xhr.send()
}

// ---------------------------------------------------

// 如果需要使用 POST 请求发送表单数据，使用 setRequestHeader() 来添加 http 头
// 然后在 send() 方法中添加需要发送的数据

// 在 Form 元素的语法中，EncType 表明提交数据的格式，用 Enctype 属性指定将数据回发到服务器时浏览器使用的编码类型

// 下面是三种常用的设置方式
// application/x-www-form-urlencoded   窗体数据被编码为 名称/值 对，这是标准的编码格式
// multipart/form-data                 窗体数据被编码为一条消息，页上的每个控件对应消息中的一个部分
// text/plain                          窗体数据以纯文本形式进行编码，其中不含任何控件或格式字符 

xhr.open('POST', url, true)
xhr.setRequestHeader('Content-type', 'application/x-www-form-urlencoded')
xhr.send(data)

Promise 版本 Ajax

function getJSON(url) {
  return new Promise((resolve, reject) => {
    var xhr = new XMLHttpRequest()
    xhr.open('GET', url, true)
    xhr.onreadystatechange = function () {
      if (this.readyState === 4) {
        if (this.status === 200) {
          resolve(this.responseText, this)
        } else {
          var resJson = { code: this.status, response: this.response }
          reject(resJson, this)
        }
      }
    }
    xhr.send()
  })
}

// 使用
getJSON(url).then(function (data) {
  console.log(data)
}).catch(function (status) {
  console.log(`Error: ${status}`)
})

终止请求

我们在上面提到了 Ajax，所以在这里我们就来多看一点，那就是如何终止请求，目前来说，使用较多的请求数据有两种方式，一种是 Ajax，另一种就是 fetch，我们先来看看在 Ajax 当中终止请求的方式，方法很简单，当我们由于某种原因（比如重复请求）想要终止它的时候，我们只需要调用 abort() 即可

1	xhr.abort()

但是对于 fetch 来说，我们主要使用的是 AbortSignal 这个接口，在 MDN 上的介绍是，AbortSignal 接口表示一个信号对象（signal object），它允许通过 AbortController 对象与 DOM 请求（如 Fetch）进行通信并在需要时将其中止

看到这里是不是有一些眉目了，我们只需要使用 AbortController() 构造函数创建一个控制器，然后使用 AbortController.signal 属性就可以了，当获取请求被启动时，我们在请求的选项对象中传递 AbortSignal 作为一个选项，这将信号和控制器与获取请求相关联，并允许我们通过调用 AbortController.abort() 来中止它，代码如下

const controller = new AbortController()
const signal = controller.signal
console.log(signal, `signal 的初始状态`)

signal.addEventListener('abort', function (e) {
  console.log(signal, `signal 的中断状态`)
})

setTimeout(function () {
  controller.abort()
}, 2000)

fetch('/api', { signal })
  .then((res) => {
    console.log(res, '请求成功')
  })

但是也有一个需要注意的地方，那就是虽然 AbortController 已经诞生很长时间了，但是目前在 MDN 上还是被标注为实验性技术，所以还是需要根据实际使用场景来考虑是否使用

批量请求

要求实现一个批量请求函数 multiRequest(urls, maxNum)，要求如下

要求最大并发数 maxNum
每当有一个请求返回，就留下一个空位，可以增加新的请求
所有请求完成后，结果按照 urls 里面的顺序依次打出

整体采用递归调用来实现，最初发送的请求数量上限为允许的最大值，并且这些请求中的每一个都应该在完成时继续递归发送，通过传入的索引来确定了 urls 里面具体是那个 url，保证最后输出的顺序不会乱，而是依次输出

function multiRequest(urls = [], maxNum) {
  const len = urls.length                           // 请求总数量
  const result = new Array(len).fill(false)         // 根据请求数量创建一个数组来保存请求的结果 
  let count = 0                                     // 当前完成的数量
  return new Promise((resolve, reject) => {
    while (count < maxNum) {                        // 利用递归
      next()
    }
    function next() {
      let current = count++
      if (current >= len) {                         // 处理边界条件
        !result.includes(false) && resolve(result)  // 请求全部完成就将 promise 置为成功状态，然后返回 resolve(result)
        return
      }
      const url = urls[current]
      console.log(`开始 ${current}`, new Date().toLocaleString())
      fetch(url).then((res) => {
        result[current] = res                       // 保存请求结果
        console.log(`完成 ${current}`, new Date().toLocaleString())
        if (current < len) {                        // 请求没有全部完成，就递归
          next()
        }
      }).catch((err) => {
        console.log(`结束 ${current}`, new Date().toLocaleString())
        result[current] = err
        if (current < len) {                        // 请求没有全部完成，就递归
          next()
        }
      })
    }
  })
}

getElementsByClassName()

function getElementsByClassName(classname) {
  if (document.querySelectorAll) {
    return document.querySelectorAll('.' + classname)
  } else {
    var elements = document.getElementsByTagName('*')
    var reg = new RegExp('(^|\\s)' + classname + '(\\s|$)')
    var results = []
    for (let i = 0, length = elements.length; i < length; i++) {
      if (reg.test(elements[i].className)) {
        results.push(elements[i])
      }
    }
  }
  return results
}

# JavaScript