Yesterday I wandered along the riverbank/to where the reeds stooped to drink

By the way please chimney/write me a long letter in the sky

Scribble is a little/and my heart is as bright as the candle before your window/a little ambiguous/inevitable/due to the wind

— Love, Because of the Wind

Welcome to Star: Pocket-LoDash

Gitbook will also be updated with the warehouse. Gitbook address: Pocket-Lodash

Function and Usage

Using Hash caching was described earlier in The LoDash Source Code Analysis of Hash Caching. As described in this article, LoDash intends to implement the same interface as Map.

In fact, Hash is used to cache objects, but objects have one limitation: the key can only be a string or Symbol type, while Map supports various types of values as keys. Therefore, Hash cache cannot completely simulate the behavior of Map. When a key is an array or object, the Hash cache cannot completely simulate the behavior of Map. Hash can’t do that.

So, in an environment where maps are not supported, LoDash implements ListCache, which essentially uses a two-dimensional array to store data.

ListCache is called the same way as Hash:

new ListCache([
  [{key: 'An Object Key'}, 1],
  [['An Array Key'].2],
  [function(){console.log('A Function Key')},3]])Copy the code

The result is as follows:

{
  size: 3.__data__: [[{key: 'An Object Key'}, 1],
    [['An Array Key'].2],
    [function(){console.log('A Function Key')},3]]}Copy the code

The structure is similar to Hash, but __data__ becomes an array.

Interface design

The ListCache interface is the same as the Hash interface and implements the Map data management interface.

Rely on

import assocIndexOf from './assocIndexOf.js'
Copy the code

Lodash source Code Analysis: Two Forms of Decrement

Source code analysis

class ListCache {

  constructor(entries) {
    let index = - 1
    const length = entries == null ? 0 : entries.length

    this.clear()
    while (++index < length) {
      const entry = entries[index]
      this.set(entry[0], entry[1])
    }
  }

  clear() {
    this.__data__ = []
    this.size = 0
  }

  delete(key) {
    const data = this.__data__
    const index = assocIndexOf(data, key)

    if (index < 0) {
      return false
    }
    const lastIndex = data.length - 1
    if (index == lastIndex) {
      data.pop()
    } else {
      data.splice(index, 1)} -this.size
    return true
  }

  get(key) {
    const data = this.__data__
    const index = assocIndexOf(data, key)
    return index < 0 ? undefined : data[index][1]
  }

  has(key) {
    return assocIndexOf(this.__data__, key) > - 1
  }

  set(key, value) {
    const data = this.__data__
    const index = assocIndexOf(data, key)

    if (index < 0) {
      ++this.size
      data.push([key, value])
    } else {
      data[index][1] = value
    }
    return this}}Copy the code

constructor

The constructor, like Hash, calls the clear method and then the set method to add the initial data to the cache.

The clear method is not called to clear the data, since we haven’t started using the class yet, and there is certainly no data, but to initialize __data__ and size properties.

clear

clear() {
  this.__data__ = []
  this.size = 0
}
Copy the code

Clear is to clear the cache.

Set __data__ to an empty array, Hash to an empty object, and cache size to 0.

has

has(key) {
  return assocIndexOf(this.__data__, key) > - 1
}
Copy the code

Has determines whether cached data already exists, and returns true if the cached data already exists.

As explained in previous articles, assocIndexOf detects the indexOf the [key,value] array corresponding to a key in a two-dimensional array. The behavior of the assocIndexOf is the same as that of indexOf. If the index does not exist in a two-dimensional array, -1 is returned, otherwise the index is returned. Therefore, the value greater than -1 can be used to determine whether the data with the specified key has been cached.

set

set(key, value) {
  const data = this.__data__
  const index = assocIndexOf(data, key)

  if (index < 0) {
    ++this.size
    data.push([key, value])
  } else {
    data[index][1] = value
  }
  return this
}
Copy the code

Set is used to increment or update values that need to be cached. When setting, you need to maintain both size and cached values.

As with HAS, we call assocIndexOf to find the index value for the specified key. If it is less than 0, the specified key is not cached. We need to increment size by 1, and add the cached data to the end of this.__data__.

Otherwise, update the value.

Obsessive-compulsive disorder sees has as greater than -1, where it can be quite uncomfortable to see it as less than 0.

get

get(key) {
  const data = this.__data__
  const index = assocIndexOf(data, key)
  return index < 0 ? undefined : data[index][1]}Copy the code

The get method takes the value from the cache.

If there is a value in the cache, return the value in the cache, otherwise return undefined.

delete

delete(key) {
  const data = this.__data__
  const index = assocIndexOf(data, key)

  if (index < 0) {
    return false
  }
  const lastIndex = data.length - 1
  if (index == lastIndex) {
    data.pop()
  } else {
    data.splice(index, 1)} -this.size
  return true
}
Copy the code

The delete method is used to delete the cache for the specified key. Returns true on success, false otherwise. Deleting also requires maintaining the size attribute.

The assocIndexOf is first called to find the cached index.

If the index is less than 0, it indicates that there is no cache and the deletion is unsuccessful.

If the cache to be deleted is the last item in the cache, the pop method is called directly to remove the cache, otherwise the splice method is called to remove the cache at the corresponding location.

Why not just use Splice to delete data? Since POP performed better than Splice, I did a quick test and found it about 17% faster.

If you’re interested in the specification for POP and Splice, splice does a lot more than POP.

Here again, you can see loDash’s extreme pursuit of performance.

Finally, reduce the cache size by 1.

reference

  1. Set and Map data structures
  2. MDN: Use objects
  3. ECMAScript5.1 Chinese Version + ECMAScript3 + ECMAScript

License

CC BY-NC-ND 4.0

Finally, all articles will be simultaneously sent to the wechat public account, welcome to pay attention to, welcome to comment:

Akik The opposite corner