JS data structure (3)- dictionary and hash table

preface

This article mainly introduces the dictionary and hash table related content. In ES2015, the dictionary has been implemented in the Map class, so this article will not introduce Map too much. If you want to learn, you can directly see Teacher Ruan Yifeng ES6 Map

The dictionary

define

Dictionaries are also called maps, symbol tables, or associative arrays
Stored as a key, value

methods

Set (key,value) : Adds a new element to the dictionary. If the key already exists, the existing value will be overwritten by the new value
Remove (key) : Removes the data value corresponding to the key value from the dictionary by using it as an argument.
HasKey (key) : Returns true if a key exists in the dictionary, false otherwise
Get (key) : Finds a specific value by taking the key value as an argument and returns it.  clear() : Deletes all values in the dictionary
Size () : Returns the number of values the dictionary contains. Similar to the length property of an array.
IsEmpty () : Returns true if size equals zero, false otherwise.
Keys () : Returns all the key names contained in the dictionary as an array.
Values () : Returns all values contained in the dictionary as an array.
KeyValues () : returns all [key, value] pairs in the dictionary.
ForEach (callbackFn) : Iterates through all key-value pairs in the dictionary. CallbackFn takes two arguments: key and value. This method can be aborted when the callback returns false (similar to the every method in the Array class).

