JavaScript implements hash tables

Hash table introduction

1.1. Know hash tables

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

• Hash tables can provide very fast insert-delet-find operations;
• Regardless of the amount of data, inserting and deleting values takes only a very short amount of time, in order of O(1) time. In fact, it only takes a few machine instructions;
• A hash table is faster than a tree and can find the desired element almost instantaneously. But it’s much easier to code than a tree.

Hash tables also have their drawbacks:

• The data in a hash table is not ordered, so you cannot traverse its elements in a fixed way (from small to large, for example).
• In general, the keys in a hash table are not allowed to be duplicated. The same key cannot be placed to hold different elements.

What is a hash table?

• Hash tables are not easy to understand, unlike arrays, linked lists, and trees, whose structure and principles can be graphically represented.
• The structure of a hash table is an array, but the magic of it is a transformation of the underlying values, which we can call a hash function, through which we get HashCode.

Learn about hash tables through the following examples:

• Case 1: The company wants to store the information of 1000 people, and each employee id corresponds to one employee’s information. If the array is used, it is troublesome to add and delete data. With linked lists, getting data is cumbersome. Is there a data structure that translates an employee’s name into a corresponding employee number and then looks up the full information about that employee based on that employee number? That’s right, and then you can use the hash function of the hash table.
• Case 2: Store contacts and corresponding phone numbers: When looking for a number for example, if you use an array: Because you do not know the subscript value of the storage data object, it is very difficult to find it, and the same is true for linked lists. And the use of hash table can be through the hash function to change the name of zhang SAN into its corresponding subscript value, and then through the subscript value search efficiency is very high.

In other words, the hash table is still based on data, but the hash table can use hash functions to transform strings into corresponding subscripts, and establish the corresponding relationship between strings and subscripts.

1.2. Hashing

To convert strings into subscripts, you need a coding system. To make things easier to understand, let’s create a coding system that says, for example, a is 1, b is 2, C is 3, and so on, z is 26, space is 27 (regardless of capitalization).

With a coding system, there are many ways to convert letters into numbers:

• Method 1: add numbers. For example, if cats is converted to a number: 3+1+20+19=43, store 43 in the array as the subscript of the word cats.

  There is a problem with this method: many words turn out to be 43 this way, such as was. In an array, each subscript value can store only one data, so this approach does not make sense.

• Method two: power multiplication. The number greater than 10 that we usually use is a power multiple to indicate its uniqueness. For example: 6543=6 * 103 + 5 * 102 + 4 * 10 + 3; Cats = 3 * 273 + 1 * 272 + 20 * 27 + 17 =60337;

  This ensures character uniqueness, but long characters (such as aaaaAAaaaa) represent large numbers, which requires a large array with many subscripts pointing to invalid data (such as the absence of words such as ZXCVVV), resulting in a waste of array space.

Summary of the two schemes:

• The first scheme (adding and summing numbers) produces too few subscripts;
• The second option (summing by a power of 27) produces too many subscripts;

Now a compression method is needed to compress the large integer range obtained in the power multiplication scheme system into an acceptable array range. This can be done with a mod operation. Although it is possible to duplicate the structure resulting from the mod operation, it can be solved in other ways.

Some concepts of hash tables:

• Hash: The process of converting a large number into an array range index, called hash;
• Hash function: We usually convert words into large numbers, and the code implementation of the hash of large numbers is put in a function, which is called the hash function;
• Hash table: Encapsulates the entire structure of the array into which the final data is inserted, resulting in a hash table.

Problems that still need to be solved:

• How to solve the problem that the hashed subscripts may still repeat? This situation is called conflict, conflict is inevitable, we can only resolve conflict.

1.3. Methods of conflict resolution

There are two common solutions to conflict resolution:

• Scheme 1: chain address method (zipper method);

As shown in the figure below, we mod each number to 10, so the remainder ranges from 0 to 9 as the subscript value of the array. And instead of storing a number at the location of each subscript, the array stores an array or linked list of numbers that have the same remainder after a mod operation.

This will get the entire array or list based on the subscript value, and then continue to look up the array or list. Also, there are generally not too many elements for conflict.

Summary: The link address method solves the conflict by storing a chain instead of a single data in each array cell. The data structure commonly used in this chain is array or linked list, and the efficiency of the two data structures is similar (because the chain usually does not have too many elements).

• Scheme 2: open address method;

The main way the open address method works is to find blank cells to place conflicting data items.

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

