JS-writing

post.posted post.in

JS 手写代码

程序员最重要的就是动手能力�?
::: tip
如有疑问，可免费 加群 讨论咨询，也可参�?1v1 面试咨询服务�?专业、系统、高效、全流程 准备前端面试
:::

手写深拷�?

考虑循环引用

::: details 参考答�?
简单的深拷贝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function cloneDeep(source, hash = new WeakMap()) {
  if (!isObject(source)) return source
  if (hash.has(source)) return hash.get(source)

  var target = Array.isArray(source) ? [] : {}
  hash.set(source, target)

  for (var key in source) {
    if (Object.prototype.hasOwnProperty.call(source, key)) {
      if (isObject(source[key])) {
        target[key] = cloneDeep(source[key], hash)
      } else {
        target[key] = source[key]
      }
    }
  }
  return target
}

考虑更多比如爆栈的情况：

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
function cloneDeep(x) {
  const root = {}

  const loopList = [
    {
      parent: root,
      key: undefined,
      data: x,
    },
  ]

  while (loopList.length) {
    const node = loopList.pop()
    const parent = node.parent
    const key = node.key
    const data = node.data

    let res = parent
    if (typeof key !== 'undefined') {
      res = parent[key] = {}
    }

    for (let k in data) {
      if (data.hasOwnProperty(k)) {
        if (typeof data[k] === 'object') {
          loopList.push({
            parent: res,
            key: k,
            data: data[k],
          })
        } else {
          res[k] = data[k]
        }
      }
    }
  }

  return root
}

参考阅读：

手写 getType 函数

获取详细的变量类�?
::: details 参考答�?

1
2
3
4
5
function getType(data) {
  // 获取�?"[object Type]"，其�?Type �?Null、Undefined、Array、Function、Error、Boolean、Number、String、Date、RegExp 等�?  const originType = Object.prototype.toString.call(data)
  // 可以直接截取�?位和倒数第一位，这样就获得了 Null、Undefined、Array、Function、Error、Boolean、Number、String、Date、RegExp �?  const type = originType.slice(8, -1)
  // 再转小写，得�?null、undefined、array、function �?  return type.toLowerCase()
}

:::

手写 class 继承

在某网页中，有三种菜单：button menu，select menu，modal menu�?
他们的共同特点：

  • 都有 title icon 属�?- 都有 isDisabled 方法（可直接返回 false�?- 都有 exec 方法，执行菜单的逻辑

他们的不同点�?

  • button menu，执�?exec 时打�?'hello'
  • select menu，执�?exec 时返回一个数�?['item1', 'item2', 'item3']
  • modal menu，执�?exec 时返回一�?DOM Element <div>modal</div>

请用 ES6 语法写出这三种菜单的 class

::: details 参考答�?

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
class BaseMenu {
  constructor(title, icon) {
    this.title = title
    this.icon = icon
  }
  isDisabled() {
    return false
  }
}

class ButtonMenu extends BaseMenu {
  constructor(title, icon) {
    super(title, icon)
  }
  exec() {
    console.log('hello')
  }
}

class SelectMenu extends BaseMenu {
  constructor(title, icon) {
    super(title, icon)
  }
  exec() {
    return ['item1', 'item2', 'item3']
  }
}

class ModalMenu extends BaseMenu {
  constructor(title, icon) {
    super(title, icon)
  }
  exec() {
    const div = document.createElement('div')
    div.innerText = 'modal'
    return div
  }
}

:::

手写防抖 Debounce

::: details 参考答�?

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
function debounce(func, wait, immediate) {
  var timeout, result

  var debounced = function () {
    var context = this
    var args = arguments

    if (timeout) clearTimeout(timeout)
    if (immediate) {
      // 如果已经执行过，不再执行
      var callNow = !timeout
      timeout = setTimeout(function () {
        timeout = null
      }, wait)
      if (callNow) result = func.apply(context, args)
    } else {
      timeout = setTimeout(function () {
        func.apply(context, args)
      }, wait)
    }
    return result
  }

  debounced.cancel = function () {
    clearTimeout(timeout)
    timeout = null
  }

  return debounced
}

参考阅读：

手写截流 Throttle

