JS implement hash table principle

Hash table principle

  • A Hash table (also called a Hash table) is a data structure that is directly accessed based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array of records is called a hash table.

  • Hash table can store various types of data, from the hash table when we find the needed data, ideally without any comparison, an access would get the check record, it must be in the record store location and its key to establish a certain corresponding relationship between f, make each keyword and the structure of a unique location. (The keyword is the data to be stored in a location equivalent to the index of the array.)

Hash table implementation

1. The chain address method is adopted here

​

  • Basic data form

    [[['key1'.'value1'],
        ['key2'.'value2']], [['key3'.'value3']]]Copy the code

  • Basic attributes

    Size: limits the length of the array

    Count: total number of data

    An array of stroge:

  • Basic method

    Put: Adds or modifies data

    Get: Obtains data

    Remove: deletes data

    IsEmpty: indicates whether the value isEmpty

    Length: indicates the data length

    Resize: Expand the array

2 Implementation Process

1 Preparing code

const HashTable = function(size=7) {
  this.stroge = []; [[key,value]]] [key,value]] [key,value]] [key,value]
  this.size = size; // Initialize the array length. If the capacity is insufficient, expand the array
  this.count = 0; // loadFactor = this.count/this.size If the value exceeds 0.75, the capacity needs to be expanded
}
Copy the code

2 Create a hash function

  • In this case, horner algorithm is used for modular operation,charCodeAtTo obtainUnicodecoding
  • After modulo, get the index value.
// Create a hash function based on horner's algorithm (you can also use JAVA median to hash binary & Length-1)
  HashTable.prototype.hashFunc = function(key) {
    const H = 37; / / prime Numbers
    let hashCode = 0
    // Use horner algorithm to find index
    for(let i = 0; i < key.length; i++) {
      hashCode = H * hashCode + key.charCodeAt(i)
    }
    return hashCode % this.size
  }
Copy the code

3 addputmethods

  1. ifthis.stroge[index] === undefined, you need to create onethis.stroge[index] = [[]]
  2. this.stroge[index] = [[key, value]]Traversal, yeskeyThen, the value is updatedkeythepushadd
// put Add and modify are the same
  If this. Stroge [index] === undefined, this. Stroge [index] = [[]]
  // 2. this.stroge[index] = [[key, value]]
  HashTable.prototype.put = function(key, value) {
    const index = this.hashFunc(key);
    Stroge [index] = [[]]; // 1 Check whether this. Stroge [index] = [[]]
    if(this.stroge[index] === undefined) {
      this.stroge[index] = []
    }
    // Go through the array data inside basket
    const basket = this.stroge[index]
    if(basket.length) {
      for(let i = 0; i < basket.length; i++) {
        const tuple =  basket[i]
        // If the key corresponds, modify the data directly and jump out
        if(tuple[0] === key) {
          tuple[1] = value;
          return}}}// If the key is not found, add it directly to the end of the array
    basket.push([key, value])
    this.count++;
  }
Copy the code

4 to addgetAccess method

  1. Get the index of the key based on hashFunc

  2. If stroge[index] is undefined, null is returned; otherwise, the corresponding backet is obtained

  3. Iterating through the corresponding backet, retrieving value, otherwise returning NULL

// get Gets the corresponding value
  Stroge [index] = stroge[index] = stroge[index] = stroge[index] Otherwise null */ is returned
  HashTable.prototype.get = (key) = > {
    const index = this.hashFunc(key);
    const backets = this.stroge[index]
    if(backets === undefined) {
      return null
    }
    let res = null;
    for(let i = 0; i < backets.length; i++) {
      if(backets[i][0] === key) {
        res = backets[i][1]
        break; }}return res;
  }
Copy the code

5 addremoveDelete methods

  1. Get the index of the key based on hashFunc

  2. If stroge[index] is undefined, null is returned; otherwise, the corresponding backet is obtained

  3. If backet[I][0] === key, splice,this.count– is called, otherwise null is returned

Stroge [index] = stroge[index] = stroge[index] = stroge[index]; Splice is called if backet[I][0] === key, otherwise null */ is returned
  HashTable.prototype.remove = (key) = > {
    const index = this.hashFunc(key);
    const backet = this.stroge[index];
    let res = null
    if(backet === undefined) {
      return null
    }
    for(let i = 0; i < backet.length; i++) {
      const tuple = backet[i];
      if(tuple[0] === key) {
        backet.splice(i, 1)
        this.count--;
        res = tuple[1]}}return res
  }