• Linear detection
• Second detection
• Then the hash method

1.4. Ways to find blank cells

Linear detection

When 13 is inserted:

• The hash (mod 10) results in index=3, but the data 33 has already been placed there. Linear detection, on the other hand, starts from index position +1 and goes back one by one to find the appropriate position to place 13. The so-called “appropriate position” refers to the empty position, as shown in the figure above, where index=4 is the appropriate position.

When query 13:

• First, hash 13 to get index=3. If the data stored at index=3 is the same as the data 13 to be queried, it will be returned directly.
• If they are different, then the linear search is performed, starting at index+1 and looking for data 13 one by one;
• The query does not traverse the entire hash table, stopping as soon as it reaches an empty position, because 13 does not skip the empty position to insert another position.

When 13 is deleted:

• The delete operation is similar to the above two cases, but it is important to note that when deleting a data item, do not set the subscript content of the location to NULL, otherwise other query operations will be affected, because the search will stop once a null location is encountered.
• Usually when we delete an item at a location, we can make it special (such as -1) so that when we encounter -1 we know to keep looking.

Problems with linear detection:

• There is a serious problem in linear detection, which is aggregation.
• If 23, 24, 25, 26, and 27 are inserted before any element is inserted into the hash table, it means that data is placed at the lower values of 3, 4, 5, 6, and 7. This series of filling units is called aggregation.
• Aggregation affects hash table performance, whether it is insert/query/delete;
• For example, if you insert 13, you will find that sequential cells 3 through 7 do not allow data to be inserted, and you will have to go through this situation several times during the insertion process. The second detection method can solve this problem.

Second detection

Problems with linear detection mentioned above:

• If the previous data was inserted consecutively, the newly inserted data may need to be probed over a long distance;

  Secondary detection is optimized on the basis of linear detection:

• Linear detection: we can regard it as the detection of step 1, for example, starting from the table value x, then linear detection is based on the subscript value: X +1, x+2, x+3 and so on.

• Secondary detection: Step size is optimized, such as detection from subscript x: x+12, x+22, x+33. In this way, a long distance is detected at one time, avoiding the influence of data aggregation.

Problems of secondary detection:

• When inserting a set of data with a large data distribution, such as 13-163-63-2133, this situation will cause a clustering of different step sizes (although this is less likely than the clustering of linear detection), which also affects performance.

Then the hash

The best way to find empty cells in the open address method is to rehash:

• The step size of the secondary probe is fixed: 1,4,9,16 and so on;
• Now you need a way to generate a sequence of probes that depend on keywords (data), rather than having the same detection step for each keyword;
• In this way, different keys can use different probe sequences even if they map to the same array subscript;
• The method of rehash is: the keyword with another hash function, do the hash again, with the result of the hash as the step of the keyword;

The second hash needs to satisfy the following two points:

• It’s not the same as the first hash function, otherwise it’s going to be the same hash function;
• The output cannot be 0, otherwise each probe will be an infinite loop of marking time;

Good hash functions:

• StepSize = constant – (key % constant);
• Where constant is a prime number and smaller than the capacity of the array.
• For example: stepSize = 5 – (key % 5), meet the requirements, and the result cannot be 0;

Efficiency of hashing

It is very efficient to perform insert and search operations in hash tables.

• If there is no conflict, then efficiency is higher;
• If a conflict occurs, the access time depends on the length of subsequent probes;
• The average probe length, as well as the average access time, depends on the filling factor, which increases with the probe length.

Understand the concept loading factor:

• The loading factor represents the ratio of the data items already contained in the current hash table to the entire length of the hash table;
• Loading factor = Total data items/hash table length;
• The open address method has a maximum loading factor of 1, because only blank cells can fit elements;
• The chain-address method can have a loading factor greater than 1, because the zipper method can go on indefinitely if you want;

1.5. Comparison of performance of different detection methods

• Linear detection:

It can be seen that with the increase of the loading factor, the average detection length increases exponentially and the performance is poor. In practice, the best loading factor depends on the balance between storage efficiency and speed. As the loading factor becomes smaller, storage efficiency decreases while speed increases.

• Secondary detection and rehash performance:

Secondary detection and rehashing have similar performance, and their performance is slightly better than linear detection. As can be seen from the following figure, with the increase of the loading factor, the average detection length increases exponentially, and so does the number of detection needed, showing low performance.

• Performance of chain address method:

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

1.6. Excellent hash functions

