0x01 Basic Concepts

  1. ES5: Object, Array

  2. ES6: Map, Set

  3. None: Dictionary, list, Linkedlist, DoublelinkedList, queue, stack, hash

1.1 compatibility

  1. The PC browser is compatible with Internet Explorer 11+

  2. Mobile browsers are better

  3. NodeJs is the most compatible and has been supported since version 0. X

1.2 contrast

You will often compare Map with Object, Set with Array. This time we will focus on the differences between them.

0x02 Set

2.1 concept

  1. 3. In mathematics, a set is a set of distinct objects;

  2. A set in a data structure: a set is an unordered and unique set of items, using the same mathematical concepts as a finite set. It can be thought of as an array with neither repeating elements nor the concept of order;

  3. Collections in JavaScript: added the Set class in ECMAScript6;

2.2 Basic Methods

2.3 Common Operations

Sets can easily implement unions, intersects, and differences

2.3.1 Intersection (Intersect)

Read: “A hands in B”

2.3.2 Union

Read: “A and B” (or “B and A”)

2.3.3 Difference

Read: B is A relative complement to A

let a = new Set([1, 2, 3]); let b = new Set([4, 3, 2]); Let union = new Set([...a,...b]); / / the Set {1, 2, 3, 4} / / intersection let intersects = new Set ([...] a filter (x = > b.h as (x))); // set {2, 3} let difference = new set ([... A].filter(x =>! b.has(x))); // Set {1}Copy the code

2.4 Converting a Set to an Array

let arr = [3, 5, 2, 2, 5, 5]; // Array => set let mySet = new set (arr); // set => array let myArr = [...mySet]; Let myArr2 = Array. From (mySet) let myArr2 = Array. From (mySetCopy the code

0x03 Map

3.1 Basic Methods

Will know way

3.2 Differences between Map and Object

The differences between MDN-Objects and MAPS are as follows:

  1. Key of the conflict

  2. The type of the key

  3. The order of the keys

  4. Size

  5. The iteration

  6. performance

This time focus on key types, key order, performance.

3.2.1 Key Type

Code 🌰 1:

const myObject = Object.create(null, { 
    m: {value: function() {}, enumerable: true}, 
    "2": {value: "2", enumerable: true}, 
    "b": {value: "b", enumerable: true}, 
    0: {value: 0, enumerable: true}, 
    "1": {value: "1", enumerable: true}, 
    "a": {value: "a", enumerable: true}, 
});
Copy the code

3.2.2 Sequence of keys

Order of Object keys

1. Integer like key, returned in ascending order (and strings like “1” that parse as ints)

2. String key is inserted in order (ES2015 avoids this and all browsers).

3. The Symbols are arranged in the order that ES2015 avoids this and all browsers.

Refer to the article

💡 Warm tips:

  1. Do not use object.keys () separately from object.values (), which may raise a key-value pair that does not match

  2. Object.keys, Object.entries, Object.values, for.. In these methods, on the iteration of Object, the order is not reliable

  3. Don’t trust the order of objects; use Map or Array instead

3.2.3 Performance Difference

Object and ES 6 maps are mostly hashes. How efficient do they compare?

// Initialize a map and an object as follows: var map = new map (); var obj = {}; var size = 100000; for(var i = 0; i < size; i++){ map.set('key' + i , i); obj['key' + i] = i; } // Create an array of keys to store the keys to be searched. 2. Only half the keys can be found. Var keys = []; for(var i = 0; i < 100; Keys. push('key' + parseInt(math.random () * size)); //keys.push('key' + parseInt(math.random () * size * 2)); //keys.push('key' + parseInt(math.random () * size) + size); } var count = 100000;} console.time("map time"); for(var i = 0; i < count; i++){ for(var j = 0; j < keys.length; j++){ let x = map.get(keys[j]); } } console.timeEnd("map time"); console.time("obj time"); for(var i = 0; i < count; i++){ for(var j = 0; j < keys.length; j++){ let x = obj[keys[j]]; } } console.timeEnd("obj time");Copy the code