::: details 参考答�?

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
function throttle(func, wait, options) {
  var timeout, context, args, result
  var previous = 0
  if (!options) options = {}

  var later = function () {
    previous = options.leading === false ? 0 : new Date().getTime()
    timeout = null
    func.apply(context, args)
    if (!timeout) context = args = null
  }

  var throttled = function () {
    var now = new Date().getTime()
    if (!previous && options.leading === false) previous = now
    var remaining = wait - (now - previous)
    context = this
    args = arguments
    if (remaining <= 0 || remaining > wait) {
      if (timeout) {
        clearTimeout(timeout)
        timeout = null
      }
      previous = now
      func.apply(context, args)
      if (!timeout) context = args = null
    } else if (!timeout && options.trailing !== false) {
      timeout = setTimeout(later, remaining)
    }
  }
  throttled.cancel = function () {
    clearTimeout(timeout)
    previous = 0
    timeout = null
  }
  return throttled
}

参考阅读：

手写 bind

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Function.prototype.bind2 = function (context) {
  if (typeof this !== 'function') {
    throw new Error('Function.prototype.bind - what is trying to be bound is not callable')
  }

  var self = this
  var args = Array.prototype.slice.call(arguments, 1)

  var fNOP = function () {}

  var fBound = function () {
    var bindArgs = Array.prototype.slice.call(arguments)
    return self.apply(this instanceof fNOP ? this : context, args.concat(bindArgs))
  }

  fNOP.prototype = this.prototype
  fBound.prototype = new fNOP()
  return fBound
}

参考阅读：

:::

手写 call �?apply

::: details 参考答�?

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
Function.prototype.call2 = function (context) {
  var context = context || window
  context.fn = this

  var args = []
  for (var i = 1, len = arguments.length; i < len; i++) {
    args.push('arguments[' + i + ']')
  }

  var result = eval('context.fn(' + args + ')')

  delete context.fn
  return result
}

Function.prototype.apply = function (context, arr) {
  var context = Object(context) || window
  context.fn = this

  var result
  if (!arr) {
    result = context.fn()
  } else {
    var args = []
    for (var i = 0, len = arr.length; i < len; i++) {
      args.push('arr[' + i + ']')
    }
    result = eval('context.fn(' + args + ')')
  }

  delete context.fn
  return result
}

参考阅读：

:::

手写 EventBus 自定义事�?

::: details 参考答�?

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
class EventBus {
  constructor() {
    this.eventObj = {}
    this.callbcakId = 0
  }

  $on(name, callbcak) {
    if (!this.eventObj[name]) {
      this.eventObj[name] = {}
    }
    const id = this.callbcakId++
    this.eventObj[name][id] = callbcak
    return id
  }
  $emit(name, ...args) {
    const eventList = this.eventObj[name]
    for (const id in eventList) {
      eventList[id](...args)
      if (id.indexOf('D') !== -1) {
        delete eventList[id]
      }
    }
  }
  $off(name, id) {
    delete this.eventObj[name][id]
    if (!Object.keys(this.eventObj[name]).length) {
      delete this.eventObj[name]
    }
  }
  $once(name, callbcak) {
    if (!this.eventObj[name]) {
      this.eventObj[name] = {}
    }
    const id = 'D' + this.callbcakId++
    this.eventObj[name][id] = callbcak
    return id
  }
}

参考阅读：

手写数组拍平 Array Flatten

::: details 参考答�?

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
function flatten(input, shallow, strict, output) {
  // 递归使用的时候会用到output
  output = output || []
  var idx = output.length

  for (var i = 0, len = input.length; i < len; i++) {
    var value = input[i]
    // 如果是数组，就进行处�?    if (Array.isArray(value)) {
      // 如果是只扁平一层，遍历该数组，依此填入 output
      if (shallow) {
        var j = 0,
          length = value.length
        while (j < length) output[idx++] = value[j++]
      }
      // 如果是全部扁平就递归，传入已经处理的 output，递归中接着处理 output
      else {
        flatten(value, shallow, strict, output)
        idx = output.length
      }
    }
    // 不是数组，根�?strict 的值判断是跳过不处理还是放�?output
    else if (!strict) {
      output[idx++] = value
    }
  }

  return output
}

参考阅读：

