preface

Dictionaries and hashmaps are data structures that store data in the form of key and value pairs.

This article explains how dictionaries and hash tables are implemented in TypeScript, and invites interested front-end developers to read this article.

Implementation approach

Dictionaries and hash tables store data as key-value pairs, so we can use objects in JavaScript to do this.

Implementation of dictionary

Dictionaries store data in the form of key-value pairs, whose keys are strings and whose keys are whatever the caller passes.

A complete dictionary class should have methods to determine whether a key is in the dictionary, add elements to the dictionary, remove elements stored in the dictionary based on the key, find elements in the dictionary based on the key, and get all elements stored in the dictionary.

  • Add an element to a dictionary (set)

    • The set method takes two arguments: key & Value
    • Determine the validity of the parameters, the key and the value is not null | undefined element is added to the dictionary, otherwise returns false directly
    • If the parameter is valid, the key parameter is converted to a string
    • Take the key converted to a string as the dictionary key, put the key & Value into an object, and store the object in the key converted to a string.
    • With that said, we have successfully added an element to the dictionary that returns true.

  • Check whether a key is in the dictionary (hasKey)

    • The hasKey method takes one argument: key
    • Because the data is stored in the form of the object in the dictionary, so we can directly to the key to a string, then the object as properties to the dictionary, decide whether to return the result it is undefined | null can know whether the key is in the dictionary.

  • Get the value stored in the dictionary by key (get)

    • The get method takes one argument: key
    • Convert the key to a string, pass it as an attribute to the dictionary object, and use a variable to receive its return value.
    • Whether the return value null | is undefined
    • If the return value is not null | undefined it returns the value of the object value, otherwise it returns undefined.

  • Remove an element from a dictionary by key

    • The remove method takes one argument: key
    • Check if the target argument exists in the dictionary object (call hasKey), return false if it does not
    • If the target element exists in the dictionary object, we convert the key to a string, pass it as an argument to the dictionary object, and finally call the object’s delete method to delete the target key, returning true

  • Get all objects stored in the dictionary (keyValues)

    • The keyValues method takes no arguments and returns an array of objects
    • First, declare an array variable (valuePairs) to store the fetched objects
    • Gets all keys in the dictionary object
    • Iterating over the obtained key, passing the iterated key as an argument to the dictionary object.
    • Put the value returned by the dictionary object into valuePairs and return it.

  • Obtain all keys stored in the dictionary & Obtain all values stored in the dictionary (value)

    • The keys method takes any arguments
    • Declare an array variable (keys) are used to store access to key | declare an array variable (values) are used to store to get the value
    • Get all objects stored in the dictionary (call keyValues method)
    • Iterate over the array of objects obtained
    • If you want to get a key, put the key value of the currently traversed element into the keys array, otherwise put the value of values into the values array.
    • Returns the keys | values

  • Iterating through the data in the dictionary (forEach)

    • The forEach method takes as an argument a callback function that takes two arguments: key & Value
    • Gets all the data in the dictionary
    • The callback function is called to pass the key and value of the currently iterated object to the callback function, and a variable (result) is used to hold the result
    • If result is false, the dictionary element has been iterated and the loop exits

  • Get the size of the dictionary, call keyValues, and return its array length

  • To determine whether the dictionary isEmpty (isEmpty), call size to determine whether it is 0 and return the result.

  • To clear the dictionary, initialize the dictionary object as an empty object

  • Convert dictionary data to a string (toString)

    • The toString method takes no arguments
    • If the dictionary is empty, the empty string is returned.
    • Retrieves all data in the dictionary when the dictionary is not empty.
    • Declare a variable (objString) that holds each object in the dictionary, starting with the number 0 in the dictionary object array
    • Iterate over the acquired object, concatenate objString with the traversed data, and return objString.

Implementation of hash table

A hash table, also known as a hash table, is another implementation of a dictionary, which differs from a dictionary in its storage of key values.

