The article background

When LeeCode brushes the question, I have a new understanding of Map data structure, so I want to talk about Map data structure

Get into the business

Episode: Understanding a matter or thing, with the help of some scientific methodology, will make our thinking clearer, understanding more efficient; Let’s use the 5W2H analysis

The inventor uses five English words starting with W and two English words starting with H to ask questions, find clues to solve the problem, look for invention ideas, design ideas, so as to come up with a new invention project, which is called 5W2H method.

(1) WHAT is it? What is the purpose? What kind of work?

(2) WHY? Can we not do it? Is there an alternative?

(3) WHO? Who will do it?

(4) WHEN? When do you do it? When is the best time?

(5) WHERE? Where to do it?

(6) HOW do you do it? How to improve efficiency? How to implement it? What is the method?

(7) HOW MUCH? To what extent? How about quantity? What is the quality level? What about the cost output?

U.S. Army Ordnance Repair Department

5W2H provides us with an idea to analyze the problem. Let’s select several W and H for analysis

What is the Map

In standard (ECMA-262) terms, it is a constructor that requires the new operator;

In terms of data structure, it is similar to an object, which is also a collection of key-value pairs, but it is a hash table structure, which is a spatial and temporal tradeoff between an array and a linked list.

The essence of a map is to allow you to associate some additional information (values) with an object (key) without putting that information into the object itself.

Contains properties and methods

  • Map.size: Returns the number in the Map.
  • Map.prototype.set(key,value): Sets the key corresponding to key to value.
  • Map.prototype.get(key): Reads the key corresponding to the key.
  • Map.prototype.has(key): Checks whether a key is in the current Map object.
  • Map.prototype.delete(key): Deletes a key and returns a Boolean type.
  • Map.prototype.clear(key): Traverses all Map members.
  • Map.prototype.has(key): Traverses all Map members.
  • Map.prototype.keys(): returns a traverser for key names.
  • Map.prototype.values(): returns a traverser for key values.
  • Map.prototype.entries(): returns a traverser for all members.
  • Map.prototype.forEach(): Traverses all Map members.

For details, please refer to Teacher Ruan yifeng’s blog address or the introduction of Map on MDN

Why is there a Map

Traditional objects can only use strings as keys. This puts a great limit on its use. Map is a data structure whose “keys” are not limited to strings. Values of all types (including objects) can be used as keys, so it has a much broader scope than objects.

When to use Map

It is not used very much in the real world. Conceptually, Map is used when you are not sure of the type of key name in a key-value pair. In actual projects, Map data is not used much, but in hash algorithms, such as 49 in LeeCode. Alphabetic hash groups are grouped by the hash key of the alphabetic hash.

Ideas reflected by Map

Map is a hash structure, which was introduced in detail in Huang Shen’s Basic Mathematics Course for Programmers about ** remainder: The original mod operation itself is a hash function **

You’re probably familiar with hashes. In every programming language, there are Hash functions. Hashing is also sometimes translated as hashing. In simple terms, it is the compression of an input of any length into an output of a fixed length through hashing. Sound familiar? Isn’t that what we did with the mod up here? For example, if you want to read and write a million records quickly, the ideal way to achieve high-speed access is to create a contiguous space to store the data, thus reducing addressing time. However, due to constraints, we do not have a contiguous address space that can accommodate 1 million records. What should we do? We can see if the system can provide several small contiguous Spaces, each of which can hold a certain number of records. For example, if we find 100 small contiguous Spaces, that is, these Spaces are separated from each other, but are contiguous inside and large enough to hold 10,000 records continuously, then we can use the remainder and the homology theorem to design a hash function and realize the structure of hash table. So how do I design this function? You might want to stop and think about it, and mind you, you might want to think about the day of the week example again, because that’s the idea of remainder.

From “Fundamentals of Mathematics for Programmers”