手写解析 URL 参数�?JS 对象

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function parseParam(url) {
  const paramsStr = /.+\?(.+)$/.exec(url)[1] // �?? 后面的字符串取出�?  //exec() 方法用于检索字符串中的正则表达式的匹配�?  const paramsArr = paramsStr.split('&') // 将字符串�?& 分割后存到数组中
  let paramsObj = {}
  // �?params 存到对象�?  paramsArr.forEach((param) => {
    if (/=/.test(param)) {
      // 处理�?value 的参�?      let [key, val] = param.split('=') // 分割 key �?value
      val = decodeURIComponent(val) // 解码
      val = /^\d+$/.test(val) ? parseFloat(val) : val // 判断是否转为数字
      //test() 方法用于检测一个字符串是否匹配某个模式.
      if (paramsObj.hasOwnProperty(key)) {
        // 如果对象�?key，则添加一个�?        paramsObj[key] = [].concat(paramsObj[key], val)
        //concat() 方法用于连接两个或多个数组�?        //该方法不会改变现有的数组，而仅仅会返回被连接数组的一个副本�?      } else {
        // 如果对象没有这个 key，创�?key 并设置�?        paramsObj[key] = val
      }
    } else {
      // 处理没有 value 的参�?      paramsObj[param] = true
    }
  })

  return paramsObj
}

参考阅读：

手写数组去重

::: details 参考答�?

1
var unique = (a) => [...new Set(a)]

参考阅读：

手写红绿�?

模拟一个红绿灯变化，红�?1 秒，绿灯 1 秒，黄灯 1 秒，然后循环

::: details 参考答�?

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
function red() {
  console.log('red')
}

function green() {
  console.log('green')
}

function yellow() {
  console.log('yellow')
}

function light(cb, wait) {
  return new Promise((resolve) => {
    setTimeout(() => {
      cb()
      resolve()
    }, wait)
  })
}

function start() {
  return Promise.resolve()
    .then(() => {
      return light(red, 1000)
    })
    .then(() => {
      return light(green, 1000)
    })
    .then(() => {
      return light(yellow, 1000)
    })
    .finally(() => {
      return start()
    })
}

start()

:::

手写 Promise

::: details 参考答�?

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
class MyPromise {
  // 构造方�?  constructor(executor) {
    // 初始化�?    this.initValue()
    // 初始化this指向
    this.initBind()
    // 执行传进来的函数
    executor(this.resolve, this.reject)
  }

  initBind() {
    // 初始化this
    this.resolve = this.resolve.bind(this)
    this.reject = this.reject.bind(this)
  }

  initValue() {
    // 初始化�?    this.PromiseResult = null // 终�?    this.PromiseState = 'pending' // 状�?  }

  resolve(value) {
    // 如果执行resolve，状态变为fulfilled
    this.PromiseState = 'fulfilled'
    // 终值为传进来的�?    this.PromiseResult = value
  }

  reject(reason) {
    // 如果执行reject，状态变为rejected
    this.PromiseState = 'rejected'
    // 终值为传进来的reason
    this.PromiseResult = reason
  }
}

参考阅读：

手写 Promise.all

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static all(promises) {
  const result = []
  let count = 0
  return new MyPromise((resolve, reject) => {
    const addData = (index, value) => {
        result[index] = value
        count++
        if (count === promises.length) resolve(result)
    }
    promises.forEach((promise, index) => {
        if (promise instanceof MyPromise) {
            promise.then(res => {
                addData(index, res)
            }, err => reject(err))
        } else {
            addData(index, promise)
        }
    })
  })
}

参考阅读：

手写 Promise.race

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static race(promises) {
  return new MyPromise((resolve, reject) => {
    promises.forEach(promise => {
      if (promise instanceof MyPromise) {
          promise.then(res => {
              resolve(res)
          }, err => {
              reject(err)
          })
      } else {
          resolve(promise)
      }
    })
  })
}

参考阅读：

手写 Promise.allSettled

::: details 参考答�?

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
static allSettled(promises) {
  return new Promise((resolve, reject) => {
    const res = []
    let count = 0
    const addData = (status, value, i) => {
      res[i] = {
          status,
          value
      }
      count++
      if (count === promises.length) {
          resolve(res)
      }
    }
    promises.forEach((promise, i) => {
      if (promise instanceof MyPromise) {
        promise.then(res => {
          addData('fulfilled', res, i)
        }, err => {
          addData('rejected', err, i)
        })
      } else {
        addData('fulfilled', promise, i)
      }
    })
  })
}

