Shulou(Shulou.com)06/01 Report--

This article mainly explains "JavaScript implementation hash table method", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let Xiaobian take you to learn "JavaScript implementation hash table method"!

Hashtables are usually implemented based on arrays, but they have many advantages over arrays:

It can provide very fast insert-delete-find operations

No matter how much data, inserting and deleting takes approximately constant time: that is, O(1) time. In fact, only a few machine commands are required to complete it.

Hash tables are faster than trees, and you can basically find the elements you want instantly.

Hash tables are much easier to encode than trees.

Some disadvantages of hash tables relative to arrays:

The data in the hash table is not ordered, so the elements cannot be traversed in a fixed way.

Usually, the keys in the hash table are not allowed to be repeated, and the same key cannot be placed, which is used to store different elements.

Space utilization is low, arrays are used at the bottom, and some cells are not utilized

What is a hash table?

Hash tables are not easy to understand, unlike arrays, linked lists, and trees, whose structure and principles can be represented graphically.

The structure of a hash table is an array, but its magic lies in a transformation of the subscript value, which we can call a hash function, through which HashCode can be obtained.

Some concepts of hash tables

Hashing: The process of converting large numbers into subscripts in an array range, called hashing;

Hash function: We usually convert words into large numbers, and put the code implementation of hashing large numbers in a function called hash function;

Hash table: the final data inserted into the array of the entire structure of the encapsulation, the result is the hash table.

Issues that still need to be addressed:

Hashed subscripts can still be duplicated. How to solve this problem? This situation is called conflict, conflict is inevitable, we can only resolve conflict.

conflict resolution

There are two common ways to resolve conflicts:

Scheme 1: Chain address method (zipper method);

As shown in the following figure, we take each number to 10 for remainder operation, then the range of remainder 0~9 as the index value of the array. Moreover, the position corresponding to each subscript value of the array is no longer a number, but an array or linked list composed of numbers that get the same remainder after the remainder operation.

Summary: Chain address method to solve the conflict is stored in each array unit is no longer a single data, but a chain, the chain often uses the data structure for the array or linked list, the efficiency of the two data structures is equivalent (because the chain elements are generally not too many).

Option 2: Open Address Law;

The main way open addressing works is to find empty cells to hold conflicting data items.

According to the different ways of detecting the position of blank cells, there are three methods:

linear probing

quadratic probing

rehashing

It can be seen that the average detection length increases linearly and gently with the increase of loading factor. Chain address method is used more in development, for example, chain address method is used in HashMap in Java.

Excellent hash function

The advantage of hash tables is their speed, so hash functions cannot be complex algorithms that consume high performance. One way to speed things up is to minimize multiplication and division in hash functions.

A high-performance hash function should have two advantages:

Fast calculations;

evenly distributed;

fast calculation

Horner's Law: In China Horner's Law is also called Qin Jiushao algorithm, and the specific algorithm is:

When calculating the value of polynomial, first calculate the value of first degree polynomial in the innermost bracket, and then calculate the value of first degree polynomial layer by layer from inside to outside. This algorithm transforms the value of polynomial f(x) of degree n into the value of polynomial f (x) of degree n.

Before transformation:

Multiplication times: n (n+1)/2 times;

Number of additions: n times;

After transformation:

Number of multiplications: n times;

Number of additions: n times;

If we use large O to represent the time complexity, we reduce it directly from O(N2) to O(N).

uniformly distributed

In order to ensure that the data is evenly distributed in the hash table, we try to use prime numbers when we need to use constants; for example, the length of the hash table, the base of the N power, etc.

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

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

function HashTable() { //store related elements this.storage = []; //How much data is stored this.count = 0; //used to mark how many elements are stored in the array this.limit = 7; /* Design hash function 1 Convert a string to a larger number 2. Compress large number hashCode into array range. */ HashTable.prototype.hashFunction = function (str, size) { var hashCode = 0; //Qin Jiushao algorithm (Horner algorithm) //The length of the hash table, the base of the Nth power, etc. Try to select prime numbers for (var i = 0; i

< str.length; i++) { // 34 43 43 都是常用的底数 hashCode = 37 * hashCode + str.charCodeAt(i); } return hashCode % size; }; // 插入和修改方法 HashTable.prototype.put = function (key, value) { // 根据key获取对应的index var index = this.hashFunction(key, this.limit); // 根据index取出对应的bucket var bucket = this.storage[index]; if (bucket == null) { bucket = []; this.storage[index] = bucket; } // 判断是否是修改数据 for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i]; if (tuple[0] === key) { tuple[1] == value; return; } } // 不是修改数据就添加数据 bucket.push([key, value]); this.count++; // 扩容 if (this.count >

this.limit * 0.75) { var newLimit = this.limit * 2; var prime = this.getPrime(newLimit); this.resize(prime); } }; //Get 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

< bucket.length; i++) { var tuple = bucket[i]; if (tuple[0] === key) { value == tuple[1]; return value; } } return null; }; // 删除 HashTable.prototype.remove = function (key) { var index = this.hashFunction(key, this.limit); var bucket = this.storage[index]; if (bucket == null) return null; for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i]; if (tuple[0] === key) { // 从i开始删除一个 bucket.splice(i, 1); this.count--; // 缩容 if (this.limit >

7 && this.count

< this.limit * 0.25) { var newLimit = Math.floor(this.limit / 2); var prime = this.getPrime(newLimit); this.resize(prime); } return tuple[1]; } } return null; }; // 扩容 HashTable.prototype.resize = function (newLimit) { var oldStorage = this.storage; // 充值所有的属性 this.storage = []; this.count = 0; this.limit = newLimit; for (var i = 0; i < this.limit; i++) { var bucket = oldStorage[i]; if (bucket == null) { continue; } for (var j = 0; j < bucket.length; j++) { var tuple = bucket[j]; this.put(tuple[0], tuple[1]); } } }; // 为空？ HashTable.prototype.isEmpty = function () { return 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 < this.limit; i++) { var arr = this.storage[i]; if (arr != undefined) { str += '['; for (var j = 0; j < arr.length; j++) { var bucket = arr[j]; str += '[' + bucket[0] + ',' + bucket[1] + ']'; if (j != arr.length - 1) { str += ','; } } str += ']'; if (i != this.limit - 1) { str += ','; } } else { str += '[]'; if (i != this.limit - 1) { str += ','; } } } return str; }; HashTable.prototype.isPrime = function (num) { if (num

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.