Dictionaries store elements by converting keys to strings.

When storing elements in a hash table, the key is hashed and the element is stored after the hash value is obtained.

When looking up elements, dictionaries need to iterate over the entire data structure to find the target element, whereas hash tables are stored with hash values, so we can quickly find the target element by simply calculating the hash value of the target element. Therefore, hash tables are more efficient than dictionaries.

Due to the hash table than hash table has many of the same place, but they store data is not the same as the key, so we need to put the methods required to write an interface, respectively, according to the characteristics of their respective to implement this interface, then we have to analyze the hash table with the implementation of different places in the dictionary of the method.

  • Adding elements to a hash table (PUT)

    • Like the dictionary implementation, it takes two arguments and determines whether they are valid
    • Call the hashCode function (we’ll do it ourselves) to calculate the hash value, taking the key argument
    • The resulting hash value is stored in the hash table as a key, and its value is the same as the dictionary value

  • Calculate the hash value (hashCode)

    • There are several solutions for generating hash values, and this article covers only two of the most common.
    • Need to use the hash function called (loseloseHashCode | djb2HashCode)

  • LoseloseHashCode computes the hash value

    • First, we check if the key is a number, and if it’s a number, we return it, we don’t hash it
    • Converts the key to a string and declares a variable (hash) to store the hash value
    • Iterate over the key converted to a string, call THE JS charCodeAt function to find the Unicode code for each character, and add the obtained Unicode code to the hash
    • After the traversal is complete, divide the hash value by 37 and return the hash to avoid a large number.

  • Djb2HashCode computes the hash value

    • As with the loseloseHashCode method, determine if the key is a number and then convert it to a string
    • The difference is that hash has an initial value of 5381
    • Iterate over the key converted to a string, get the Unicode code for each character iterated, multiply the hash value by 33, and add the obtained Unicode code to it
    • When the traversal is complete, divide the hash value by 1013 and return the hash

  • Get hash table elements by key (GET)

    • Hash the key and get the result. Pass the key as a parameter to the hash table object to get the elements of the target key in the hash table
    • Determine whether the result is null | undefined, if is it returns undefined, otherwise it returns to its value

  • Remove an element from a hash table by key

    • Hashes the key to see if it is in the hash or returns false if it is not
    • Key Passes the calculated hash value to the hash table as an attribute. The delete method is called to delete the key of the target element. Returns true

  • The other methods are basically the same as the dictionary implementation, with the only difference being their handling of keys.

Handle Hash value conflicts in a Hash table

When we use HashMap, if we call the hash value calculated by loseloseHashCode method, the collision rate will be very high. Here are two common methods to deal with the problem of hash conflict.

The separation of link

The split chaining method creates a linked list for each position in the hash table and stores the elements in it. It is the easiest way to resolve conflicts, but it takes up extra storage space.

Since the method of separating links only changes the storage structure of HashMap, we can inherit HashMap and rewrite methods that are different from HashMap.

  • Change the variable name of the private table, since the value of the split link method is a linked list type and the HashMap uses ValuePair type, there is no real private attribute in JS, the type of the table attribute cannot be changed when inherited, so we need to change the variable name (tableLink).

  • Override the put method

    • As with a HashMap, determine the validity of its key & value
    • Calculates the hash value of the key and stores it in a variable (position)
    • Will the position as a parameter to tableLink whether it is null | is undefined
    • If not null | undefined, create a linked list in tableLink position location
    • Adds a Key & Value object to the list of positions on the table
    • True is returned after successful addition

  • Override the get method (need to get elements from the list)

    • Calculates the hash value of the key and stores it in a variable (position)
    • Gets the linked list structure element stored in position
    • If the list is not empty, iterating from the head of the list until the key of the currently iterated list element is the same as the key of the target parameter, then the corresponding value is returned
    • Return undefined if the list is empty

  • Override remove method (need to remove elements from list)

    • Calculates the hash value of the key and stores it in a variable (position)
    • Gets the list structure element for position
    • If the list is not empty, start at the head of the list.
    • If the list element currently traversed is the same as the target parameter key, the element in the current list is removed from the list.
    • If the linked list is empty, the position element on the table is deleted
    • Return undefined if the list is empty

  • Override the clear method to point the tableLink to an empty object

  • Rewrite the keyValues method to retrieve the stored objects from the linked list in HashMap (valuePair).

    • Declare an array variable (valuePairs) to store the fetched valuePairs object
    • Get all keys on the tableLink, convert them to int, and store them in a variable.
    • Keys is iterated to retrieve the current iterated linkedList element data, which is stored in the linkedList variable
    • If the linkedList is not empty, it iterates through the list starting at the head of the list, retrieves the currently iterated list element, and stores it in valuePairs.
    • Return valuePairs