参考阅读：

手写一�?LazyMan 实现 sleep 机制

1
2
3
4
5
6
7
8
LazyMan('Tony').eat('breakfast').sleep(3).eat('lunch').sleep(1).eat('dinner')
// 输出:
// Hi I am Tony
// I am eating breakfast
// 等待3�?..
// I am eating lunch
// 等待1�?..
// I am eating dinner

::: details 参考答�?

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
class LazyMan {
  constructor(name) {
    this.name = name
    this.tasks = [] // 任务队列

    // 初始任务
    this.tasks.push(() => {
      console.log(`Hi I am ${name}`)
      return Promise.resolve()
    })

    // 使用 setTimeout 确保所有任务入队后再执�?    setTimeout(() => {
      this.runTasks()
    }, 0)
  }

  // 执行任务队列
  async runTasks() {
    for (const task of this.tasks) {
      await task()
    }
  }

  eat(food) {
    this.tasks.push(() => {
      console.log(`I am eating ${food}`)
      return Promise.resolve()
    })
    return this
  }

  sleep(seconds) {
    this.tasks.push(() => {
      console.log(`等待${seconds}�?..`)
      return new Promise((resolve) => {
        setTimeout(resolve, seconds * 1000)
      })
    })
    return this
  }
}

// 工厂函数，方便调�?function createLazyMan(name) {
  return new LazyMan(name)
}

:::

手写 curry 函数，实现函数柯里化

::: details 参考答�?

  1. 基础版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function curry(fn) {
  return function curried(...args) {
    // 如果传入的参数个数大于等于原函数的参数个数，直接执行
    if (args.length >= fn.length) {
      return fn.apply(this, args)
    }
    // 否则返回一个新函数，等待接收剩余参�?    return function (...args2) {
      return curried.apply(this, args.concat(args2))
    }
  }
}

// 使用示例
function add(a, b, c) {
  return a + b + c
}

const curriedAdd = curry(add)
console.log(curriedAdd(1)(2)(3)) // 6
console.log(curriedAdd(1, 2)(3)) // 6
console.log(curriedAdd(1)(2, 3)) // 6
  1. 支持占位符的进阶版本
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
function curry(fn, placeholder = '_') {
  const length = fn.length

  return function curried(...args) {
    // 检查是否所有参数都已经填充（不包含占位符）
    const checkFilled = (args) => {
      // 统计非占位符的参数个�?      const filledArgsCount = args.filter((arg) => arg !== placeholder).length
      return filledArgsCount >= length
    }

    // 合并新旧参数，处理占位符
    const mergeArgs = (existingArgs, newArgs) => {
      const result = [...existingArgs]
      let newArgsIndex = 0

      // 遍历现有参数，将占位符替换为新参�?      for (let i = 0; i < result.length && newArgsIndex < newArgs.length; i++) {
        if (result[i] === placeholder) {
          result[i] = newArgs[newArgsIndex++]
        }
      }

      // 将剩余的新参数添加到结果�?      return result.concat(newArgs.slice(newArgsIndex))
    }

    const mergedArgs = mergeArgs(args, [])

    // 如果参数已经足够，执行原函数
    if (checkFilled(mergedArgs)) {
      // 过滤掉占位符
      const finalArgs = mergedArgs.slice(0, length).filter((arg) => arg !== placeholder)
      return fn.apply(this, finalArgs)
    }

    // 否则继续返回柯里化函�?    return function (...nextArgs) {
      return curried.apply(this, mergeArgs(mergedArgs, nextArgs))
    }
  }
}

// 使用示例
const add = (a, b, c) => a + b + c
const curriedAdd = curry(add)
const _ = '_' // 占位�?
console.log(curriedAdd(1)(2)(3)) // 6
console.log(curriedAdd(1, 2)(3)) // 6
console.log(curriedAdd(1)(_, 3)(2)) // 6
console.log(curriedAdd(_, 2)(1)(3)) // 6
console.log(curriedAdd(_, _, 3)(1)(2)) // 6
  1. ES6 简化版�?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    const curry = (fn, arity = fn.length) => {
      const curried = (...args) => (args.length >= arity ? fn(...args) : (...more) => curried(...args, ...more))
      return curried
    }

    // 使用示例
    const sum = (a, b, c) => a + b + c
    const curriedSum = curry(sum)

    console.log(curriedSum(1)(2)(3)) // 6
    console.log(curriedSum(1, 2)(3)) // 6
    console.log(curriedSum(1)(2, 3)) // 6

