Recently someone tested my knowledge of JavaScript and asked me what types of native data structures exist which can contain an arbitrary amount of data. My answer was that Arrays and Objects can both do this right out of the box. He said that I was mostly correct, but that JS also has hash tables. Although I am only 24 and have a lot to learn about programming, I have also been developing in JS for about 12 years and have never heard about a native HashTable object apart from the Object object. After doing more research I found that such a data structure, aside from the Object one, doesn’t exist natively. Consequently, I decided to write my own Hashtable JavaScript class implementation loosely based on the Java Hashtable class. It defines all of the following prototype functions:

  • Hashtable.prototype.get(key) → Object
    Returns the object at the specified key if it exists, otherwise returns undefined.

  • Hashtable.prototype.keys() → Array
    Returns an Array of all of the keys in this Hashtable.

  • Hashtable.prototype.containsValue(value) → Boolean
    Returns a Boolean value indicating whether or not value is in the Hashtable.

  • Hashtable.prototype.containsKey(key) → Boolean
    Returns a Boolean value indicating whether or not key is in the Hashtable.

  • Hashtable.prototype.clear() → Hashtable
    Removes all of the items from the Hashtable and returns those objects in a Object indexed by the keys of the Hashtable.

  • Hashtable.prototype.elements() → Array
    Returns an Array of all of the elements in this Hashtable.

  • Hashtable.prototype.size() → Number
    Returns the amount of elements that the Hashtable contains.

  • Hashtable.prototype.remove(key) → Object
    Removes the element at the specified key and returns it.

  • Hashtable.prototype.put(key, value) → Object
    Puts value in the hash table at the specified key. If a value existed at that key previously, that value is returned, otherwise undefined is returned.

  • Hashtable.prototype.put(objHash) → Object
    Takes all of the key-value pairs from the specified object and puts them in this hash table. Returns an object indexed by all of the keys that were found in objHash which were previously defined in this Hashtable.

  • Hashtable.prototype.clone() → Hashtable
    Returns a shallow copy of this Hashtable.

  • Hashtable.prototype.isEmpty() → Boolean
    Returns true if this is empty. Otherwise false is returned.

  • Hashtable.prototype.equals() → Boolean
    Returns true if this hash table has all of the same keys and objects defined at those keys as the specified Hashtable object.

  • Hashtable.prototype.forEach(callback [, objThis]) → Hashtable
    Iterates through all of the elements in this and executes the specified callback function for each. The function will be passed the element as the first parameter, the key as the second, and the reference to this Hashtable as the third. If objThis is defined, it will be referenced by the this keyword within the callback function. If objThis is not defined, this will refer to the global object.

The following is the definition for this JavaScript class:


// JavaScript Hashtable - By Chris West - MIT Licensed
(function($) {
  // A reference to the generic hasOwnProperty() function.
  var hasOwnProperty = [].hasOwnProperty;
  
  // This is an IE fix because these will not be found by a for..in statement.
  var unenumerableKeys = "constructor,hasOwnProperty,isPrototypeOf,prototypeIsEnumerable,toLocaleString,toString,valueOf".split(",");
  for(var key, o = {}, i = 0; key = unenumerableKeys[i]; i++) {
    o[key] = i;
    for(key in o) {
      unenumerableKeys.splice(i--, 1);
      delete o[key];
    }
  }
  
  // The constructor for the new Hashtable class.
  function Hashtable(obj) {
    obj = arguments.length ? obj : {};
    
    var hash = {}, key, keys = unenumerableKeys.slice(0), i = 0;
    while(key = keys[i++]) {
      !hasOwnProperty.call(obj, key)
        ? hash[key] = obj[key]
        : keys.splice(i, 1);
    }
    for(key in obj) {
      if(hasOwnProperty.call(obj, key)) {
        keys.push(key);
        hash[key] = obj[key];
      }
    }
    
    var _ = {o : hash, k : keys};
    this._ = function(k) {
      return k === $ ? _ : undefined;
    };
    
    return this;
  }
  
  // Reference for quickly defining prototype functions.
  var p = Hashtable.prototype;
  
  // Returns the item at the specified `key`.
  p.get = function(key) {
    return this._($).o[key];
  };
  
  // Returns an array of all of the keys in the hash table.
  p.keys = function() {
    return this._($).k.slice(0);
  };
  
  // Returns a boolean value indicating whether or not the specified `value` is
  // contained within the hash table.
  p.containsValue = p.contains = function(value) {
    var _ = this._($), keys = _.k, obj = _.o, i = keys.length;
    while(--i >= 0) {
      if(obj[keys[i]] === value) {
        return true;
      }
    }
    return false;
  };
  
  // Returns a boolean value indicating whether or not the specified `key` is
  // contained within the hash table.
  p.containsKey = function(key) {
    var keys = this._($).k, i = keys.length;
    while(--i >= 0) {
      if(keys[i] == key) {
        return true;
      }
    }
    return false;
  };
  
  // Clear the hash table and return the object indexed by the keys that
  // contains all of the items.
  p.clear = function() {
    var _ = this._($), ret = _.o;
    _.k = [];
    _.o = {};
    return ret;
  };

  // Get an array of all of the items.
  p.elements = function() {
    var elems = [],
        _ = this._($),
        keys = _.k,
        i = 0,
        len = keys.length,
        obj = _.o;
    while(i < len) {
      elems.push(obj[keys[i++]]);
    }
    return elems;
  };
  
  // Get the amount of items.
  p.size = function() {
    return this._($).k.length;
  };
  
  // Removes the item at the specified key and returns the item that is removed.
  p.remove = function(key) {
    var _ = this._($), keys = _.k, obj = _.o, i = keys.length;
    while(--i >= 0) {
      if(keys[i] == key) {
        var ret = obj[keys.splice(i, 1)[0]];
        delete obj[key];
        break;
      }
    }
    return ret;
  };
  
  // Puts one or more items in this hash table, returning the previous value(s).
  p.put = function(key, value) {
    var _ = this._($), keys = _.k, obj = _.o;
    // If only one value is to be added...
    if(arguments.length - 1) {
      if(hasOwnProperty.call(obj, key)) {
        ret = obj[key];
      }
      else {
        keys.push(key);
      }
      obj[key] = value;
    }
    // If all of the key-value pairs in the specified object are to be added...
    else {
      var ret = {},
          objNew = key,
          newKeys = (new Hashtable(objNew)).keys(),
          i = newKeys.length;
      while(--i >= 0) {
        _ = newKeys[i];
        if(hasOwnProperty.call(obj, _)) {
          ret[_] = obj[_];
        }
        else {
          keys.push(_);
        }
        obj[_] = objNew[_];
      }
    }
    return ret;
  };
  
  // Makes a shallow copy of the Hashtable.
  p.clone = function() {
    return new Hashtable(this._($).o);
  };
  
  // Returns true if no items in the hash table, otherwise false is returned.
  p.isEmpty = function() {
    return !this._($).k.length;
  };
  
  // Returns true if the specified hash table has all of the same key-value
  // pairs, otherwise returns false.
  p.equals = function(hashTable2) {
    var t, i, _ = this._($), o = _.o, k = _.k,
        _2 = hashTable2._($), o2 = _2.o, k2 = _2.k;
    if(k.length != (i = k2.length)) {
      return false;
    }
    for(;--i >= 0 && hasOwnProperty.call(o, t = k2[i]) && o[t] === o2[t];);
    return i < 0;
  };
  
  // Executes the specified function for each item, sending the specified
  // objThis object (if not specified uses the global object) as the context or
  // `this` object, the item as the first parameter, the key as the second
  // parameter, and this hash table as the final parameter.  Returns a reference
  // to this hash table so that a chained call can occur if desired.
  p.forEach = function(callback, objThis) {
    var ret, _ = this._($), o = _.o, k = _.k;
    for(var i = 0, len = k.length; i < len; i++) {
      callback.call(objThis, o[k[i]], k[i], this);
    }
    return this;
  };

  // If Hashtable is already defined in the global context, save a reference to
  // that definition as the `__OLD__` property of the new Hashtable class that
  // will be defined in the global context.
  if(hasOwnProperty.call(this, "Hashtable")) {
    Hashtable.__OLD__ = this.Hashtable;
  }
  this.Hashtable = Hashtable;
})({});