Copy the code

6 Add other methods

isEmpty, length

/** * isEmpty isEmpty */
  HashTable.prototype.isEmpty = () = > {
    return this.count === 0
  }

  /** * size Length */
  HashTable.prototype.length = () = > {
    return this.count
  }
Copy the code

7 Test Data

const hashTable = new HashTable()
hashTable.put('abc'.'123')
hashTable.put('abc'.'234')
hashTable.put('abcd'.'123')
hashTable.put('ab'.'123')
console.log(hashTable.get('abc'))

hashTable.remove('ab')

console.log(hashTable.stroge)

console.log(hashTable.isEmpty())
console.log(hashTable.length())
Copy the code

3 Expand the hash table capacity

When a hash table has a loadFactor, the loadFactor is the extent to which elements in the Hsah table are filled. The larger the loading factor is, the more elements are filled, and the advantage is that the space utilization rate is high, but the chance of conflicts is increased; on the contrary, the smaller the loading factor is, the fewer filled elements are. The advantage is that the chance of conflicts is reduced, but the space waste is more. The greater the chance of conflict, the higher the cost of lookup. Conversely, the lower the cost of lookup. Therefore, the smaller the search time.

After adding put, the loadFactor needs to be expanded when the loadFactor exceeds 0.75

Add 1resizemethods

When expansion is required, the elements in stroge array in the hash table need to be stored again. Because the size is different at this time, the index after modulo is different, and the old array needs to be replaced in the new array.

  /** * Capacity expansion: When adding elements, loadFactor > 0.75 requires capacity expansion */; when deleting elements, loadFactor < 0.25 && size >= 7 requires capacity reduction */
  HashTable.prototype.resize = (limit) = > {
    const oldStore = this.stroge;
    // reset stroge, count, size
    this.stroge = [];
    this.count = 0;
    this.size = limit;
    // Add the original data back to the store
    for(let i = 0; i < oldStore.length; i++) {
      const basket = oldStore[i]
      if(basket === undefined) {
        continue
      }
      for(let i = 0; i < basket.length; i++) {
        const tuple = basket[i]
        this.put(tuple[0], tuple[1])}}}Copy the code

2 addsmallerPrimemethods

Find the nearest prime number after doubling, and ensure that the prime number is to avoid common factors between numbers with the same modulus

  /** * is a prime number */
  function isPrime(num) {
    / / square root
    const sqr = parseInt(Math.sqrt(num))

    for(let i = 2; i <= sqr; i++) {
      if(num % i === 0) {
        return false}}return true
  }
  /** * find the smallest contiguous prime */
  function smallerPrime(num) {
    while(! isPrime(num)) { num++ }return num;
  }
Copy the code

3 Modifying and Addingputmethods

Capacity expansion: when adding elements, the loadFactor is greater than 0.75

HashTable.prototype.put = function(key, value) {
    const index = this.hashFunc(key);
    Stroge [index] = [[]]; // 1 Check whether this. Stroge [index] = [[]]
    if(this.stroge[index] === undefined) {
      this.stroge[index] = []
    }
    // Go through the array data inside basket
    const basket = this.stroge[index]
    if(basket.length) {
      for(let i = 0; i < basket.length; i++) {
        const tuple =  basket[i]
        // If the key corresponds, modify the data directly and jump out
        if(tuple[0] === key) {
          tuple[1] = value;
          return}}}// If the key is not found, add it directly to the end of the array
    basket.push([key, value])
    this.count++;

    // If this.count/this.size >= 0.75, the system needs to expand
    if(this.count >= this.size * 0.75) {
      // Find the smallest prime number
      const newSize = smallerPrime(this.size * 2)
      this.resize(newSize)
    }
  }
Copy the code

4 to modifyremovemethods

Scaling down, loadFactor < 0.25 && size >= 7 when deleting elements, scaling down is required

HashTable.prototype.remove = (key) = > {
    const index = this.hashFunc(key);
    const backet = this.stroge[index];
    let res = null
    if(backet === undefined) {
      return null
    }
    for(let i = 0; i < backet.length; i++) {
      const tuple = backet[i];
      if(tuple[0] === key) {
        backet.splice(i, 1)
        this.count--;
        res = tuple[1]
        if(this.size > 7 && this.count < this.size * 0.25) {
          const num = smallerPrime(Math.floor(this.size / 2));
          this.resize(num)
        }
      }
    }
    return res
  }
Copy the code

4 summarizes

JS implementation of single linked lists