Linear probe

Another approach to conflict resolution is linear probe, which is called linear because it handles collisions by storing elements directly in a table, rather than in a separate data structure.

When you want to add a new element to a position in the table, try position + 1 if the index position is already occupied, position + 2 if position + 1 is already occupied, and so on. Until a free position is found in the hash table.

Now, let’s see what we need to rewrite to solve conflicts with linear probes

  • Override the put method

    • As with a HashMap, you need to determine the validity of its parameters and the number of parameters passed
    • Computes the hash value of the key and stores it in a variable (position)
    • Check whether the position of the table is occupied
    • If it is not occupied, create a new object in position to store the key & Value
    • If occupied, use a variable (index) to receive the value of position+1
    • Iterates through the index position of the table. If the index position is not empty, the index keeps increasing.
    • When a free position is found in the table, create a new object in the index position of the table to store the Key and Value, return true

  • Override the get method

    • Computes the hash value of the key and stores it in a variable (position)
    • Judge whether the elements of the table position location is null | undefined, if not it returns undefined
    • Check whether the key of the position element in the table is equal to the key of the target parameter. If so, return the value of position
    • If not, use a variable (index) to store the value of position+1
    • Iterate over the index position of the table. If the index position is not empty and the key of the index position is not equal to the key of the target parameter, the index is incremented
    • At the end of the loop, check whether the key of the index element of the current table is equal to the key of the target parameter. If so, return the value of the index position

  • Override remove method

    • Computes the hash value of the key and stores it in a variable (position)
    • Check whether the table position is null. If it is null, return false
    • If the key in position of the table is equal to the key of the target parameter, delete the element in position, verify whether the deletion has side effects, adjust the position of the element, return true
    • If not, declare a variable (index) to find the value following position. The default value is position + 1
    • Iterating over the index position of the table, index increments if the element is not null and its key is not equal to the target key
    • After traversal, if the element at index position is not null and the key of the element at index position is equal to the key of the target parameter, delete the element at index position in the table, verify whether the deletion has side effects, adjust the position of the element, and return true

  • New verifyRemoveSideEffect. If a conflict occurs after an element is removed, the conflicting element needs to be moved to a previous location so that no empty space is created.

    • The verifyRemoveSideEffect method receives the parameters: the deleted key, removedPosition of the deleted key in the table
    • Computes the hash value of the key and stores it in a variable.
    • Receive the next position (index) of the deleted key position with a variable. The default is removedPosition+1
    • If the index element is not null, retrieve the hash value of the key at the current index position and store it in a variable (posHash).
    • If posHash is less than or equal to hash or posHash is less than or equal to removedPosition, assign elements at index position in the table to removedPosition
    • Delete the index element from the table
    • Assign index to removedPosition
    • Move on to the next round of judgment

The implementation code

After analysis, we have an implementation idea, which we can then translate into code.

Writing a Map interface

