preface

Recently, I was researching algorithms, and I happened to see the Hash table of algorithms, which is really an interesting thing.

Hash tables are used to quickly determine whether an element is in a set, but when we want to use hash to solve the problem, we usually choose one of three data structures:

• An array of
• Set
• Map (map)

Seeing how both maps and sets are related to hash tables, I found that although these ES6 syntaxes have been used many times before, I haven’t taken the time to dig into them. Now that you’ve learned about hash tables, take a look at their underlying principles and try writing a simple Map that implements all its methods. Go!

Hash table

First, let’s talk about hash tables in algorithms. The purpose of the hash algorithm is to find a value in the data structure as quickly as possible. If you want to query a data through enumeration, the time complexity is O(n), and the hash function can be used to quickly retrieve the value directly through the index, with only O(1).

The hash function can obtain the position of the key argument through the hashCode method. That is, the key of different data formats can be converted into different values through a specific encoding method, and then the corresponding values can be obtained based on the values. However, if hashCode results in a value larger than the hash table size, a modulo operation can be performed on that value to avoid the risk that the operands exceed the maximum representation range of the value variable.

Conflict resolution

However, sometimes some keys will have the same hash value, which will inevitably lead to conflicts. Generally, there are two main methods to solve conflicts, zipper method and linear exploration.

1. The zipper method: The easiest way to resolve conflicts is to create a linked list for each position in the hash table and store the elements in it, in the so-called array + linked list form. This way, you don’t waste a lot of memory because the array is empty, and you don’t waste too much time looking up the list because it is too long.
2. Linear probing: Is another effective method for resolving conflicts, so called because it handles conflicts by storing elements directly in a table, rather than in a separate data structure. When you want to add a new element, if the corresponding position is occupied, you iterate through the hash table until a free position is found. One thing to be aware of when using linear probes is that the array may run out of available places, so you may need to create a larger array and copy the elements into the new array.

A good hash function is made up of several things: the time it takes to insert and retrieve elements, and a low probability of collisions.

Map

The Map is introduced

The three most common hash structures are array, set and map. Let’s take a look at map.

The Map object holds key-value pairs and can remember the original insertion order of the keys. Any value (object or raw value) can be a key or a value.

The traditional JavaScript Object Object uses a string as a key, which limits its use.

To address this problem, ES6 provides a new Map data structure. Unlike Object, which can only use a value, string, or symbol as a key, Map can use any JS data type as a key, meaning that the range of “keys” is not limited to strings. Values of all types (including objects) can be used as keys. Internally, Map uses the SameValueZero comparison operation, which is basically equivalent to using strict object equality criteria to check key matches.

Like Object, there is no limit to the value of a Map, but a Map is a more complete implementation of a Hash structure than Object. If you need key-value data structures, Map is better than Object.

Using the Map method

Map attributes and operation methods

An instance of a Map structure has the following properties and operations.

Map traversal method

Write a Map by hand

Then write a simplified version of the map by hand, following its properties and methods.

Initialize the

First define a MyMap and then initialize it by creating an init method on its prototype chain. You can also use class to create a MyMap.

function MyMap() {
  this.init()
}

MyMap.prototype.init = function () {
  // Hash length
  this.size = 0;
  
  // Bucket is a hash structure: array + list, initialized with next pointing to the header pointer for each list
  this.bucket = new Array(8).fill(0).map(() = > {
    return {
      next: null}}); };Copy the code

const map = new MyMap();

console.log(map);
Copy the code

Defining hash methods

Create a hash method on the MyMap prototype chain to classify the new data and store them in the specified linked list for quick lookup, as well as for subsequent get, set, delete and other methods.

MyMap.prototype.hash = function (key) {
  let index = 0;

  // Classify data according to the type of key, return the specified index, or use other methods
  if (typeof key == "object") {
    index = 0;
  } else if (typeof key === "undefined") {
    index = 1;
  } else if (typeof key === "null") {
    index = 2;
  } else if (typeof key === "boolean") {
    index = 3;
  } else if (typeof key === "number") {
    // perform the mod operation on the number
    index = key % this.bucket.length;
  } else if (typeof key == "string") {
    for (let i = 0; i < key.length; i++) {
      // Find the sum of the Unicode encoding for each character of the string
      index += key.charCodeAt(i);
    }
    
    // Perform the modulo operation on the string index
    index = index % this.bucket.length;
  }

  return index;
}
Copy the code