:::

手写 compose 函数

::: details 参考答�?
compose 函数是函数式编程中的一个重要概念，它将多个函数组合成一个函数，从右到左执行�?

  1. 基础实现（使�?reduce�?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function compose(...fns) {
      if (fns.length === 0) return (arg) => arg
      if (fns.length === 1) return fns[0]

      return fns.reduce(
        (a, b) =>
          (...args) =>
            a(b(...args))
      )
    }

    // 使用示例
    const add1 = (x) => x + 1
    const multiply2 = (x) => x * 2
    const addThenMultiply = compose(multiply2, add1)
    console.log(addThenMultiply(5)) // (5 + 1) * 2 = 12

  2. 支持异步函数的实�?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    async function composeAsync(...fns) {
      if (fns.length === 0) return (arg) => arg
      if (fns.length === 1) return fns[0]

      return fns.reduce((a, b) => async (...args) => {
        const result = await b(...args)
        return a(result)
      })
    }

    // 使用示例
    const asyncAdd = async (x) => {
      await new Promise((resolve) => setTimeout(resolve, 1000))
      return x + 1
    }
    const asyncMultiply = async (x) => {
      await new Promise((resolve) => setTimeout(resolve, 1000))
      return x * 2
    }

    const asyncOperation = composeAsync(asyncMultiply, asyncAdd)
    asyncOperation(5).then((result) => console.log(result)) // 12 (after 2 seconds)

  3. 从左到右执行�?pipe 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function pipe(...fns) {
  if (fns.length === 0) return (arg) => arg
  if (fns.length === 1) return fns[0]

  return fns.reduce(
    (a, b) =>
      (...args) =>
        b(a(...args))
  )
}

// 使用示例
const addOne = (x) => x + 1
const multiplyTwo = (x) => x * 2
const addThenMultiplyPipe = pipe(addOne, multiplyTwo)
console.log(addThenMultiplyPipe(5)) // (5 + 1) * 2 = 12
  1. 带错误处理的实现
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
function composeWithError(...fns) {
  if (fns.length === 0) return (arg) => arg
  if (fns.length === 1) return fns[0]

  return fns.reduce((a, b) => (...args) => {
    try {
      const result = b(...args)
      return a(result)
    } catch (error) {
      console.error('Error in compose:', error)
      throw error
    }
  })
}

// 使用示例
const divide = (x) => {
  if (x === 0) throw new Error('Cannot divide by zero')
  return 10 / x
}
const square = (x) => x * x

const divideAndSquare = composeWithError(square, divide)
console.log(divideAndSquare(2)) // (10 / 2)² = 25
try {
  divideAndSquare(0) // 抛出错误
} catch (e) {
  console.log('Caught error:', e.message)
}

使用场景示例�?

  1. 数据转换管道�?

    1
    2
    3
    4
    5
    6
    const toLowerCase = (str) => str.toLowerCase()
    const removeSpaces = (str) => str.replace(/\s/g, '')
    const addPrefix = (str) => `prefix_${str}`

    const processString = compose(addPrefix, removeSpaces, toLowerCase)
    console.log(processString('Hello World')) // 'prefix_helloworld'

  2. 数学计算�?

    1
    2
    3
    4
    5
    6
    const double = (x) => x * 2
    const addTen = (x) => x + 10
    const square = (x) => x * x

    const calculate = compose(square, addTen, double)
    console.log(calculate(5)) // (5 * 2 + 10)² = 400

  3. **数据处理�?*�?

    1
    2
    3
    4
    5
    6
    const filterEven = (arr) => arr.filter((x) => x % 2 === 0)
    const multiplyAll = (arr) => arr.map((x) => x * 2)
    const sum = (arr) => arr.reduce((a, b) => a + b, 0)

    const processNumbers = compose(sum, multiplyAll, filterEven)
    console.log(processNumbers([1, 2, 3, 4, 5, 6])) // 2*2 + 4*2 + 6*2 = 24

