This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

In the previous chapter, we briefly introduced the definition of hash table, and began to encapsulate their own implementation of a hash table structure class, complete the definition of attributes and hash function, this article continues to implement the custom hash table structure class add, delete, change, check and capacity expansion method.

Increase and change the update ()

The update method takes two parameters, key and value. Key Is used to determine the location of the data stored in a storage, that is, the subscript value. Value is the data to store. Before we get down to the actual code, let’s resolve the possible conflicts — what if different keys passed in get the same value through hashFn processing? I use the chain address method to solve the conflict.

Conflict resolution – chain address method

Since it is possible to store multiple values for the same subscript, each location of the storage array should not store a single data, but a second array (or linked list). Data according to the key to find a storage item, and then with the item stored in the array of each element is compared, if the original already exists, change the data; If there is no data, add data. Data is stored as a fixed two-length array (or more like a typescript tuple) with the 0th item being key and the first item being value. A simple hash table is drawn as follows:

The code implementation is as follows:

/ / add & change
update(key, value) {
  // 1. Get the subscript
  const index = this.hashFn(key, this.size)
  // 2. Check whether there is an array at this location
  let bucket = this.storage[index]
  // Add an empty array if there is no array
  if(! bucket) {this.storage[index] = bucket = []
  }
  // If there is an array, loop over
  for (let i = 0; i < bucket.length; i++) {
    // Whether an element with the same key is stored
    if (key === bucket[i][0]) {
      // There are some modifications
      bucket[i][1] = value
      return}}// If no, add
  bucket.push([key, value])
  this.count++
  // Check whether the capacity needs to be expanded (described later)
  if (this.count > this.size * 0.75) this.resize(this.getPrime(this.size * 2))}Copy the code

You can do a test, define a hash table, store some data, the first three are new, the last is changed, and print the hash table instance object:

/ / test
const hashTable = new HashTable()
hashTable.update('Jay', { name: 'Jay'.age: 22 }) / / new
hashTable.update('Zhou', { name: 'Zhou'.age: 23 }) / / new
hashTable.update('Chaim', { name: 'Chaim'.age: 28 }) / / new
hashTable.update('Chaim', { name: 'ChaimHL'.age: 28 }) / / modify
console.log(hashTable)
Copy the code

The results are shown below:

Check the find ()

Once the increment operation is done, the implementation of the query operation is relatively simple, because the principle is the same. Put the code directly:

/ / check
find(key) {
  // 1. Get the subscript
  const index = this.hashFn(key, this.size)
  // 2. Check whether there is an array at this location
  let bucket = this.storage[index]
  if (bucket) {
    // There is an array
    const found = bucket.find((item) = > item[0] === key)
    return found ? found[1] : undefined
  } else {
    // There is no array
    return undefined}}Copy the code

The query operation is to obtain the corresponding subscript value by passing in the key value, and then check whether there is an array (bucket) at the subscript value, if not, return undefined. If there is an array, the array is iterated to see if there is an element whose 0th value is equal to key. If there is an element whose 0th value is equal to key, the first value of the element is returned.

Delete the remove ()

In fact, add, delete, change and check are check, the front of the meeting, delete the operation of the code is also natural. You just try to find the element, delete it and return it if you find it; Returns an empty array if none is found.

/ / delete
remove(key) {
  const index = this.hashFn(key, this.size)
  let bucket = this.storage[index]
  if (bucket) {
    const index = bucket.findIndex((item) = > item[0] === key)
    if(index ! = = -1) {
      // There is an array in which the 0th element is equal to key
      this.count--
      // Check whether the capacity needs to be reduced (described below)
      if (this.size > 11 && this.count < this.size * 0.25) {
        this.resize(this.getPrime(Math.floor(this.size / 2)))}return bucket.splice(index, 1) [0]}}// Return an empty array if no element is removed
  return[]}Copy the code

Splice (index, 1)[0] return bucket.splice(index, 1)[0] return bucket.splice(index, 1)[0]

Resize ()

When defining the hash table class, we set this.size = 11, which means that each instance of the hash table starts with a size of 11. If we want to store a large amount of data, we must have a long bucket at each location of the hash table, which becomes inefficient. So we need to have a mechanism to change the size of the hash table in time, and the implementation of this mechanism depends on the size of the loading factor.

Load Factor

The value of the loading factor is the ratio of the number of data stored in the hash table (count) to the size of the hash table itself (size), i.e., loadFactor = count/size. Generally, the hash table that uses the chained address method to resolve conflicts needs to be expanded when the loading factor is greater than 0.75; when the loading factor is smaller than 0.25, the capacity needs to be reduced.

Implementation approach

  1. Create a new variableoldStoragePoint to the original store one by onebucket 的 storageThe array;
  2. willthis.storageReassign to an empty array,countReassign it to 0, and then letsizeBecome incomingnewSize, its value is about twice (capacity expansion) or half (capacity reduction);
  3. Will be stored in theoldStorageReload all data in thestorage.

The code is as follows:

// Expand & shrink
resize(newSize) {
  // 1. Save the value of the original storage
  const oldStorage = this.storage
  // 2. Change the capacity
  this.storage = []
  this.size = newSize
  this.count = 0
  // 3. Put all stored data into a new storage
  oldStorage.forEach((bucket) = > {
    if (bucket) bucket.forEach((item) = > this.update(item[0], item[1]))})}Copy the code

Get prime Numbers

In step 2, the newSize passed in had better be prime, which helps to distribute the data stored in the hash table more evenly. So how do I make newSize prime? We can define a new getPrime() method that takes the number num as an argument. If num is a prime number, return num. If num is not a prime number, return 1.

// Get a prime number
getPrime(num) {
  while (!this.isPrime(num)) {
    num++
  }
  return num
}
Copy the code

The isPrime() method is implemented to determine whether it isPrime:

Determine the prime number isPrime()

If a number can be factorized, the resulting two numbers must be one <= the square root of the number, and the other >= the square root of the number. So we can iterate from 2 to the square root of the number as a divisor. If the result is 0, it means that the number is divisible by 1 and itself, that is, it is not prime.

// Determine the prime number
isPrime(num) {
  // Get the square root of num
  const squareRoot = Math.sqrt(num)
  for (let i = 2; i <= squareRoot; i++) {
    if (num % i === 0) {
      return false}}return true
}
Copy the code

The reason why num is not a prime number is that the for loop needs a complete traversal, and the traversal number is less, which is more efficient.

Disadvantages of hash tables

Finally, of course, hash tables have their drawbacks. Here are four common examples:

  • Space utilization is not high, and the underlying array may not be used for every cell;
  • The data is unordered and cannot be traversed in a certain order;
  • Can’t find a maximum or minimum quickly
  • When storing an object, the key value of the object cannot be repeated.