We know that dictionaries and hash tables have many common methods, so we need to separate the common methods into interfaces and implement different interfaces according to different requirements.

  • Create the map. ts file
  • Create the dictionary-list-models.ts file
  • Add and export a ValuePair class in dictionary-list-Models that stores values in the dictionary
// Generate an object
export class ValuePair<K,V>{
    constructor(public key: K,public value: V) {}

    toString(){
 return ` [#The ${this.key}: The ${this.value}] `;  } } Copy the code
  • Import the ValuePair class into the Map, add and define the methods we will use later and specify their return value types
import {ValuePair} from ".. /.. /utils/dictionary-list-models.ts";

export default interface Map<K,V> {
    hasKey(key: K): boolean;
    set? (key: K, value: V):boolean;
put? (key: K, value: V):boolean; hashCode? (key: K):number;  remove(key: K): boolean;  get(key: K): V|undefined;  keyValues(): ValuePair<K, V>[];  keys(): K[];  values(): V[];  forEach(callbackFn: (key: K, value: V) = > any) :void;  size(): number;  isEmpty(): boolean;  clear():void;  toString():string; } Copy the code

Implementing dictionary classes

  • Create a new dictionary. ts file and add a Dictionary class to implement the Map interface
export default class Dictionary<K, V> implements Map<K, V> {

}
Copy the code
  • Declare the private property table for dictionary storage
    private table: { [key: string]: ValuePair<K, V> };
Copy the code
  • Initialize table in the constructor, declare the value to string function and give it a default value
// toStrFn is used to convert a value to a string
    constructor(private toStrFn: (key: K) => string = defaultToString) {
        this.table = {};
    }
Copy the code
  • Implementing the set method
    // Add elements to the dictionary
    set(key: K, value: V) {
        if(key ! =null&& value ! =null) {
            // Convert the key to a string. The key required in the dictionary is a string
            const tableKey = this.toStrFn(key);
 this.table[tableKey] = new ValuePair(key, value);  return true;  }  return false;  } Copy the code
  • Implement the hasKey method
    hasKey(key: K) {
        return this.table[this.toStrFn(key)] ! =null;
    }
Copy the code
  • Implement the GET method
    get(key: K) {
        const valuePair = this.table[this.toStrFn(key)];
        return valuePair == null ? undefined : valuePair.value;
    }
Copy the code
  • Implement the remove method
    remove(key: K) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
 return false;  } Copy the code
  • Implement the keyValues method
    keyValues(): ValuePair<K, V>[] {
        /* Use the Object. Values method introduced in ES2017 to directly retrieve the values of all corresponding keys stored in the Object into an array */
        const valuePairs = [];
        const keys = Object.keys(this.table);
        for (let i = 0; i < keys.length; i++){
 valuePairs.push(this.table[keys[i]])  }  return valuePairs;  } Copy the code
  • Implement keys
    keys() {
        // You can use map directly to obtain the key of the object
        // return this.keyValues().map(valuePair=> valuePair.key);
        const keys = [];
        const valuePairs = this.keyValues();
 for (let i = 0; i < valuePairs.length; i++) {  keys.push(valuePairs[i].key);  }  return keys;  } Copy the code
  • Implement values method
    values() {
        const values = [];
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            values.push(valuePairs[i].value);
 }  return values;  } Copy the code
  • Implement the forEach method
    forEach(callbackFn: (key: K, value: V) = > any) {
        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;  }  }  } Copy the code
  • Implement size, isEmpty, clear methods
    size() {
        return this.keyValues().length;
    }

    isEmpty() {
 return this.size() === 0;  }   clear() {  this.table = {};  } Copy the code
  • Implement the toString method
    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;  } Copy the code

For the complete code, go to dictionary.ts

Write test code

Now that we’ve implemented the dictionary class, let’s test to see if everything works