1. Map and Object are similar in general and can be used as needed.

2. When keys cannot be found, map is more efficient than object.

3. It is recommended to use map, object, iteration order and prototype lookup when map is available;

0x04 Comparison between Set and Map

Must know the method comparison

0 x05 hash table

HashMap vs TreeMap

HashSet vs TreeSet

The time complexity of each data structure

5.1 Implementation of various languages

  1. Python: Dict dictionary HashMap

  2. Java, C#, and C++ : HashMap and TreeMap must be specified

  3. JavaScript: “Everything is object?”

💡 Let’s review the order of object.values () from above:

var data = { name: "yin", age: 18, "-school-": "high school", 1: "Monday", 2: "Thuesday", "3": "Wednesday" }; . /.. /v8/src/runtime/http://runtime-literals.cc 105 boilerplate obj: 0x3930221af3a9: [JS_OBJECT_TYPE] - map = 0x6712e19cc41 [FastProperties] - prototype = 0x27d71d20f19 - elements = 0x2e1e1a56b579 <FixedArray[19]> [FAST_HOLEY_ELEMENTS] - properties = 0x2c2a4d782241 <FixedArray[0]> { #name: 0x3930221aec51 <String[3]: yin> (data field at offset 0) #age: 18 (data field at offset 1) #-school-: 0x3930221aecb1 <String[11]: high school> (data field at offset 2) } - elements = { 0: 0x2c2a4d782351 <the hole> 1: 0x3930221aecf9 <String[6]: Monday> 2: 0x3930221aed39 <String[8]: Thuesday> 3: 0x3930221aed79 <String[9]: Wednesday> 4-18: 0x2c2a4d782351 <the hole> }Copy the code

5.2 Basic Concepts

The elements of a hash table are determined by the hash function. The key word K of the data element is taken as an independent variable, and the value calculated through a certain functional relationship (called a hash function) is the storage address of the element. Addr = HashFuction (key)

Two main problems need to be solved before a hash table can be constructed:

  1. Construct a proper hash function

  2. Conflict management

5.3 Hash functions

5.3.1 Types of hash functions

  1. Add a Hash

  2. A computing the Hash

  3. Multiplication Hash

  4. Divide the Hash

  5. The Hash table

  6. Mix the Hash

  7. An array of the Hash

5.3.2 Implementation of hash function

5.3.3 Application of hash functions

Scenario: implementation principle of AB Test in CMP

5.4 Hash Collisions

For example: 0 ~ 14 points in bucket A, 15~ 30 points in bucket B, for 117406, 406117 these two people will always fall in A

Note: In practice, the AB test of our company does not take modulo again, but directly uses the last digit after CRC32, there will be 0 ~ 9 tens digit, which is the bucket allocation strategy. The figure above is just to illustrate the common method.

0x06 Recommended exercises

This is often used to determine the same number of elements in an Array or String

6.1 Problem solving routines

6.1.1 the Set

Skilled use of Set properties, Set intersection, Set, Set difference, subset operations

6.1.2 the Map

169. Majority elements

// [2,2,1,1,1,2,2] => 2 var majorityElement = function(nums) {// [2,2,1,1,1,2,2] let I; let length = nums.length; let myMap = new Map(); for(i = 0; i < length; i++){ if(myMap.has(nums[i])){ myMap.set(nums[i], myMap.get(nums[i]) + 1); // Else {mymap.set (nums[I], 1)}} for (let [key, value] of mymap.entries ()) {if (value > length / 2) return key; }};Copy the code

0 x07 reference

  1. Map – JavaScript | MDN

  2. Set – JavaScript | MDN

  3. Introduction to ES6

  4. Chrome source code to see the implementation of JS Object

  5. The hash function

  6. V8 – Most object types in the V8 JavaScript are described in this file

  7. stackoverflow – Do Object.keys() and Object.values() methods return arrays that preserve the same order