implementation

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    return ` [#The ${this.key}: The ${this.value}] `; }}class Dictionary {
  constructor() {
    this.table = {};
  }
  // A function that converts a key to a string
  toStrFn(item) {
    if (item === null) {
      return 'NULL';
    } else if (item === undefined) {
      return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`;
    }
    return item.toString(); / / {1}
  }

  hasKey(key) {
    return this.table[this.toStrFn(key)] ! =null;
  }

  set(key, value) {
    if(key ! =null&& value ! =null) {
      const tableKey = this.toStrFn(key); / / {1}

      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  remove(key) {
    if (this.hasKey(key)) {
      delete this.table[this.toStrFn(key)];
      return true;
    }
    return false;
  }

  get(key) {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value; / / {2}
  }
  keyValues() {
    return Object.values(this.table);
  }

  keys() {
    return this.keyValues().map(valuePair= > valuePair.key);
  }
  values() {
    return this.keyValues().map(valuePair= > valuePair.value);
  }

  forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      if (result === false) {
        break;
      }
    }
  }
  size() {
    return Object.keys(this.table).length;
  }
  clear() {
    this.table = {};
  }

  toString() {
    if (this.isEmpty()) {
      return ' ';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
      objString = `${objString}.${valuePairs[i].toString()}`;
    }
    return objString;
  }
  isEmpty() {
    return this.size() === 0; }}/ / use
const dictionary = new Dictionary();
dictionary.set('Gandalf'.'[email protected]');
dictionary.set('John'.'[email protected]');
dictionary.set('Tyrion'.'[email protected]');

console.log(dictionary.hasKey('Gandalf'));  //true
console.log(dictionary.size()); / / 3

console.log(dictionary.keys()); // ["Gandalf", "John", "Tyrion"]
console.log(dictionary.values()); //["[email protected]", "[email protected]", "[email protected]"]
console.log(dictionary.get('Gandalf')) //[email protected]
Copy the code

Hash table

define

The HashTable class, also known as the HashMap class, is a hash implementation of the Dictionary class.
The purpose of the hash algorithm is to find a value in the data structure as much as possible
The common hash function, the lose Lose hash function, simply adds the ASCII value of each letter in each key value
Non-sequential data structures

methods

Put (key,value) : Adds a new item to the hash table (can also update the hash table)
Remove (key) : Removes a value from the hash table based on the key value.
Get (key) : Returns a specific value retrieved based on the key value.

implementation

class ValuePair {
 constructor(key, value) {
   this.key = key;
   this.value = value;
 }
 toString() {
   return ` [#The ${this.key}: The ${this.value}] `; }}class HashTable {
 constructor() {
   this.table = {};
 }
 // A function that converts a key to a string
 toStrFn(item) {
   if (item === null) {
     return 'NULL';
   } else if (item === undefined) {
     return 'UNDEFINED';
   } else if (typeof item === 'string' || item instanceof String) {
     return `${item}`;
   }
   return item.toString(); / / {1}
 }
 // Sum of each ASCII character of key
 loseloseHashCode(key) {   
   if (typeof key === 'number') { 
     return key;  
   }  
   const tableKey = this.toStrFn(key); 
   let hash = 0; 
   for (let i = 0; i < tableKey.length; i++) { 
     hash += tableKey.charCodeAt(i); / / {4}
   }   
   return hash % 37; / / {5}
 } 

 hashCode(key) {  
   return this.loseloseHashCode(key); 
 }
 put(key, value) {   
   if(key ! =null&& value ! =null) {
     const position = this.hashCode(key); 
     this.table[position] = new ValuePair(key, value); 
     return true;   
   }   
   return false; 
 }

 get(key) {   
   const valuePair = this.table[this.hashCode(key)];  
   return valuePair == null ? undefined : valuePair.value; 
 } 

 remove(key) {  
   const hash = this.hashCode(key);
   const valuePair = this.table[hash]; 
   if(valuePair ! =null) {     
     delete this.table[hash]; 
     return true;  
   }   
   return false; }}const hash = new HashTable(); 
hash.put('Gandalf'.'[email protected]'); 
hash.put('John'.'[email protected]'); 
hash.put('Tyrion'.'[email protected]'); 

console.log(hash.hashCode('Gandalf') + ' - Gandalf'); //19 - Gandalf
console.log(hash.hashCode('John') + ' - John'); //29 - John
console.log(hash.hashCode('Tyrion') + ' - Tyrion') //16 - Tyrion

Copy the code

Handle conflicts in hash tables

define

Sometimes some keys have the same key value. When different values correspond to the same position in the hash table, we call it a conflict. At this point, when we get the attribute value through the same hash value, mutual coverage and data loss will occur. There are several ways to handle collisions: split chaining, linear probing, and double hashing,

The separation of link

define

The split chaining method involves creating a linked list for each position in the hash table and storing the elements in it
Additional storage is required beyond the HashTable instance

implementation


class HashTableSeparateChaining  {
  constructor() {
    this.table = {};
  }
  // A function that converts a key to a string
  toStrFn(item) {
    if (item === null) {
      return 'NULL';
    } else if (item === undefined) {
      return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`;
    }
    return item.toString(); / / {1}
  }
  // Sum of each ASCII character of key
  loseloseHashCode(key) {   
    if (typeof key === 'number') { 
      return key;  
    }  
    const tableKey = this.toStrFn(key); 
    let hash = 0; 
    for (let i = 0; i < tableKey.length; i++) { 
      hash += tableKey.charCodeAt(i); / / {4}
    }   
    return hash % 37; / / {5}
  } 

  hashCode(key) {  
    return this.loseloseHashCode(key); 
  }
  put(key, value) {   
    if(key ! =null&& value ! =null) {
      const position = this.hashCode(key);     
      if (this.table[position] == null) { //
        this.table[position] = new SinglyLinkedList(); / / for classes in the https://juejin.cn/post/6844904055311958024#heading-19 list section
      }     
      this.table[position].push(new ValuePair(key, value)); 
      return true;  
    }   
    return false; 
  }

  get(key) {  
    const position = this.hashCode(key);  
    const linkedList = this.table[position]; 
    if(linkedList ! =null && !linkedList.isEmpty()) {    
      let current = linkedList.getHead(); 
      while(current ! =null) { 
        if (current.element.key === key) {
          returncurrent.element.value; } current = current.next; }}return undefined;  
  } 

  remove(key) {   
    const position = this.hashCode(key);   
    const linkedList = this.table[position];  
    if(linkedList ! =null && !linkedList.isEmpty()) {    
      let current = linkedList.getHead();     
      while(current ! =null) {       
        if (current.element.key === key) { 
          linkedList.remove(current.element); 
          if (linkedList.isEmpty()) { 
            delete this.table[position]; 
          }         
          return true; } current = current.next; }}return false; }}Copy the code

Linear probe

define

The way to handle collisions is to store elements directly into a table, rather than in a separate data structure

When adding a new element to a table, try index+1 if the index is already occupied. If index+1 is also occupied, try index+2, and so on. Sample code is as follows

implementation

class HashTableSeparateChaining  {
  constructor() {
    this.table = {};
  }
  // A function that converts a key to a string
  toStrFn(item) {
    if (item === null) {
      return 'NULL';
    } else if (item === undefined) {
      return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`;
    }
    return item.toString(); / / {1}
  }
  // Sum of each ASCII character of key
  loseloseHashCode(key) {   
    if (typeof key === 'number') { 
      return key;  
    }  
    const tableKey = this.toStrFn(key); 
    let hash = 0; 
    for (let i = 0; i < tableKey.length; i++) { 
      hash += tableKey.charCodeAt(i); / / {4}
    }   
    return hash % 37; / / {5}
  } 

  hashCode(key) {  
    return this.loseloseHashCode(key); 
  }
  put(key, value) {   
    if(key ! =null&& value ! =null) {     
      const position = this.hashCode(key);     
      if (this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);      
      } else {       
        let index = position + 1; 
        while (this.table[index] ! =null) { 
          index++;
        }       
        this.table[index] = new ValuePair(key, value); 
      }     
      return true;  
     }   
     return false; 
  }

  get(key) {   
    const position = this.hashCode(key);   
    if (this.table[position] ! =null) {      
      if (this.table[position].key === key) {       
        return this.table[position].value;    
      }     
      let index = position + 1;   
      while (this.table[index] ! =null && this.table[index].key ! == key) {/ / {5}
        index++;     
      }     
      if (this.table[index] ! =null && this.table[index].key === key) { / / {6}
        return this.table[position].value; }}return undefined; 
  }

  remove(key) {   
    const position = this.hashCode(key);   
    if (this.table[position] ! =null) {     
      if (this.table[position].key === key) {       
        delete this.table[position]; / / {1}
        this.verifyRemoveSideEffect(key, position); 
        return true;     
      }     
      let index = position + 1;     
      while (this.table[index] ! =null && this.table[index].key ! == key ) { index++; }if (this.table[index] ! =null && this.table[index].key === key) {       
        delete this.table[index]; / / {3}
        this.verifyRemoveSideEffect(key, index); / / {4}
        return true; }}return false; 
  }
  // Side effect validation
  verifyRemoveSideEffect(key, removedPosition) {   
    const hash = this.hashCode(key); / / {1}
    let index = removedPosition + 1; / / {2}
    while (this.table[index] ! =null) { / / {3}
      const posHash = this.hashCode(this.table[index].key); / / {4}
      if (posHash <= hash || posHash <= removedPosition) { / / {5}
        this.table[removedPosition] = this.table[index]; / / {6}
        delete this.table[index]; removedPosition = index; } index++; }}}Copy the code

conclusion

A pupil in the front end

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

JS data structure (3)– dictionary and hash table

preface

The dictionary

define

methods

implementation

Hash table

define

methods

implementation

Handle conflicts in hash tables

define

The separation of link

define

implementation

Linear probe

define

implementation

conclusion

JS data structure (3)– dictionary and hash table

preface

The dictionary

define

methods

implementation

Hash table

define

methods

implementation

Handle conflicts in hash tables

define

The separation of link

define

implementation

Linear probe

define

implementation

conclusion

Related Posts

An API-friendly theme for Vuepress

Learn call, apply and bind

Some Common HTTP Status Codes