It is also important to note that changing the value of the `_` property of a Hashtable object will render it useless. Fortunately, almost nobody would think to even define that property anyway, but I felt it necessary to put everyone on notice. The following are some examples of using this Hashtable class:


// Define `me` using an object literal.
var me = new Hashtable({
  firstName : "Christopher",
  lastName : "West",
  age : 23
});

// Define `myFriend` using `me`.
var myFriend = me.clone().put({
  firstName : "Curran",
  lastName : "McCalley"
});

// Add my nickname
me.put("nickname", "Chris");

// Check if I am equal to my friend.
alert("My friend and I are equal:  " + me.equals(myFriend));

// Update my age and notice what my previous age was
alert("My age is being changed from " + me.put("age", 24));

// Show all of the keys that I have.
alert("These are all of my attributes:  " + me.keys());

// Show all of the values that my friend has.
alert("These are all of my friend's attributes:  " + myFriend.values());

If you would like to use a minified version (2 KB) of this class, you can download it here. Please let me know what you think! 8)

Categories: BlogJavaScriptJScript

7 Comments

ildar · November 6, 2012 at 3:56 PM

That person who has asked you was correct and incorrect in the same time. Hashtable is a creature of JScript.NET world and mostly unknown in the universe of JavaScript. It is unknown in usual JScript (as a part of WSH). That person’s answer was incomplete because he has forgotten to tell about Dictionary, another creature by Microsoft, habitant of both JScript.NET and JScript worlds. 🙂

    Chris West · November 6, 2012 at 5:38 PM

    I will take that as a suitable argument. In this case though, the person was incorrect simply because we were having a discussion about JavaScript within any modern-day Internet browser. If we are talking about JScript (WSH), I would definitely consider the Dictionary class another one of those structures that can hold many pieces of data. I will have do some research as far as the Hashtable in JScript.NET is concerned. I love JavaScript (and all of its flavors) and look forward to seeing what JScript.NET has to offer. Thanks for the feedback! 😀

      ildar · November 9, 2012 at 12:44 PM

      In Gecko, JavaScript engine by Mozilla, they have implemented XPCOM interface to native functions by Windows. Hashtable is bundled into there. Possibly there are couple of projects using Hashtable or Dictionary.
      I see how some programmers having more experience in VBScript continue use Dictionary in JScript. They don’t need it because of coming to J(ava)Script world they had got objects as a universal hash. I came to the decision that Dictionary had been implemented for compatibility and/or comfortability of programmers that are not familiar with JavaScript features.

Paul · August 6, 2014 at 6:15 PM

Nice work Chris. I think this will prove to be the perfect class for allowing me to manage groups of points on a google map and allowing them to be toggled. I’ve been battling with a solution for the good part of a day – and being able to use a hashtable (with a familiar interface – and good, concise documentation) is the way I want to go. Hopefully the rest of the solution pans out. Thanks for your work. PK

George · December 16, 2014 at 2:38 PM

No source code? After looking at 3 hashtable implementations I decided to use yours but… not if I can’t improve it. 🙁

    Chris West · December 16, 2014 at 3:45 PM

    Its there. If you click on expand source after where it says “The following is the definition for this JavaScript class”.

Dain Miller · December 21, 2014 at 6:15 AM

Your coding style is really interesting to me. I’m 26, and only have been doing javascript for 2 years professionally (but with albeit not the intelligence you have) and my coding pattern is so inferior to this, it blows me away. I have a hard time even reading this source code, just trying to keep up with what you are doing here with all the keys and objects.

With that being said, do you have any recommendations on how to keep more in our heads when reading source code? For problems like the one I stated above. I imagine it even happens to geniuses like yourself where you read something crazy complex, how do you deal with that?

Leave a Reply

Your email address will not be published. Required fields are marked *