Js implementation encapsulates hash tables

1. The principle of hash tables

** 1. Hash tables need arrays to store data *

** 2. The following table for each array is generated by the hash function *

** 3. The hash table must have more space than the content elements to hold *

** 4. The chain address method is generally used to solve conflicts *

2. Precautions

2.1 Implement efficient hash functions

The hash function is the soul of the entire hash table, and through the hash function, you can convert the field into hascode as an array subscript, and implement the hash function, and you can use Horner’s rule to simplify the number of times you multiply polynomials.

** Why use Horner’s rule? *

** When converting a word to a number, in order to ensure the uniqueness of the word, each word cannot be added after converting to a number using Unicode, *

** Therefore requires some conversion of the words in each position *

** For example, the unicode for each letter of cast is 99, 97, 115, 116; If the sum is simply added, the converted numbers will be repeated *

** So the cast can be 99*37^3 + 97*37^2 + 115*37^1 + 116*37^0; *

** again, why use Horner’s rule? *

** Horner’s law can simplify polynomial addition to improve the speed of converting characters into numbers. *

** 1. If polynomial transformation is directly used, it will lead to a very large amount of calculation. It’s going to be order 2 to the N star

** 2. Simplification of Horner’s rule requires time complexity O(N);

** Why hascode initializes 0? *

** According to Horner’s rule, starting with the highest degree term, ensure that the first term coefficients are involved *

3. Complete code implementation

/* Hash table */
class HasMap {
  constructor() {
    // Required attributes
    //1. Need a container to store the contents of the hash table.
    this.storage = [];
    //2. Require a representation of the amount of data currently stored
    this.count = 0;
    //3. The number of elements that can be stored in an array is used to limit the size of the array. In the hash function to reduce the hash number, to ensure that the hash number can be compressed to a reasonable range of storage.
    this.limit = 7;
  }
  // A hash function is required to hash the input data and compress it into an array
  hasFunc(str) {
    //1. Convert the string to a larger number hascode
    / / attention! So hascode can be any value, and the reason why it's 0 is because it's a smaller number, it's faster. In Horner's algorithm, the first calculation starts with the highest degree term. So the first number can reduce the size of the next number to some extent.
    
    let hascode = 0;
    // The horner algorithm hashes
    for (let i = 0; i < str.length; i++) {
      hascode = hascode * 37 + str.charCodeAt(i);
    }
    //2. Compress the large number hascode into the array range.
    hascode = hascode % this.limit;
    return hascode;
  }
  isEmpty() {
    return !this.count;
  }
  // Insert data or modify
  put(key, val) {
    1. Obtain the hascode subscript
    let hascode = this.hasFunc(key);
    //2. Check whether the hascode subscript has a value in the container

    If there is no value, create an array to store the first value and return true
    if (this.storage[hascode] == null) {
      this.storage[hascode] = [{ key, val }];
      this.count++;
      this.resize();
      return;
    }
    //2.2 If there is a value, proceed to the next step
    //3 Run through the hascode array to find each object in the array to see if there is already a key;
    let index = 0,
      chain = this.storage[hascode];
    // console.log(chain);
    while (index < chain.length) {
      //3.1 Replace the object corresponding to the key if there is a key.
      if (chain[index].key == key) {
        chain[index].val = val;
        return;
      }
      index++;
    }
    Insert an object at the end of the array if there is no key.
    chain.push({ key, val });
    this.count++;
    this.resize();
  }
  // Get data
  get(key) {
    //1. Check whether the hash table is empty
    //1.1 Returns -1 if it is empty
    if (this.isEmpty()) return -1;
    //1.2 goes to the next step without null
    / / 2. Obtain hascode
    let hascode = this.hasFunc(key);
    //3. Run hascode to check whether the location is empty
    //3.1 Returns -1 if empty
    if (!this.storage[hascode]) return -1;
    If not empty, go to the next step
    //4. Loop through the hascode array to check whether the key exists
    let index = 0,
      chain = this.storage[hascode];

    while (index < chain.length) {
      //4.1 Returns the corresponding val if it exists
      if (chain[index].key === key) {
        return chain[index].val;
      }
      index++;
    }
    //4.2 If it does not exist, return -1
    return -1;
  }
  // Delete method
  remove(key) {
    if (this.isEmpty()) return -1;
    let hascode = this.hasFunc(key);
    if (this.storage[hascode] == null) return -1;
    let index = 0;
    while (index < this.storage[hascode].length) {
      if (this.storage[hascode][index].key == key) {
        return this.storage[hascode].splice(index, 1);
      }
      index++;
    }
    return -1;
  }
  // Hash table expansion
  resize() {
    //1. If the current loadFactor exceeds 0.75, the array is expanded. LoadFactor is the ratio of count to the limit length of the array. The count/limit > 0.75
    // if loadFactor is less than 0.75, return;
    if (this.count / this.limit < 0.75) return;
    //1.2 If greater than 0.75 next step
    //2. The capacity of the array is approximately equal to 2 times, but it must be a prime multiple
    this.limit = this.limit * 2 + 1;
    while (!this.isPrime(this.limit)) {
      this.limit++;
    }
    // We need to reinitialize the storage and insert all the data again, because the limit length of the array (limit length) is changed, hascode obtained by the original hash function is no longer corresponding to the new array. So recreate and insert;
    let oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    //4. Iterate over the old storage and insert into the new storgae.
    let index = 0;
    while (index < oldStorage.length) {
      if (oldStorage[index]) {
        let chainIndex = 0;
        while (chainIndex < oldStorage[index].length) {
          let obj = oldStorage[index][chainIndex];
          this.put(obj.key, obj.val);
          chainIndex++;
        }
      }
      index++;
    }
    console.log('Re-inserted successfully, current limit is: %d'.this.limit);
  }
  // Check whether a number is prime
  isPrime(num) {
    //1. Divide this number to get a smaller number.
    let newNum = parseInt( Math.sqrt(num) );
    //2. Loop over the number, judging each number iterated with the input number %
    for (let i = 2; i <= newNum; i++) {
      //2.1 If the modulo is 0, it is not prime
      if (num % i == 0) {
        return false; }}If 0 is not found, return true;
    return true; }}let hastable = new HasMap();
hastable.put("lipeng11", { age: "18".sex: "Male" });
hastable.put("chen", { age: "3".sex: "Female" });
console.log(hastable.remove("lipeng11"));
console.log(hastable.get("lipeng11"));

Copy the code

Personal Blog Address: Click to enter my personal blog