One, the Map

Is essentially a collection of key-value pairs (Hash structures) whose keys and values can be of any data type.

1. Grammar

new Map([iterable])
Copy the code
  • The argument [iterable] can be an array or other iterable whose elements are either key-value pairs or arrays of two elements. Each key-value pair is added to a new Map, and null is treated as undefined.
  • When iterating over Map objects in insertion order, for example for… Of returns an array of [key, value] for each iteration.
  • Based on the SameValueZero algorithm,NaNIs with theNaNSimilarly, other values are equal based on the result of the === operator.
let m = new Map()

m.set(-0.111)
m.get(+0) / / 111

m.set(true.1)
m.set('true'.2)
m.get(true) / / 1
m.get('true') / / 2

m.set(undefined.3)
m.set(null.4)
m.get(undefined) / / 3

m.set(NaN.123)
m.get(NaN) / / 123
Copy the code

Map keys are bound to memory addresses. As long as the memory addresses are different, they are regarded as two keys.

2. The attribute

const m = new Map
// Map(0) {size: 0}
Copy the code
  • Map.prototype.set(key, value) : Sets the key and value and returns the Map object.
m.set('a'.1)  // Map(1) {'a' => 1}
m.set(2.'b')  // Map(2) {'a' => 1, 2 => 'b'}
m.set(undefined.'c') // Map(3) {'a' => 1, 2 => 'b', undefined => 'c'}
Copy the code

If the same key is assigned more than once, the next value overwrites the previous value

  • Map.prototype.get(key): Returns the value of the key, or undefined if none exists.
m.get('a') / / 1
m.get(2) // 'b'
m.get(undefined) // 'c'
Copy the code
  • Map.prototype.size: Returns the number of key-value pairs of the Map object.
m.size / / 3
Copy the code
  • Map.prototype.has(key): Returns a Boolean value indicating whether the Map instance contains the value corresponding to the key.
m.has('a') // true
Copy the code
  • Map.prototype.delete(key): Removes the value associated with the key and returns a Boolean value. This value will be deleted successfully and return true, but not false.
m.delete('a') // true
m // Map(2) {2 => 'b', undefined => 'c'}
Copy the code
  • Map.prototype.clear(): Removes all elements in the Map.

3. Traversal method

The order of traversal is the order of insertion.

const m = new Map([['a'.1],
    ['b'.2]])Copy the code
  • Map.prototype.keys(): Returns all key names
m.keys() // 'a', 'b'
Copy the code
  • Map.prototype.values(): Returns all key values
m.values() / / 1. 2
Copy the code
  • Map.prototype.entries(): Returns all [key, value] members
m.entries() // {'a' => 1, 'b' => 2 }
Copy the code
  • Map.prototype.forEach(callbackFn(value, key, map) {}, thisArg): Traverses all members
    • parameter
      • The first argument (callbackFn) : is used to execute each element
      • Second argument (thisArg) : this to bind when executing the first argument
    • The return value undefined
    • Three arguments in callbackFn
      • Value: the value of the element
      • Key: The key of an element
      • Map: Collection object to traverse
m.forEach(function(value, key, map) { 
  console.log(`k[${key}] :${value}`)},this)
// k[a]:1, k[b]:2
Copy the code

4. Difference between Map and Object

Both Map and Object allow keys to access a value, delete keys, and detect whether a key is bound to a value. The difference between:

  • Objects have their own prototype, but starting with ES5 you can use Object.create (null) to create an object without a prototype. By default, Map contains no keys, only the keys that show insertion.
  • The keys of an object can only be strings or Symbols. The keys of a Map can be any value, including functions, objects, or any basic type.
  • The object’s keys are unordered, the Map’s keys are ordered, and when iterated, the keys are returned in insertion order.
  • The size attribute is used to obtain the number of key-value pairs in the Map. The number of key-value pairs in the object can only be obtained in other ways.
  • Map performs better when key pairs are frequently added or deleted.

Map usage scenarios:

  • Keys need to be queried dynamically
  • Value types are not uniform and can be interchanged
  • Key is not a string
  • Key-value pairs are often added/removed
  • There are any key-value pairs that are very easy to change
  • You can iterate (you can iterate over the map using the forEach() method)

Second, the Set

Similar to an array, but the values of the members are unique and cannot be duplicated. (So it can be used to do de-redo operations)

[...new Set(array)] // Use the extension operator (...) Quick conversion to array format
Copy the code

1. Grammar

new Set([iterable])
Copy the code
  • Iterable: If an iterable is passed, all its elements are added to the new Set. If this parameter is not specified or its value is null, the new Set is null.
  • A set object is a collection of values that can iterate over its elements in the order in which they are inserted.
  • Based on the same-value-Zero Equality algorithm, both NaN and undefined can be stored in a set, and NaN is treated as the Same value between NaN

2. The attribute

const s = new Set(a)// Set(0) {size: 0}
Copy the code
  • Set.prototype.add(value): Adds an element to the end of the Set. Returns the Set object.
s.add(1).add(2).add(2)
// Set(2) {1, 2}
Copy the code
  • Set.prototype.sizeReturns theSetThe total number of members of an instance.
s.size / / 2
Copy the code
  • Set.prototype.has(value): Returns a Boolean value indicating whether the value isSetA member of.
  • Set.prototype.delete(value): Deletes a value and returns a Boolean value indicating whether the deletion was successful.
  • Set.prototype.clear(): Clears all members with no return value.
  • Set.prototype.constructorThe: constructor is the defaultSetFunction.

3. Traversal method

  • Set.prototype.keys(): returns a traverser for key names
  • Set.prototype.values(): returns a traverser for key values
  • Set.prototype.entries(): returns a traverser for key-value pairs

Keys, values and entries are used in the same way as arrays. The set structure has no key names, only key values, keys and values return the same result, and entries return a map-like structure with key names equal to key values.

const s = new Set()
s.add('a').add('b').add('c')
s.entries() 
// ['a', 'a']
// ['b', 'b']
// ['c', 'c']
Copy the code

  • Set.prototype.forEach(callbackFn(value, key, map) {}, thisArg): Uses the callback function to iterate over each member, similar to map, where value and key output are the same.
s.forEach(function(value, key, map) { 
  console.log(`k[${key}] :${value}`)},this)
// k[a]:a
// k[b]:b
// k[c]:c
Copy the code

Originally intended to rearrange the map and set implementation principle, later did not see the source code, and the principle of related articles are very few, and so on after learning to supplement the complete, roughly and Java hashMap implementation principle is similar, but JS has no thread problem, mainly by linked lists, hash ideas and buckets to achieve. Why do we use linked lists? Hash conflict: When an element is hashed and a storage address is obtained, it is found that the address has been occupied by other elements. Since Map is like Object and set is like array, why come up with two new data structures? Because if you want to determine whether there is an element in the array, the existing methods is based on the underlying implementation based on the for loop iterates through implementation, the time complexity is O (n), and Set the underlying data structure is a hash table, the array in the underlying data structure is a linear table, is a continuous memory, according to an index lookup element is very fast, But according to the element search index can only traverse each array element according to the index, and then compare with the data element to find, for ordered array, we can use binary search, interpolation search, Fibonacci search, etc., can improve the time complexity to O(logn). The position of the element in the hash table is obtained according to the hash algorithm. When an element is to be found, the element is put into the algorithm for calculating the hash value to obtain the hash value. Modulo the length of the hash table can obtain the position of the element in the hash table (without considering the hash conflict, the time complexity is O(1)). Later, I will write a column to record leetcode’s brush problems. I will write a summary of problems solved with hash tables.