JavaScript – Hash Table Implementation

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)