注意事项�?

  1. compose 函数从右到左执行，�?pipe 函数从左到右执行
  2. 确保函数的输入输出类型匹�?3. 处理异步操作时需要使�?async/await 版本
  3. 考虑错误处理机制
  4. 函数组合应该保持纯函数的特�?
    compose 函数是函数式编程中的重要工具，它能够帮助我们构建更加模块化和可维护的代码。通过组合小的、单一功能的函数，我们可以构建出复杂的数据转换管道�?
    :::

手写一�?LRU 缓存

::: details 参考答�?
LRU（Least Recently Used）是一种缓存淘汰策略，它会优先删除最近最少使用的数据。下面提供两种实现方式：使用 Map 的简单实现和不使�?Map 的基础实现�?

  1. 使用 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
    35
    36
    class LRUCache {
      constructor(capacity) {
        this.cache = new Map()
        this.capacity = capacity
      }

      get(key) {
        if (!this.cache.has(key)) return -1

        // 将访问的元素移到最新使用的位置
        const value = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, value)
        return value
      }

      put(key, value) {
        // 如果 key 已存在，先删�?    if (this.cache.has(key)) {
          this.cache.delete(key)
        }
        // 如果达到容量限制，删除最久未使用的元�?    else if (this.cache.size >= this.capacity) {
          // Map �?keys() 会按插入顺序返回�?      const firstKey = this.cache.keys().next().value
          this.cache.delete(firstKey)
        }

        this.cache.set(key, value)
      }
    }

    // 使用示例
    const cache = new LRUCache(2)
    cache.put(1, 1) // 缓存�?{1=1}
    cache.put(2, 2) // 缓存�?{1=1, 2=2}
    console.log(cache.get(1)) // 返回 1
    cache.put(3, 3) // 删除 key 2，缓存是 {1=1, 3=3}
    console.log(cache.get(2)) // 返回 -1 (未找�?

  2. 使用双向链表的实现（不依�?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
    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
    // 双向链表节点
    class Node {
      constructor(key, value) {
        this.key = key
        this.value = value
        this.prev = null
        this.next = null
      }
    }

    class LRUCache {
      constructor(capacity) {
        this.capacity = capacity
        this.cache = {} // 哈希表用于O(1)查找
        this.count = 0
        // 创建头尾哨兵节点
        this.head = new Node(0, 0)
        this.tail = new Node(0, 0)
        this.head.next = this.tail
        this.tail.prev = this.head
      }

      // 将节点移到双向链表头�?  moveToHead(node) {
        this.removeNode(node)
        this.addToHead(node)
      }

      // 从链表中删除节点
      removeNode(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
      }

      // 在链表头部添加节�?  addToHead(node) {
        node.prev = this.head
        node.next = this.head.next
        this.head.next.prev = node
        this.head.next = node
      }

      // 删除链表尾部节点
      removeTail() {
        const node = this.tail.prev
        this.removeNode(node)
        return node
      }

      get(key) {
        if (key in this.cache) {
          const node = this.cache[key]
          this.moveToHead(node)
          return node.value
        }
        return -1
      }

      put(key, value) {
        if (key in this.cache) {
          // 如果 key 存在，更新值并移到头部
          const node = this.cache[key]
          node.value = value
          this.moveToHead(node)
        } else {
          // 创建新节�?      const newNode = new Node(key, value)
          this.cache[key] = newNode
          this.addToHead(newNode)
          this.count++

          // 如果超过容量，删除最久未使用�?      if (this.count > this.capacity) {
            const tail = this.removeTail()
            delete this.cache[tail.key]
            this.count--
          }
        }
      }
    }

    // 使用示例
    const cache = new LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    console.log(cache.get(1)) // 返回 1
    cache.put(3, 3) // 删除 key 2
    console.log(cache.get(2)) // 返回 -1 (未找�?
    cache.put(4, 4) // 删除 key 1
    console.log(cache.get(1)) // 返回 -1 (未找�?
    console.log(cache.get(3)) // 返回 3
    console.log(cache.get(4)) // 返回 4

实现原理说明�?

  1. Map 实现版本�?
    • 利用 Map 的特性，它能够记住键的原始插入顺�? - get 操作时将访问的元素移到最后（最新使用）
    • put 操作时如果超出容量，删除第一个元素（最久未使用�?
  2. 双向链表实现版本�? - 使用哈希表实�?O(1) 的查�? - 使用双向链表维护数据的使用顺�? - 最近使用的数据放在链表头部
    • 最久未使用的数据在链表尾部