const dictionary = new Dictionary();
dictionary.set("name"."Zhang");
dictionary.set("age".20);
dictionary.set("id".198);
console.log("Check whether name is in the dictionary",dictionary.hasKey("name"));
// Remove the key named id dictionary.remove("id"); console.log("Check whether id is in dictionary",dictionary.hasKey("id")); console.log("Convert the data stored in the dictionary to a string",dictionary.toString()) // Get the value named name in the dictionary console.log("Value named name in dictionary",dictionary.get("name")); // Get all the stored values in the dictionary console.log("All values stored in the Dictionary",dictionary.keyValues()); // Get all the keys in the dictionary console.log("All the keys stored in the Dictionary",dictionary.keys()); // Get all the values in the dictionary console.log("All values stored in the Dictionary",dictionary.values()); // Iterate over each key-value pair in the dictionary const obj = {}; dictionary.forEach(function (key,value) {  obj[key] = value; }) console.log(obj) Copy the code

Complete code please move:DictionaryTest.js

Implement a hash table

  • Create a HashMap class to implement the Map interface.
export class HashMap<K,V> implements Map<K, V>{

}
Copy the code
  • Declare table and specify its type
    protected table:{ [key:number]: ValuePair<K, V> };
Copy the code
  • Initialize the table in the constructor and specify the value to string function, allowing the caller to pass a value string function
    constructor(protected toStrFn: (key: K) => string = defaultToString) {
        this.table = {};
    }
Copy the code
  • Implement hashCode, loseloseHashCode, djb2HashCode methods
    // Generate hash code
    hashCode(key: K): number {
        return this.loseloseHashCode(key);
    }

 // Loselose implements hash functions  loseloseHashCode(key: K): number {  if (typeof key === "number") { return key;  }  const tableKey = this.toStrFn(key);  let hash = 0;  for (let i = 0; i < tableKey.length; i++){  // Get the ASCII code for each character and concatenate it into the hash  hash += tableKey.charCodeAt(i);  }  return hash % 37;  }   Djb2 implements hash functions  djb2HashCode(key: K): number {  if (typeof key === "number") { return key;  }   // Convert the argument to a string  const tableKey = this.toStrFn(key);  let hash = 5381;  for (let i = 0; i < tableKey.length; i++){  hash = (hash * 33) + tableKey.charCodeAt(i);  }  return hash % 1013;  } Copy the code
  • Implement the PUT method
    put(key: K, value: V): boolean {
        if(key ! =null&& value ! =null) {            const position = this.hashCode(key);
            this.table[position] = new ValuePair(key, value);
            return true;
 }  return false;  } Copy the code
  • Implement the GET method
    get(key: K): V|undefined {
        const valuePair = this.table[this.hashCode(key)];
        return valuePair == null ? undefined : valuePair.value;
    }
Copy the code
  • Implement the hasKey method
    hasKey(key: K): boolean {
        return this.table[this.hashCode(key)] ! =null;
    }
Copy the code
  • Implement the remove method
    remove(key: K): boolean {
        if(this.hasKey(key)){
            delete this.table[this.hashCode(key)];
            return true;
        }
 return false;  } Copy the code
  • Implement keyValues, keys, values methods
    keyValues(): ValuePair<K, V>[] {
        const valuePairs = [];
        // Get all the keys in the object and convert them to an array of type int
        const keys = Object.keys(this.table).map(item= > parseInt(item));
        for (let i = 0; i < keys.length; i++){
 valuePairs.push(this.table[keys[i]]);  }  return valuePairs;  }   keys(): K[] {  const keys = [];  const valuePairs = this.keyValues();  for (let i = 0; i < valuePairs.length; i++){  keys.push(valuePairs[i].key);  }  return keys;  }   values(): V[] {  const values = [];  const valuePairs = this.keyValues();  for (let i = 0; i < valuePairs.length; i++){  values.push(valuePairs[i].value);  }  return values;  } Copy the code
  • Implement isEmpty, size, clear methods
    isEmpty(): boolean {
        return this.values().length === 0;
    }
    
    size(): number {
 return this.keyValues().length;  }   clear(): void {  this.table= {};  } Copy the code
  • Implement the forEach method
    forEach(callbackFn: (key: K, value: V) = > any) :void {
        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;  }  }  } Copy the code
  • Implement the toString method
    toString(): string {
        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;  } Copy the code

