Detailed introduction to how JavaScript implements hash tables

This article brings you relevant knowledge about javascript, which mainly introduces related issues about how JavaScript implements hash tables, and encapsulates the entire structure of the array into which the final data is inserted. , what you get is the hash table, I hope it will be helpful to everyone.

Related recommendations: javascript learning tutorial

Hash tables are usually implemented based on arrays. But it has many advantages over arrays:

1. It can provide very fast insert-deletion-find operations
2. No matter how much data, insertion and deletion need to be close to constant time: that is, O(1) time level. In fact, it only takes a few machine instructions to do it.
3. The hash table is faster than the tree, and you can basically find the desired element instantly
4. The hash table is much easier to code than the tree

Some shortcomings of hash tables compared to arrays:

1. The data in the hash table is not in order, so it cannot be traversed in a fixed way. The elements
2. Normally, the keys in the hash table are not allowed to be repeated, and the same key cannot be placed. It is used to save different elements
3. The space utilization is not high, and the bottom layer uses is an array, and some cells are not utilized

What is a hash table?

• Hash tables are not easy to understand, unlike arrays, linked lists, and trees, which can express their structure and principles in the form of graphics.
• The structure of the hash table is an array, but its magic lies in a transformation of the subscript value, which we can call Hash function, HashCode can be obtained through the hash function.

Some concepts of hash tables

• Hashing: Convert large numbers The process of forming a subscript within the array range is called hashing;
• Hash function: We usually use Word is converted into big number, and the code implementation of big number for hashing is placed in a function, which is called Hash function;
• Hash table: Encapsulate the entire structure of the array inserted into the final data, and get is the hash table.

Problems that still need to be solved:

• The hashed subscript is still possibleDuplicate, how to solve this What's the problem? This situation is called conflict. Conflict is inevitable, and we can onlysolve the conflict.

Methods to resolve conflicts

Two common solutions to resolve conflicts:

• Option 1:Chain address Method(zipper method);

As shown in the figure below, we will perform the remainder operation on 10 for each number, then the remainder The range 0~9 is used as the subscript value of the array. Moreover, the position corresponding to each subscript value in the array no longer stores a number, but stores an array or linked list## composed of numbers that have the same remainder after a remainder operation. #.

Summary: The way to resolve conflicts with the chain address method is that the data stored in each array unit is no longer A single data , but a chain. The commonly used data structure for this chain is array or linked list. The search efficiency of the two data structures is equivalent (because the elements of the chain are generally Not too much).

Option 2:
• Open address method;

The main working method of the open address method is

Looking for blank cells To place conflicting data items.

According to the different ways of detecting the position of blank cells, it can be divided into three methods:

• Linear detection
• Secondary detection
• Rehashing method

It can be seen that as the loading factor increases, the average The detection length increases linearly and gently. The chain address method is often used in development. For example, the HashMap in Java uses the

chain address method.

Excellent hash function

The advantage of a hash table is its speed, so the hash function cannot use complex algorithms that consume high performance. One way to improve speed is to

minimize multiplications and divisions in the hash function.

A high-performance hash function should have the following two advantages:

• Fast calculation;
• Uniform distribution;

Quick calculation

Horner's Law: In China, Horner's Law is also called Qin Jiushao's Algorithm. The specific algorithm is:

When finding the value of a polynomial, First, calculate the value of the linear polynomial in the innermost bracket, and then calculate the value of the linear polynomial layer by layer from the inside out. This algorithm converts the value of n degree polynomial f(x) into the value of n degree polynomials.

Before transformation:

• Number of multiplications: n(n 1)/2 times;
• Number of additions: n times;

After transformation:

• Number of multiplications: n times;
• Number of additions: n times;

If big O is used to represent the time complexity, it will directly drop from O(N2) before transformation to O(N).

Uniform distribution

In order to ensure that the data is evenly distributed in the hash table, when we need touse constants, try to use Prime numbers; For example: the length of the hash table, the base of Nth power, etc.

HashMap in Java uses the chain address method, and the hashing method uses the formula: index = HashCode (key) & (Length-1)

That is to say, the data is converted into binary for and operations instead of remainder operation. In this way, the computer directly operates on binary data, which is more efficient. However, JavaScript will have problems when performing and operations called big data, so the remainder operation will still be used when using JavaScript to implement hashing.

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i  7 && this.count  0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i <p><detailed introduction to how javascript implements hash tables src="https://Detailed%20introduction%20to%20how%20JavaScript%20implements%20hash%20tables.php.cn/upload/article/000/000/067/4ca10f86d3fe737c57c2ff0ae29c077f-3.png" alt="Detailed introduction to how JavaScript implements hash tables"></detailed></p><p>Related recommendations: <a href="https://www.php.cn/course/list/17.html" target="_blank">javascript learning tutorial</a><br></p>

The above is the detailed content of Detailed introduction to how JavaScript implements hash tables. For more information, please follow other related articles on the PHP Chinese website!