Create a set method

MyMap.prototype.set = function (key, value) {
  // Obtain the corresponding index of the linked list according to the key value
  const i = this.hash(key);
  let listNode = this.bucket[i];
  
  // Iterate over the list, append data to the end of the list
  while (listNode.next) {
    // If there is a key, perform the update operation and return its own object
    if (listNode.key === key) {
      listNode.value = value;
      
      return this;
    }
    
    // Do not find the list moving down
    listNode = listNode.next;
  }

  // If no one is found, perform the new operation
  listNode.next = {
    key,
    value,
    next: null
  };

  this.size++;
  return this;
};
Copy the code

const map = new MyMap();

map.set('0'.'foo');
map.set(1.'bar');
map.set({}, "baz");

console.log(map);
Copy the code

Create a get method

MyMap.prototype.get = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  // Iterate through the list to find the specified key and return value, undefined if not found
  while (listNode.next) {
    if (listNode.next.key === key) {
      return listNode.next.value;
    }

    // Do not find the list moving down
    listNode = listNode.next;
  }

  return undefined;
};
Copy the code

const map = new MyMap();

map.set('0'.'foo');
map.set(1.'bar');
map.set({}, "baz");

console.log('get 0', map.get(0));  // get 0 undefined
console.log('get 1', map.get(1));  // get 1 bar
Copy the code

Create the HAS method

MyMap.prototype.has = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  // Iterate through the list to find the specified key, returning true if there is one, false otherwise
  while (listNode.next) {
    if (listNode.next.key === key) {
      return true;
    }

    // Do not find the list moving down
    listNode = listNode.next;
  }

  return false;
};
Copy the code

const map = new MyMap();

map.set('0'.'foo');
map.set(1.'bar');
map.set({}, "baz");

console.log('has 0', map.get(0));  // has 0 false
console.log('has 1', map.get(1));  // has 1 true
Copy the code

Create delete method

MyMap.prototype.delete = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  // Iterate through the list to find the specified key, and return true if there is any change to the next pointer, false otherwise
  while (listNode.next) {
    if (listNode.next.key === key) {
      listNode.next = listNode.next.next;
      this.size--;
      
      return true;
    }

    // Do not find the list moving down
    listNode = listNode.next;
  }

  return false;
};
Copy the code

const map = new MyMap();

map.set('0'.'foo');
map.set(1.'bar');
map.set({}, "baz");

console.log('delete "0"', map.delete('0'));  // delete "0" true
console.log(map);
Copy the code

Create the clear method

Perform the initialization operation.

MyMap.prototype.clear = function () {
  this.init();
};
Copy the code

Create entries method

You can iterate through each list of an array and return a new Iterator containing [key, value] pairs.

MyMap.prototype.entries = function* () {
  for (let i = 0; i < this.bucket.length; i++) {
    let listNode = this.bucket[i];
    
    while (listNode.next) {
      if (listNode.next.key) {
        yield[listNode.next.key, listNode.next.value]; } listNode = listNode.next; }}};Copy the code

But while this allows for the simple entry method, it does not record the original insertion order of the map, so you can add a header and tail node to record the order.