For the complete code, go to hashmap.ts

Write test code

Let’s test the above code to see if it works

const hashMap = new HashMap();
hashMap.put("name"."Zhang");
hashMap.put("id".1);
hashMap.put("class"."Products");
console.log("Check whether the class exists in the HashMap", hashMap.hasKey("class"));
hashMap.remove("id"); console.log("Check whether id exists in HashMap", hashMap.hasKey("id")) console.log(hashMap.get("name")); hashMap.forEach(((key, value) = > {  console.log(key +"="+ value); })) console.log("Determine whether data in HashMap is empty",hashMap.isEmpty()); console.log("Output values for all keys in the HashMap",hashMap.keyValues()); console.log("Get all keys in the HashMap",hashMap.keys()); console.log("Get all values in the HashMap",hashMap.values()); console.log("Get the size of the HashMap",hashMap.size()); console.log("Convert data to string output in HashMap",hashMap.toString()); console.log("Empty the data in the HashMap"); hashMap.clear(); // Test hash conflicts hashMap.put('Ygritte'.'[email protected]'); hashMap.put('Jonathan'.'[email protected]'); hashMap.put('Jamie'.'[email protected]'); hashMap.put('Jack'.'[email protected]'); hashMap.put('Jasmine'.'[email protected]'); hashMap.put('Jake'.'[email protected]'); hashMap.put('Nathan'.'[email protected]'); hashMap.put('Athelstan'.'[email protected]'); hashMap.put('Sue'.'[email protected]'); hashMap.put('Aethelwulf'.'[email protected]'); hashMap.put('Sargeras'.'[email protected]'); console.log(hashMap.toString()); Copy the code

Complete code please move:HashMapTest.js

Separate linked list method to solve hash conflict

After executing the above test code, we found that some values were conflicting and replaced, causing data loss problems.

Let’s look at how linked lists can be combined to resolve conflicts.

  • New HashMapSeparateChaining ts file, add HashMapSeparateChaining class inherits from HashMap
export default class HashMapSeparateChaining<K,V> extends HashMap<K, V> {

}
Copy the code
  • Declare a private property tableLink and define its type for the storage of the table.
    private tableLink:{ [key: number]: LinkedList<ValuePair<K, V>> };
Copy the code
  • Declare the toStrFn method in the constructor to give the default value and initialize the parent class and tableLink
    constructor(protected toStrFn: (key: K) => string = defaultToString) {
        super(toStrFn);
        this.tableLink = {};
    }