The advantage of hash table is its speed, so the hash function can not use high consumption performance of complex algorithms. One way to speed things up is to minimize multiplication and division in hash functions.

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

• Quick calculation;
• Evenly distributed;

Fast calculation

Horner’s Law: In China horner’s law is also called Qin Jiushao algorithm, the specific algorithm is:

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

Before transformation:

• Multiplication times: n (n+1) /2 times;
• Number of addition: n times;

After transformation:

• Multiplication times: n times;
• Number of addition: n times;

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

Uniform distribution

To ensure that data is evenly distributed in the hash table, we use prime numbers where constants are needed; For example, the length of the hash table, the base of the N power, etc.

Index = HashCode (key) & (length-1)

The idea is to make the data binary and instead of mod. This makes computing binary data directly more efficient. However, JavaScript has problems with the sum operation called big data, so the following implementation of JavaScript hashing still adopts the mod operation.

Second, the initial package hash table

Common operations on hash tables are:

• Put (key, value) : Insert or modify operations.
• Get (key) : retrieves the element at a specific position in the hash table;
• Remove (key) : deletes the element at a specific position in the hash table.
• IsEmpty () : Returns trun if the hash table contains no elements, false if the hash table length is greater than 0;
• Size () : Returns the number of elements in the hash table;
• Resize (value) : expands the hash table.

2.1. Simple implementation of hash function

The value of hashCode is first computed using Horner’s rule and then hashed by resizing, simply specifying the size of the array.

// Design the hash function
//1. Convert the string to a larger number: hashCede
//2. Compress the large number hasCode into the array range (size)
function hashFunc(str, size) {
    //1. Define the hashCode variable
    let hashCode = 0;

    //2. Horner's rule, calculate the value of hashCode
    //cats -> Unicode encoding
    for (let i = 0; i < str.length; i++) {
        // str.charcodeat (I)// Get the Unicode encoding for a character
        hashCode = 37 * hashCode + str.charCodeAt(i);
    }

    //3. Mod operation
    let index = hashCode % size;
    return index;
}
Copy the code

Test code:

// Test the hash function
console.log(hashFunc('123'.7));
console.log(hashFunc('NBA'.7));
console.log(hashFunc('CBA'.7));
console.log(hashFunc('CMF'.7));
Copy the code

Test results:

2.2. Create hash tables

An array structure model for encapsulating hash tables:

First create the HashTable class HashTable, and add the necessary attributes and hash functions implemented above, and then implement the other methods.

// Encapsulate the hash table class
function HashTable() {
    / / property
    this.storage = [];
    this.count = 0; // Count the number of stored elements
    // loadFactor: loadFactor > 0.75 requires expansion; When loadFactor < 0.25, the capacity needs to be reduced
    this.limit = 7; // Initial length

    / / method
    // hash function
    HashTable.prototype.hashFunc = function(str, size) {
        //1. Define the hashCode variable
        let hashCode = 0;

        //2. Horner's rule, calculate the value of hashCode
        //cats -> Unicode encoding
        for (let i = 0; i < str.length; i++) {
            // str.charcodeat (I)// Get the Unicode encoding for a character
            hashCode = 37 * hashCode + str.charCodeAt(i);
        }

        //3. Mod operation
        let index = hashCode % size;
        return index;
    };

}
Copy the code

2.3. The put (key, value)

Insert and modify hash tables are the same function: when the user passes in a <key, value>, it is an insert if the key does not already exist, and it is a modify if the key already exists.

Implementation idea:

• First, obtain the index value index according to the key, in order to insert the data to the corresponding location of the storage.
• Then, the bucket is fetched based on the index value. If the bucket does not exist, the bucket is created and placed at the index value.
• Next, determine whether to add or modify the original value. If it already has a value, change it; If no, perform subsequent operations.
• Finally, add data.

Code implementation:

// Insert & modify operations
HashTable.prototype.put = function(key, value) {
    //1. Obtain the corresponding index based on the key
    let index = this.hashFunc(key, this.limit);

    //2. Retrieve the corresponding bucket according to index
    let bucket = this.storage[index];

    //3. Check whether the bucket is null
    if (bucket == null) {
        bucket = [];
        this.storage[index] = bucket;
    }

    //4. Check whether the data is modified
    for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i];
        if (tuple[0] == key) {
            tuple[1] = value;
            return; // Do not return a value}}//5. Perform the add operation
    bucket.push([key, value]);
    this.count += 1;
}
Copy the code