性能分析�?

  1. **时间复杂�?*�?

    • get 操作：O(1)
    • put 操作：O(1)

  2. **空间复杂�?*�? - O(capacity)，其�?capacity 是缓存的容量

使用场景�?

  1. **浏览器缓�?*�?

    1
    2
    3
    const browserCache = new LRUCache(100)
    browserCache.put('url1', 'response1')
    browserCache.put('url2', 'response2')

  2. 内存缓存�?

    1
    2
    3
    const memoryCache = new LRUCache(1000)
    memoryCache.put('userId1', userDataObject1)
    memoryCache.put('userId2', userDataObject2)

  3. **数据库查询缓�?*�?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    const queryCache = new LRUCache(50)
    function query(sql) {
      const cached = queryCache.get(sql)
      if (cached !== -1) return cached

      const result = executeQuery(sql)
      queryCache.put(sql, result)
      return result
    }

:::

使用 Vue3 Composable 组合式函数，实现 useCount

1
const { count } = useCount() // count 初始值是 0 ，每一�?count �?1

::: details 参考答�?

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
import { ref, onMounted, onUnmounted } from 'vue'

export function useCount() {
  const count = ref(0)
  let timer = null

  // 开始计�?  const startCount = () => {
    timer = setInterval(() => {
      count.value++
    }, 1000)
  }

  // 组件挂载时开始计�?  onMounted(() => {
    startCount()
  })

  // 组件卸载时清除定时器
  onUnmounted(() => {
    if (timer) {
      clearInterval(timer)
    }
  })

  return {
    count,
  }
}

:::

使用 Vue3 Composable 组合式函数，实现 useRequest

1
const { loading, data, error } = useRequest(url) // 可只考虑 get 请求

::: details 参考答�?

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
import { ref } from 'vue'

export function useRequest(url) {
  const data = ref(null)
  const loading = ref(false)
  const error = ref(null)

  const fetchData = async () => {
    loading.value = true
    error.value = null

    try {
      const response = await fetch(url)
      if (!response.ok) {
        throw new Error(`HTTP error! status: ${response.status}`)
      }
      data.value = await response.json()
    } catch (e) {
      error.value = e
    } finally {
      loading.value = false
    }
  }

  // 立即执行请求
  fetchData()

  return {
    data,
    loading,
    error,
  }
}

:::

使用 React Hook 实现 useCount

1
// count �?0 计数，每一�?+1 （可使用 setInterval�?const { count } = useTimer()

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import { useState, useEffect } from 'react'

function useTimer() {
  const [count, setCount] = useState(0)

  useEffect(() => {
    const timer = setInterval(() => {
      setCount((prev) => prev + 1)
    }, 1000)

    // 清理函数，组件卸载时清除定时�?    return () => clearInterval(timer)
  }, [])

  return { count }
}

export default useTimer

:::

使用 React Hook 实现 useRequest

1
const { loading, data, error } = useRequest(url) // 可只考虑 get 请求

::: details 参考答�?

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
import { useState, useEffect } from 'react'

function useRequest(url) {
  const [data, setData] = useState(null)
  const [loading, setLoading] = useState(true)
  const [error, setError] = useState(null)

  useEffect(() => {
    const fetchData = async () => {
      setLoading(true)
      setError(null)

      try {
        const response = await fetch(url)
        if (!response.ok) {
          throw new Error(`HTTP error! status: ${response.status}`)
        }
        const result = await response.json()
        setData(result)
      } catch (e) {
        setError(e)
      } finally {
        setLoading(false)
      }
    }

    fetchData()
  }, [url])

  return { data, loading, error }
}

export default useRequest

:::

手写 VNode 对象，表示如�?DOM 节点

1
2
3
4
<div class="container">
  <img src="x1.png" />
  <p>hello</p>
</div>

::: details 参考答�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const vnode = {
  tag: 'div',
  props: {
    class: 'container',
  },
  children: [
    {
      tag: 'img',
      props: {
        src: 'x1.png',
      },
    },
    {
      tag: 'p',
      props: {},
      children: ['hello'],
    },
  ],
}

:::