Copy the code
  • Override the put method
    put(key: K, value: V): boolean {
        if(key ! =null&& value ! =null) {
            const position = this.hashCode(key);
            if (this.tableLink[position] == null) {                // Create a linked list if the current location to add elements is empty
 this.tableLink[position] = new LinkedList<ValuePair<K, V>>();  }  // Add the current element to the current list  this.tableLink[position].push(new ValuePair(key,value));  return true;  }  return false;  } Copy the code
  • Override the get method
    get(key: K): V | undefined {
        // Get the hash value of the argument
        const position = this.hashCode(key);
        // Get the list structure element stored at the target element location
        const linkedList = this.tableLink[position];
 if(linkedList ! =null && !linkedList.isEmpty()){  // Get the list header data  let current = linkedList.getHead();  while(current ! =null) { // Walk through the list to find the same data in the list as the target parameter  if (current.element.key === key){  // Return the value of the target key  return current.element.value;  }  current = current.next;  }  }  return undefined;  } Copy the code
  • Override remove method
    remove(key: K): boolean {
        const position = this.hashCode(key);
        // Get the list structure element stored at the target element location
        const linkedList = this.tableLink[position];
        if(linkedList ! =null && !linkedList.isEmpty()){
 // Get the list header element  let current = linkedList.getHead();  while(current ! =null) { // Iterate through the list to find the same data as the target element  if (current.element.key === key){  // Remove the current list element from the list  linkedList.remove(current.element);  if (linkedList.isEmpty()){  // If the list is empty, delete the target location element  delete this.tableLink[position];  }  return true;  }  current = current.next;  }  }  return false;  } Copy the code
  • Override clear method
    clear() {
        this.tableLink = {};
    }
Copy the code
  • Override the keyValues method
    keyValues(): ValuePair<K, V>[] {
        const valuePairs = [];
        // Get all keys on the tableLink and convert them to int
        const keys = Object.keys(this.tableLink).map(item= >parseInt(item));
        for (let i = 0; i < keys.length; i++){
 const linkedList = this.tableLink[keys[i]];  if(linkedList ! =null && !linkedList.isEmpty()){  // Iterate over the data in the list, putting the data in the list into valuePairs  let current = linkedList.getHead();  while(current ! =null) { valuePairs.push(current.element);  current = current.next;  }  }  }  return valuePairs;  } Copy the code

The complete code please click: HashMapSeparateChaining. Ts

Write test code

Let’s test if all of the above methods work

const hashMapSC = new HashMapSeparateChaining();
hashMapSC.put("name"."Zhang");
hashMapSC.put("id".11);
hashMapSC.put("age".22);
hashMapSC.put("phone"."09871588");
hashMapSC.remove("id"); console.log(hashMapSC.get("name")); console.log("Determine whether data in hashMap is empty", hashMapSC.isEmpty()); console.log(hashMapSC.toString()); console.log("Use forEach to traverse the data in the hashMap"); hashMapSC.forEach((key,value) = >{  console.log(`${key} = ${value}`); }) console.log("Get all keys stored in the hashMap",hashMapSC.keys()); console.log("Get all values stored in the hashMap",hashMapSC.values()); console.log("Check if ID is in hashMap",hashMapSC.hasKey("id")); console.log("Empty the data in the HashMap"); hashMapSC.clear(); console.log("Determine whether data in HashMap is empty", hashMapSC.isEmpty()); console.log("Collision test") hashMapSC.put('Ygritte'.'[email protected]'); hashMapSC.put('Jonathan'.'[email protected]'); hashMapSC.put('Jamie'.'[email protected]'); hashMapSC.put('Jack'.'[email protected]'); hashMapSC.put('Jasmine'.'[email protected]'); hashMapSC.put('Jake'.'[email protected]'); hashMapSC.put('Nathan'.'[email protected]'); hashMapSC.put('Athelstan'.'[email protected]'); hashMapSC.put('Sue'.'[email protected]'); hashMapSC.put('Aethelwulf'.'[email protected]'); hashMapSC.put('Sargeras'.'[email protected]'); console.log(hashMapSC.toString()); Copy the code

Complete code please move:HashMapSeparateChainingTest.js

Linear probe to solve the hashing problem

  • Create a new HashMapLinearProbing. Ts file and add the HashMapLinearProbing class inherited from HashMap
export default class HashMapLinearProbing<K,V> extends HashMap<K, V>{

}
Copy the code
  • Constructor to initialize the parent class
    constructor() {
        super(a);    }
Copy the code
  • Override the put method
    put(key: K, value: V): boolean {
        if(key ! =null&& value! =null) {            const position = this.hashCode(key);
            // Determine whether the current position is occupied in the table
            if (this.table[position] == null) { // If the current position is not occupied, place the Key & Value in ValuePair for the element in the current table to be inserted  this.table[position] = new ValuePair(key,value);  } else{  // The position is occupied, incrementing index until the position is not occupied  let index = position + 1;  while (this.table[index] ! =null) { index++;  }  // Find the position that is not occupied and place the Key & Value in ValuePair to the element in the current table where the value is to be inserted  this.table[index] = new ValuePair(key,value);  }  return true;  }  return false;  } Copy the code
  • Override the get method
    get(key: K): V | undefined {
        const position = this.hashCode(key);
        if(this.table[position] ! =null) {
            // If the key of the current location element is equal to the key of the target element, return the value of the current location element
            if (this.table[position].key === key){
 return this.table[position].value;  }  // Position increments until we find the element we are looking for or an empty position is found  let index = position + 1;  while (this.table[index] ! =null && this.table[index].key ! == key){ index++;  }  // Determine whether the index key in the current table is equal to the target key  if (this.table[index] ! =null && this.table[index].key === key){  return this.table[index].value;  }  }  return undefined;  } Copy the code
  • Override remove method
    remove(key: K): boolean {
        const position = this.hashCode(key);
        if (this.table[position] ! =null) {            if (this.table[position].key === key){
                delete this.table[position];
 // After the deletion, verify that the deletion has no side effects and adjust the element position  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];  this.verifyRemoveSideEffect(key,index);  return true;  }  }  return false;  } Copy the code
  • Implement the verifyRemoveSideEffect method
    // Verify that the delete operation has any side effects
    private verifyRemoveSideEffect(key: K,removedPosition: number) {        // Calculate the hash value of the deleted key
        const hash = this.hashCode(key);
        // Start traversing the table from the next deleted element position until an empty position is found
 // When an empty position is found, the element does not need to be moved in the appropriate position  let index = removedPosition + 1;  while (this.table[index] ! =null) { // Computes the hash value of the current iterated element key  const posHash = this.hashCode(this.table[index].key);  console.log('Hash = of the currently traversed element${posHash}, hash = of the last key removed${removedPosition}`)  if (posHash <= hash || posHash <= removedPosition){  // If the current element hash is less than or equal to the deleted element hash or less than or equal to the last removed key hash (removedPosition)  // The current element needs to be moved to removedPosition  this.table[removedPosition] = this.table[index];  // After the move is complete, delete the element at the current index position  delete this.table[index];  // Update removedPosition to index  removedPosition = index;  }  index++;  }  } Copy the code

For the complete code, go to hashMaplinearplugi.ts

Write test code

Test whether all the above methods work properly

const hashMapLP = new HashMapLinearProbing();
console.log("Conflicting element Deletion Test");
hashMapLP.put('Ygritte'.'[email protected]');
hashMapLP.put('Jonathan'.'[email protected]');
hashMapLP.put('Jamie'.'[email protected]');
hashMapLP.put('Jack'.'[email protected]'); hashMapLP.put('Jasmine'.'[email protected]'); hashMapLP.put('Jake'.'[email protected]'); hashMapLP.put('Nathan'.'[email protected]'); hashMapLP.put('Athelstan'.'[email protected]'); hashMapLP.put('Sue'.'[email protected]'); hashMapLP.put('Aethelwulf'.'[email protected]'); hashMapLP.put('Sargeras'.'[email protected]'); // hashMapLP.remove("Ygritte"); hashMapLP.remove("Jonathan"); console.log(hashMapLP.toString()); Copy the code

Complete code please move:HashMapLinearProbing.ts

Better hash functions

In this code we use loseloseHashCode to generate hash values. This method generates a lot of duplicate elements, so it is not recommended because handling conflicts can be costly in performance.

We implemented the djb2HashCode method in the above code, which has a low probability of producing duplicate hash values, so we should use this method to generate them. Next, we change the method used for hashCode to djb2HashCode to test the results of the HashMap execution.

    hashCode(key: K): number {
        return this.djb2HashCode(key);
    }
Copy the code

❝

The result is as we expected, it doesn’t duplicate the hash value, and all the elements are saved.

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