An overview of the
When searching for unordered elements in an array, the array needs to be traversed, namely, the time complexity is O (n).
Hash tables can store data with o(n) space complexity, and then find out the location of storage through the hash function, so as to achieve a time complexity close to O (1) curD.
Objects_vs._maps js provides two specific implementations of Map and Object. There is no significant difference between objects_vs._maps.
This article discusses language-independent hash tables and implementations in JS.
Hash table implementation
For details, please refer to here.
The hash function
The hash function f(key) is the function that maps the data to the location in the array.
If different values go to the same hash address, this is called hash collision, and hash collision should be avoided as much as possible, but not completely.
A good hash function should be equally likely to be stored in every location for each value. Common ways to construct hash functions include
(1) After the keyword is divided by a number p not larger than the length of the hash table m, the remainder is the hash address. That is, f(key)=key % p, p≤m;
(2) Direct addressing method refers to taking the keyword or a linear function value of the keyword as the hash address. That is, f(key)=key or F (key)=a*key+ B
(3) The number analysis method assumes that the keyword is the number based on the base (such as the decimal number based on 10), and the possible keywords in the hash table are known in advance, then several digits of the keyword can be selected to form the hash table.
Handle hash conflicts
If a conflict occurs, that is, the calculated location already holds data, where should the current data be stored?
(1) Open addressing method when address conflict occurs, according to some method to continue to explore other storage units in the hash table, until the empty location is found. So one way to do this is to keep adding plus 1, or do it again with a hash function.
(2) Establish a public overflow area to maintain an overflow table to store the occupied data.
(3) Chain address method If conflict occurs, the current element will be inserted into the linked list at the target location. In extreme cases, all data will be saved in the linked list at the same location, and the search complexity is O (n).
A hashMap in Java uses this approach
If the extreme case of O (n) is simply solved, avL or red-black trees can be used instead of linked lists, and the time complexity is reduced to O (LGN).
Js hash table implementation
As a dynamic language, the location of properties is only known when running to a specific code, so it is impossible to define the location of each key-value pair and the size of allocated space during object creation like Java.
The implementation in js depends on the js engine (the mainstream engines implement it similarly), using Shape and inline cache.
The js object maps a key to a property attribute, which works without any additional information, such as [[Enumerable]], [[64x], and so on.
- How to quickly find the corresponding attribute value
- How to reduce data redundancy
Shape
The JS engine provides Shape to solve the above problems, which saves the corresponding attribute and the saved position (offset) of the attribute.
The same objects share the same Shape, and the same criteria means that the corresponding attributes are added in the same order.
If you add properties to an object, Shape creates Transition Chains, where your Shape holds the properties you just added.
Inline Caches
In extreme cases, if each attribute is added, the lookups for each attribute become O (n) again, thus introducing inline cache.
Every time a function is called and an object is used as a parameter, the transition Chains will cache the position of the corresponding attribute, and the next time it will be read directly, greatly improving the access speed.
Related to the sample
Hash table can be used to count the number of times. You can directly use map or object, such as the sum of two numbers.