jsHashtable vs Builtin objects (v4)

Revision 4 of this benchmark created by pcowdogg on


Preparation HTML

<script>
  /**
   * Copyright 2010 Tim Down.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  var Hashtable = (function() {
    var p = "function";
    var n = (typeof Array.prototype.splice == p) ?
    function(s, r) {
      s.splice(r, 1)
    } : function(u, t) {
      var s, v, r;
      if (t === u.length - 1) {
        u.length = t
      } else {
        s = u.slice(t + 1);
        u.length = t;
        for (v = 0, r = s.length; v < r; ++v) {
          u[t + v] = s[v]
        }
      }
    };
  
    function a(t) {
      var r;
      if (typeof t == "string") {
        return t
      } else {
        if (typeof t.hashCode == p) {
          r = t.hashCode();
          return (typeof r == "string") ? r : a(r)
        } else {
          if (typeof t.toString == p) {
            return t.toString()
          } else {
            try {
              return String(t)
            } catch (s) {
              return Object.prototype.toString.call(t)
            }
          }
        }
      }
    }
    function g(r, s) {
      return r.equals(s)
    }
    function e(r, s) {
      return (typeof s.equals == p) ? s.equals(r) : (r === s)
    }
    function c(r) {
      return function(s) {
        if (s === null) {
          throw new Error("null is not a valid " + r)
        } else {
          if (typeof s == "undefined") {
            throw new Error(r + " must not be undefined")
          }
        }
      }
    }
    var q = c("key"),
        l = c("value");
  
    function d(u, s, t, r) {
      this[0] = u;
      this.entries = [];
      this.addEntry(s, t);
      if (r !== null) {
        this.getEqualityFunction = function() {
          return r
        }
      }
    }
    var h = 0,
        j = 1,
        f = 2;
  
    function o(r) {
      return function(t) {
        var s = this.entries.length,
            v, u = this.getEqualityFunction(t);
        while (s--) {
          v = this.entries[s];
          if (u(t, v[0])) {
            switch (r) {
            case h:
              return true;
            case j:
              return v;
            case f:
              return [s, v[1]]
            }
          }
        }
        return false
      }
    }
    function k(r) {
      return function(u) {
        var v = u.length;
        for (var t = 0, s = this.entries.length; t < s; ++t) {
          u[v + t] = this.entries[t][r]
        }
      }
    }
    d.prototype = {
      getEqualityFunction: function(r) {
        return (typeof r.equals == p) ? g : e
      },
      getEntryForKey: o(j),
      getEntryAndIndexForKey: o(f),
      removeEntryForKey: function(s) {
        var r = this.getEntryAndIndexForKey(s);
        if (r) {
          n(this.entries, r[0]);
          return r[1]
        }
        return null
      },
      addEntry: function(r, s) {
        this.entries[this.entries.length] = [r, s]
      },
      keys: k(0),
      values: k(1),
      getEntries: function(s) {
        var u = s.length;
        for (var t = 0, r = this.entries.length; t < r; ++t) {
          s[u + t] = this.entries[t].slice(0)
        }
      },
      containsKey: o(h),
      containsValue: function(s) {
        var r = this.entries.length;
        while (r--) {
          if (s === this.entries[r][1]) {
            return true
          }
        }
        return false
      }
    };
  
    function m(s, t) {
      var r = s.length,
          u;
      while (r--) {
        u = s[r];
        if (t === u[0]) {
          return r
        }
      }
      return null
    }
    function i(r, s) {
      var t = r[s];
      return (t && (t instanceof d)) ? t : null
    }
    function b(t, r) {
      var w = this;
      var v = [];
      var u = {};
      var x = (typeof t == p) ? t : a;
      var s = (typeof r == p) ? r : null;
      this.put = function(B, C) {
        q(B);
        l(C);
        var D = x(B),
            E, A, z = null;
        E = i(u, D);
        if (E) {
          A = E.getEntryForKey(B);
          if (A) {
            z = A[1];
            A[1] = C
          } else {
            E.addEntry(B, C)
          }
        } else {
          E = new d(D, B, C, s);
          v[v.length] = E;
          u[D] = E
        }
        return z
      };
      this.get = function(A) {
        q(A);
        var B = x(A);
        var C = i(u, B);
        if (C) {
          var z = C.getEntryForKey(A);
          if (z) {
            return z[1]
          }
        }
        return null
      };
      this.containsKey = function(A) {
        q(A);
        var z = x(A);
        var B = i(u, z);
        return B ? B.containsKey(A) : false
      };
      this.containsValue = function(A) {
        l(A);
        var z = v.length;
        while (z--) {
          if (v[z].containsValue(A)) {
            return true
          }
        }
        return false
      };
      this.clear = function() {
        v.length = 0;
        u = {}
      };
      this.isEmpty = function() {
        return !v.length
      };
      var y = function(z) {
          return function() {
            var A = [],
                B = v.length;
            while (B--) {
              v[B][z](A)
            }
            return A
          }
          };
      this.keys = y("keys");
      this.values = y("values");
      this.entries = y("getEntries");
      this.remove = function(B) {
        q(B);
        var C = x(B),
            z, A = null;
        var D = i(u, C);
        if (D) {
          A = D.removeEntryForKey(B);
          if (A !== null) {
            if (!D.entries.length) {
              z = m(v, C);
              n(v, z);
              delete u[C]
            }
          }
        }
        return A
      };
      this.size = function() {
        var A = 0,
            z = v.length;
        while (z--) {
          A += v[z].entries.length
        }
        return A
      };
      this.each = function(C) {
        var z = w.entries(),
            A = z.length,
            B;
        while (A--) {
          B = z[A];
          C(B[0], B[1])
        }
      };
      this.putAll = function(H, C) {
        var B = H.entries();
        var E, F, D, z, A = B.length;
        var G = (typeof C == p);
        while (A--) {
          E = B[A];
          F = E[0];
          D = E[1];
          if (G && (z = w.get(F))) {
            D = C(F, z, D)
          }
          w.put(F, D)
        }
      };
      this.clone = function() {
        var z = new b(t, r);
        z.putAll(w);
        return z
      }
    }
    return b
  })();
  
  
  /*
  =====================================================================
     @license MIT
     @author Daniel Kwiecinski <daniel.kwiecinski@lambder.com>
     @copyright 2009 Daniel Kwiecinski.
     @end
  =====================================================================
  */
  var HashMap = function() {
    this.initialize();
  }
   
  HashMap.prototype = {
    hashkey_prefix: "<#HashMapHashkeyPerfix>",
    hashcode_field: "<#HashMapHashcodeField>",
    hashmap_instance_id: 0,
   
    initialize: function() {
      this.backing_hash = {};
      this.code = 0;
      this.hashmap_instance_id += 1;
      this.instance_id = this.hashmap_instance_id;
    },
   
    hashcodeField: function() {
      return this.hashcode_field + this.instance_id;
    },
    /*
     maps value to key returning previous assocciation
     */
    put: function(key, value) {
      var prev;
   
      if (key && value) {
        var hashCode;
        if (typeof(key) === "number" || typeof(key) === "string") {
          hashCode = key;
        } else {
          hashCode = key[this.hashcodeField()];
        }
        if (hashCode) {
          prev = this.backing_hash[hashCode];
        } else {
          this.code += 1;
          hashCode = this.hashkey_prefix + this.code;
          key[this.hashcodeField()] = hashCode;
        }
        this.backing_hash[hashCode] = value;
      }
      return prev;
    },
    /*
     returns value associated with given key
     */
    get: function(key) {
      var value;
      if (key) {
        var hashCode;
        if (typeof(key) === "number" || typeof(key) === "string") {
          hashCode = key;
        } else {
          hashCode = key[this.hashcodeField()];
        }
        if (hashCode) {
          value = this.backing_hash[hashCode];
        }
      }
      return value;
    },
    /*
     deletes association by given key.
     Returns true if the assocciation existed, false otherwise
     */
    del: function(key) {
      var success = false;
      if (key) {
        var hashCode;
        if (typeof(key) === "number" || typeof(key) === "string") {
          hashCode = key;
        } else {
          hashCode = key[this.hashcodeField()];
        }
        if (hashCode) {
          var prev = this.backing_hash[hashCode];
          this.backing_hash[hashCode] = undefined;
          if (prev !== undefined)
            success = true;
        }
      }
      return success;
    }
  }
   
  //http://freecode-freecode.blogspot.com/2007/06/hashmap-object-in-javascript-like.html
   function Map()
  {
      // members
      this.keyArray = new Array(); // Keys
      this.valArray = new Array(); // Values
          
      // methods
      this.put = put;
      this.get = get;
      this.size = size;  
      this.clear = clear;
      this.keySet = keySet;
      this.valSet = valSet;
      this.showMe = showMe;   // returns a string with all keys and values in map.
      this.findIt = findIt;
      this.remove = remove;
  }
  
  function put( key, val )
  {
      var elementIndex = this.findIt( key );
      
      if( elementIndex == (-1) )
      {
          this.keyArray.push( key );
          this.valArray.push( val );
      }
      else
      {
          this.valArray[ elementIndex ] = val;
      }
  }
  
  function get( key )
  {
      var result = null;
      var elementIndex = this.findIt( key );
  
      if( elementIndex != (-1) )
      {   
          result = this.valArray[ elementIndex ];
      }  
      
      return result;
  }
  
  function remove( key )
  {
      var result = null;
      var elementIndex = this.findIt( key );
  
      if( elementIndex != (-1) )
      {
          this.keyArray = this.keyArray.removeAt(elementIndex);
          this.valArray = this.valArray.removeAt(elementIndex);
      }  
      
      return ;
  }
  
  function size()
  {
      return (this.keyArray.length);  
  }
  
  function clear()
  {
      for( var i = 0; i < this.keyArray.length; i++ )
      {
          this.keyArray.pop(); this.valArray.pop();   
      }
  }
  
  function keySet()
  {
      return (this.keyArray);
  }
  
  function valSet()
  {
      return (this.valArray);   
  }
  
  function showMe()
  {
      var result = "";
      
      for( var i = 0; i < this.keyArray.length; i++ )
      {
          result += "Key: " + this.keyArray[ i ] + "\tValues: " + this.valArray[ i ] + "\n";
      }
      return result;
  }
  
  function findIt( key )
  {
      var result = (-1);
  
      for( var i = 0; i < this.keyArray.length; i++ )
      {
          if( this.keyArray[ i ] == key )
          {
              result = i;
              break;
          }
      }
      return result;
  }
  
  function removeAt( index )
  {
    var part1 = this.slice( 0, index);
    var part2 = this.slice( index+1 );
  
    return( part1.concat( part2 ) );
  }
  Array.prototype.removeAt = removeAt;
  
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
jsHashtable
var typesHash = new Hashtable();
typesHash.put("A string", "string");
typesHash.put(1, "number");
typesHash.get("not there");
typesHash.get("A string");
typesHash.get(1);
ready
Built-in Objects
var o = new Object();
o["A string"] = "string";
o[1] = "number";
o["not there"];
o["A string"];
o[1];
ready
Daniel Kwiecinski's Hash Map
var typesHash = new HashMap();
typesHash.put("A string", "string");
typesHash.put(1, "number");
typesHash.get("not there");
typesHash.get("A string");
typesHash.get(1);
ready
Map (from somewhere on the internet)
var typesHash = new Map();
typesHash.put("A string", "string");
typesHash.put(1, "number");
typesHash.get("not there");
typesHash.get("A string");
typesHash.get(1);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.