Test code:

// Test the hash table
//1. Create hash table
let ht = new HashTable()

//2. Insert data
ht.put('class1'.'Tom')
ht.put('class2'.'Mary')
ht.put('class3'.'Gogo')
ht.put('class4'.'Tony')
ht.put('class4'.'Vibi')
console.log(ht);
Copy the code

Test results:

2.4. The get (key)

Implementation idea:

• First, according to the key through the hash function to obtain its corresponding index in the storage index;
• Then, the corresponding bucket is retrieved based on the index value;
• If the bucket is null, null is returned.
• Next, we linearly iterate over whether each key in the bucket is equal to the incoming key. If equal, return value directly;
• Finally, if no corresponding key is found after traversing the bucket, return null.

// Get operation
HashTable.prototype.get = function(key) {
    //1. Obtain the corresponding index based on the key
    let index = this.hashFunc(key, this.limit)

    //2. Obtain the corresponding bucket according to index
    let bucket = this.storage[index]

    //3. Check whether the bucket is null
    if (bucket == null) {
        return null
    }

    //4. If there is a bucket, then do a linear search
    for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i];
        if (tuple[0] == key) { //tuple[0] stores keys, and tuple[1] stores values
            return tuple[1]}}//5. If no one is found, return null
    return null
}
Copy the code

Test code:

// Test the hash table
//1. Create hash table
let ht = new HashTable()

//2. Insert data
ht.put('class1'.'Tom')
ht.put('class2'.'Mary')
ht.put('class3'.'Gogo')
ht.put('class4'.'Tony')

//3. Obtain data
console.log(ht.get('class3'));
console.log(ht.get('class2'));
console.log(ht.get('class1'));
Copy the code

Test results:

2.5. The remove (key)

Implementation idea:

• First, according to the key through the hash function to obtain its corresponding index in the storage index;
• Then, the corresponding bucket is retrieved based on the index value;
• If the bucket is null, null is returned.
• Then, the bucket is linearly searched for the corresponding data and deleted.
• Finally, if it is still not found, null is returned;

Code implementation:

// Delete operation
HashTable.prototype.remove = function(key) {
    //1. Obtain the corresponding index based on the key
    let index = this.hashFunc(key, this.limit)

    //2. Obtain the corresponding bucket according to index
    let bucket = this.storage[index]

    //3. Check whether the bucket is null
    if (bucket == null) {
        return null
    }

    //4. If there is a bucket, do a linear search and delete it
    for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i]
        if (tuple[0] == key) {
            bucket.splice(i, 1)
            this.count -= 1
            return tuple[1]}}//5. If no, return null
    return null
}
Copy the code

Test code:

// Test the hash table
//1. Create hash table
let ht = new HashTable()

//2. Insert data
ht.put('class1'.'Tom')
ht.put('class2'.'Mary')
ht.put('class3'.'Gogo')
ht.put('class4'.'Tony')

//3. Delete data
console.log(ht.remove('class2'));
console.log(ht.get('class2'));
Copy the code

Test results:

2.6. Implementation of other methods

Other methods include: isEmpty(), size() :

// Check whether the hash table is null
HashTable.prototype.isEmpty = function() {
    return this.count == 0
}

// Get the number of elements in the hash table
HashTable.prototype.size = function() {
    return this.count
}
Copy the code

Test code:

// Test the hash table
//1. Create hash table
let ht = new HashTable()

//2. Insert data
ht.put('class1'.'Tom')
ht.put('class2'.'Mary')
ht.put('class3'.'Gogo')
ht.put('class4'.'Tony')

/ / 3. Test isEmpty ()
console.log(ht.isEmpty());
/ / 4. Test isEmpty ()
console.log(ht.size());
console.log(ht);
Copy the code

Test results:

Three, hash table expansion

3.1. Expansion and compression

Why does it need to be expanded?

• We used an array of length 7 in the hash table. Because the chained address method is used, the loadFactor can be greater than 1, so the hash table can insert new data without limit.
• However, as the amount of data increases, the bucket array (linked list) corresponding to each index in the storage becomes longer and longer, which reduces the efficiency of the hash table

When does the capacity need to be expanded?

• When loadFactor > 0.75, capacity expansion is performed.

How do I expand capacity?

• A simple expansion can be made twice as large (on prime numbers, discussed later);
• After capacity expansion, all data items must be modified synchronously.

Implementation idea:

• First, define a variable, such as oldStorage, to point to the original storage;
• Then, create a new, larger array and have this.storage point to it;
• Finally, take each bucket from each oldStorage and add it in turn to the new array pointed to by this.storage;

Code implementation:

// Hash table expansion
HashTable.prototype.resize = function(newLimit) {
    //1. Save the old storage array contents
    let oldStorage = this.storage

    //2. Reset all attributes
    this.storage = []
    this.count = 0
    this.limit = newLimit

    //3. Iterate over all buckets in oldStorage
    for (let i = 0; i < oldStorage.length; i++) {
        //3.1. Fetch the corresponding bucket
        const bucket = oldStorage[i];

        Check whether the bucket is null
        if (bucket == null) {
            continue
        }

        //3.3. If the bucket contains data, insert it again
        for (let j = 0; j < bucket.length; j++) {
            const tuple = bucket[j];
            this.put(tuple[0], tuple[1]) // Insert key and value of data}}}Copy the code

The resize method of hash table defined above can not only realize the expansion of hash table, but also realize the compression of hash table capacity.

Loading factor = data in the HashTable/length of the HashTable, that is, loadFactor = count/hashtable.length.

• Generally, when the loading factor laodFactor > 0.75, the hash table is expanded. Add the following code to the add method (push method) in the hash table to determine whether expansion function needs to be called for expansion:

// Determine whether an expansion operation is required
if (this.count > this.limit * 0.75) {
    this.resize(this.limit * 2)}Copy the code

• When the loading factor laodFactor < 0.25, the hash table capacity is compressed. Add the following code to the remove method in the hash table to determine whether the expansion function needs to be called for compression:

// Shrink the capacity
if (this.limit > 7 && this.count < this.limit * 0.25) {
    this.resize(Math.floor(this.limit / 2))}Copy the code

3.2. Select prime numbers as capacity

Prime number judgment

First of all, let’s review the ways to judge prime numbers:

Note that 1 is not prime

• Method 1: Primes are divisible only by 1 and num, but not by 2 to (num-1). Traverses 2 to (num-1).

function isPrime(num) {
    if (num <= 1) {
        return false
    }
    for (let i = 2; i <= num - 1; i++) {
        if (num % i == 0) {
            return false}}return true
}
Copy the code

Although this method can realize prime number judgment, it is not efficient.

• Method 2: Just iterate over the square root of 2 ~ num.

function isPrime(num) {
    if (num <= 1) {
        return false
    }
    Math.sqrt(num); //1.
    //2
    for (var i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false; }}return true;
}
Copy the code

The capacity of the expanded hash table is prime

Implementation idea:

After doubling the capacity, check whether the obtained capacity isPrime through the loop call isPrime. If it is not, +1 until it is. 14 is not prime, 14 + 1 = 15 is not prime, 15 + 1 = 16 is not prime, 16 + 1 = 17 is prime, stop the loop and get 17.

Code implementation:

• We need to add isPrime and getPrime methods to the HashTable class:

// Check whether num is prime
HashTable.prototype.isPrime = function(num) {
    if (num <= 1) {
        return false
    }
    Math.sqrt(num); //1.
    //2
    for (var i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false; }}return true;
}

// The method to get prime numbers
HashTable.prototype.getPrime = function(num) {
    / / * 2 = 7, 14 + 1 = 15, 16, + 1 = + 1 = 17 (prime)
    while (!this.isPrime(num)) {
        num++
    }
    return num
}
Copy the code

• Step 2: Modify the operations related to array expansion in the PUT method of adding elements and remove method of removing elements:

Add the following code to the PUT method:

// Determine whether an expansion operation is required
if (this.count > this.limit * 0.75) {
    let newSize = this.limit * 2
    let newPrime = this.getPrime(newSize)
    this.resize(newPrime)
}
Copy the code

Add the following code to the remove method:

// Shrink the capacity
if (this.limit > 7 && this.count < this.limit * 0.25) {
    let newSize = Math.floor(this.limit / 2)
    let newPrime = this.getPrime(newSize)
    this.resize(newPrime)
}
Copy the code

Test code:

let ht = new HashTable()

ht.put('class1'.'Tom')
ht.put('class2'.'Mary')
ht.put('class3'.'Gogo')
ht.put('class4'.'Tony')
ht.put('class5'.'5')
ht.put('class6'.'6')
ht.put('class7'.'7')
ht.put('class8'.'8')
ht.put('class9'.'9')
ht.put('class10'.'10')
console.log(ht.size()); / / 10
console.log(ht.limit); / / 17
Copy the code

Test results:

Four, hash table complete implementation

// Encapsulate the hash table class
function HashTable() {
    / / property
    this.storage = []
    this.count = 0 // Count the number of stored elements
        // loadFactor: loadFactor > 0.75 requires expansion; When loadFactor < 0.25, the capacity needs to be reduced
    this.limit = 7 // Initial length

    / / method
    // hash function
    HashTable.prototype.hashFunc = function(str, size) {
        //1. Define the hashCode variable
        let hashCode = 0

        //2. Horner's rule, calculate the value of hashCode
        //cats -> Unicode encoding
        for (let i = 0; i < str.length; i++) {
            // str.charcodeat (I)// Get the Unicode encoding for a character
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }

        //3. Mod operation
        let index = hashCode % size
        return index
    }

    // Insert & modify operations
    HashTable.prototype.put = function(key, value) {
        //1. Obtain the corresponding index based on the key
        let index = this.hashFunc(key, this.limit)

        //2. Retrieve the corresponding bucket according to index
        let bucket = this.storage[index]

        //3. Check whether the bucket is null
        if (bucket == null) {
            bucket = []
            this.storage[index] = bucket
        }

        //4. Check whether the data is modified
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] == key) {
                tuple[1] = value
                return // Do not return a value}}//5. Perform the add operation
        bucket.push([key, value])
        this.count += 1

        //6. Determine whether capacity expansion is required
        if (this.count > this.limit * 0.75) {
            let newSize = this.limit * 2
            let newPrime = this.getPrime(newSize)
            this.resize(newPrime)
        }
    }

    // Get
    HashTable.prototype.get = function(key) {
        //1. Obtain the corresponding index based on the key
        let index = this.hashFunc(key, this.limit)

        //2. Obtain the corresponding bucket according to index
        let bucket = this.storage[index]

        //3. Check whether the bucket is null
        if (bucket == null) {
            return null
        }

        //4. If there is a bucket, then do a linear search
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] == key) { //tuple[0] stores keys, and tuple[1] stores values
                return tuple[1]}}//5. If no one is found, return null
        return null
    }

    // Delete
    HashTable.prototype.remove = function(key) {
        //1. Obtain the corresponding index based on the key
        let index = this.hashFunc(key, this.limit)

        //2. Obtain the corresponding bucket according to index
        let bucket = this.storage[index]

        //3. Check whether the bucket is null
        if (bucket == null) {
            return null
        }

        //4. If there is a bucket, do a linear search and delete it
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                bucket.splice(i, 1)
                this.count -= 1
                return tuple[1]

                //6. Reduce the capacity
                if (this.limit > 7 && this.count < this.limit * 0.25) {
                    let newSize = Math.floor(this.limit / 2)
                    let newPrime = this.getPrime(newSize)
                    this.resize(newPrime)
                }
            }
        }

        //5. If no, return null
        return null
    }

    /*------------------ Other methods --------------------*/
    // Check whether the hash table is null
    HashTable.prototype.isEmpty = function() {
        return this.count == 0
    }

    // Get the number of elements in the hash table
    HashTable.prototype.size = function() {
        return this.count
    }


    // Hash table expansion
    HashTable.prototype.resize = function(newLimit) {
        //1. Save the old storage array contents
        let oldStorage = this.storage

        //2. Reset all attributes
        this.storage = []
        this.count = 0
        this.limit = newLimit

        //3. Iterate over all buckets in oldStorage
        for (let i = 0; i < oldStorage.length; i++) {
            //3.1. Fetch the corresponding bucket
            const bucket = oldStorage[i];

            Check whether the bucket is null
            if (bucket == null) {
                continue
            }

            //3.3. If the bucket contains data, insert it again
            for (let j = 0; j < bucket.length; j++) {
                const tuple = bucket[j];
                this.put(tuple[0], tuple[1]) // Insert key and value of data}}}// Check whether num is prime
    HashTable.prototype.isPrime = function(num) {
        if (num <= 1) {
            return false
        }
        Math.sqrt(num); //1.
        //2
        for (var i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; }}return true;
    }

    // The method to get prime numbers
    HashTable.prototype.getPrime = function(num) {
        / / * 2 = 7, 14 + 1 = 15, 16, + 1 = + 1 = 17 (prime)
        while (!this.isPrime(num)) {
            num++
        }
        return num
    }
}
Copy the code