SoFunction
Updated on 2025-03-02

Example of implementing dictionary and hash table structures corresponding to key values ​​in JavaScript

javascript implementation of Dictionary
Programming ideas:

  • The bare object datastore is used for element storage;
  • Two methods for obtaining dictionary length are implemented, one is variable tracking and the other is real-time calculation.

Code:

function(){
  "use strict";

  function Dictionary(){
    this._size = 0;
     = (null);
  }

   = function(){
    return this._size === 0;
  };

   = function(){
    return this._size;
  };

   = function(){
    for(var key in ){
      delete [key];
    }
    this._size = 0;
  };

   = function(key, value){
    [key] = value;
    this._size++;
  };

   = function(key){
    return [key];
  };

   = function(){
    var n = 0;
    for(var key in ){
      n++;
    }
    return n;
  };

   = function(key){
    delete [key];
    this._size--;
  };

   = function(){
    for(var key in ){
      (key + "->" + [key]);
    }
  };

   = Dictionary;
})();

JavaScript implementation of hash (hashtable)
Programming ideas:

  • Use linked lists to solve the problem of opening the link method to solve the collision, and use the single linked list library LinkedList written by yourself (see https:///article/ before jb51 for details);
  • Use naked objects to store;
  • ValuePair simple encapsulation of key-value pairs;
  • Organize code in module mode;

Code:

(function(){
  "use strict";

  function ValuePair(key, value){
     = key;
     = value;
  }

   = function(){
    return "[" +  + ":" +  + "]";
  };

   = ValuePair;

})();



(function(){

  "use strict";

  var ValuePair = require("./lib/ValuePair");
  var LinkedList = require("./LinkedList");

  function Hashtable(){
     = (null);
    this._size = 0;
  }

   = function(){
    return this._size === 0;
  };

   = function(){
    return this._size;
  };

   = function(key){
    var index = hashCode(key);

    if([index] == null){
      return false;
    }else{
      var currNode = [index].getHead();
      while(){
        currNode = ;
        if( == key){
          [index].remove();
          this._size--;
          return true;
        }
      }
      return false;
    }
  };

   = function(key){
    var index = hashCode(key);

    if([index] == null){
      return null;
    }else{
      var currNode = [index].getHead();
      while(){
        currNode = ;
        if( == key){
          return ;
        }
      }
      return null;
    }
  };

   = function(key, value){
    var index = hashCode(key);

    if([index] == null){
      [index] = new LinkedList();
    }

    var currNode = [index].getHead();
    while(){            //If the key already exists, modify the value to the new value      currNode = ;
      if( == key){
         = value;
        break;
      }
    }

    if( == null &&  != value){         //The key does not exist, add a new value. Pay attention to the boundary value.      [index].add(new ValuePair(key,value));
      this._size++;
    }

    return this;
  };

   = function(){
    for(var key in ){
      var currNode = [key].getHead();
      while(){
        currNode = ;
        (());
      }
    }
  };


  /*********************** Utility Functions ********************************/

  function hashCode(key) {        //Horner's algorithm, prime number is 37    var hashValue = 6011;
    for (var i = 0; i < ; i++) {
      hashValue = hashValue * 37 + (i);
    }
    return hashValue % 1019;
  }

   = Hashtable;

})();