1. Modify the init method and move the top and bottom nodes in the set and delete methods

   MyMap.prototype.init = function () {
     // Hash length
     this.size = 0;
   
     // Bucket is a hash structure: array + list, initialized with next pointing to the header pointer for each list
     this.bucket = new Array(8).fill(0).map(() = > {
       return {
         next: null}});// Record the head and tail nodes
     this.head = {
       next: null
     };
     this.tail = null;
   };
   
   MyMap.prototype.set = function (key, value) {
     // Obtain the corresponding index of the linked list according to the key value
     const i = this.hash(key);
     let listNode = this.bucket[i];
   
     let flag = false;
     // Iterate over the list, append data to the end of the list
     while (listNode.next) {
       // If there is a key, perform the update operation and return its own object
       if (listNode.next.key === key) {
         listNode.next.value = value;
   
         // return this;
         flag = true;
         break;
       }
   
       // Do not find the list moving down
       listNode = listNode.next;
     }
   
     // If so, update the value in the head node
     if (flag) {
       listNode = this.head;
       while (listNode.next) {
         if (listNode.next.key === key) {
           listNode.next.value = value;
           return this; } listNode = listNode.next; }}const node = {
       key,
       value,
       next: null
     };
     // If no one is found, perform the new operation
     listNode.next = node;
   
     // Assign values to the first and last nodes to record the hash order
     if (this.size === 0) {
       this.head.next = node
       this.tail = this.head.next;
     } else {
       this.tail.next = node
       this.tail = this.tail.next;
     }
   
     this.size++;
     return this;
   };
   
   MyMap.prototype.delete = function (key) {
     const i = this.hash(key);
     let listNode = this.bucket[i];
   
     let flag = false;
     // Iterate through the list to find the specified key, and return true if next is changed and next in head is changed, false otherwise
     while (listNode.next) {
       if (listNode.next.key === key) {
         listNode.next = listNode.next.next;
         this.size--;
   
         flag = true;
         break
       }
   
       // Do not find the list moving down
       listNode = listNode.next;
     }
   
     if (flag) {
       listNode = this.head;
       while (listNode.next) {
         if (listNode.next.key === key) {
           listNode.next = listNode.next.next;
           break; } listNode = listNode.next; }}return flag;
   };
   Copy the code

2. Iterate over the head node, returning a new Iterator containing the [key, value] pair.

   MyMap.prototype.entries = function* () {
     let listNode = this.head.next;
   
     // Iterate sequentially from the beginning node
     while (listNode) {
       if (listNode.key) {
         yield[listNode.key, listNode.value]; } listNode = listNode.next; }};Copy the code

   const map = new MyMap();
   
   map.set('0'.'foo');
   map.set(1.'bar');
   map.set({}, "baz");
   
   const iterator = map.entries();
   console.log(iterator.next().value);  // ['0', 'foo']
   console.log(iterator.next().value);  // [1, 'bar']
   console.log(iterator.next().value);  // [{}, 'baz']
   
   console.log(map);
   Copy the code

   

Create values method

The values method is similar to the entries method.

MyMap.prototype.values = function* () {
  let listNode = this.head.next;

  // Iterate sequentially from the beginning node
  while (listNode) {
    if (listNode.value) {
      yieldlistNode.value; } listNode = listNode.next; }};Copy the code

Create keys method

The keys method is also similar to the entries method.

MyMap.prototype.keys = function* () {
  let listNode = this.head.next;

  // Iterate sequentially from the beginning node
  while (listNode) {
    if (listNode.key) {
      yieldlistNode.key; } listNode = listNode.next; }};Copy the code

Create the @@iterator method

The initial value of the @@iterator property is the same function object as the initial value of the entries property.

MyMap.prototype[Symbol.iterator] = MyMap.prototype.entries; 
Copy the code

Create the forEach method

ForEach (fn, context)
MyMap.prototype.forEach = function (fn, context = this) {
 let listNode = this.head.next;

  // Iterate sequentially from the beginning node
  while (listNode) {
    if(listNode.key) { fn.call(context, listNode.value, listNode.key); } listNode = listNode.next; }};Copy the code

const map = new MyMap();

map.set('0'.'foo');
map.set(1.'bar');
map.set({}, "baz");

function logMapElements(value, key, map) {
  console.log(`m[${key}] = ${value}`);
}
map.forEach(logMapElements);

console.log(map);
Copy the code

The complete code

The code is longer. If you are interested, you can check out gitee.com/sosir/handw…

conclusion

Most of the features of a map can be implemented with the Object type, but the performance of a map is much better if the code is designed to do a lot of querying, inserting, and deleting. In other words, when we need to quickly determine whether an element exists or requires a large number of additions and deletions, we need to consider the hash table structure map.

However, the hash table also sacrifices space for time. We still need to use additional arrays, sets and maps to store data in order to achieve fast search and maximize the efficiency of reading. Moreover, the search efficiency of the hash table mainly depends on the hash function selected when constructing the hash table and the method to deal with conflicts.

Hash tables are not a panacea, but they should be the first thing you want to do when you need to quickly determine whether an element exists or not.