Example Hashtable for WWCDC

Hashtable.js

// Duplicates the String hashcode method in Java
function hashCode(str) {
  var hash = 0, i, chr, len;
  if (str.length === 0) return hash;
  for (i = 0, len = str.length; i < len; i++) {
    chr = str.charCodeAt(i);
    hash = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
}

// The table is just an array,
// an a count of how many cells of the array are being used
function Hashtable() {
  this.table = Array(31);  // 31 is prime
  this.count = 0;
}

// The array holds Entries that contain both the key and value
function Entry(key, value) {
  this.key = key;
  this.value = value;
}

// Insert a key/value pair. The location is determined solely by the key
Hashtable.prototype.put = function(key, value) {
  var hashval = hashCode(key);
  var offset = hashval % this.table.length;
  // check for a collision, if so, then expand the table
  while (typeof this.table[offset] != 'undefined' &&
         this.table[offset].key !== key) {
    this.rehash();
    offset = hashval % this.table.length;
  }
  // finally, put the entry in the array
  this.table[offset] = new Entry(key, value);
  this.count++;
}

// find a value for a key
Hashtable.prototype.get = function(key) {
  // find the entry
  var offset = hashCode(key);
  offset = offset % this.table.length;
  var result = this.table[offset];
  // if the data at this place isn't the entry, then there is nothing to return
  if (typeof result == 'undefined' || result.key !== key) return null;
  return result.value;
}

// remove a key/value pair
Hashtable.prototype.delete = function(key) {
  // find the entry
  var offset = hashCode(key);
  offset = offset % this.table.length;
  // if there is nothing here, or it's the wrong thing, then nothing to do
  if (typeof this.table[offset] == 'undefined' ||
      this.table[offset].key !== key) {
  	return;
  }
  this.table[offset] = undefined;
  this.count--;
}

// expand the table, and insert all existing data into the right places
Hashtable.prototype.rehash = function() {
  var i, new_table, size = this.table.length;
  do {
    // allocated new size. Won't be prime, but don't let it be even
    size = size * 2 + 1;
    new_table = new Array(size);
    // copy everything from the old table to the new
    for (i = 0; i < this.table.length; i++) {
      var element = this.table[i];
      if (typeof element != 'undefined') {
        var offset = hashCode(element.key) % size;
        // if there is a collision in the new table, then expand again and restart
        if (typeof new_table[offset] != 'undefined') break;
        new_table[offset] = element;
      }
    }
    // keep expanding until we made it all the way through the copying
  } while (i < this.table.length);
  this.table = new_table;
}

// iterate through the hashtable, and put all the elements in an array
Hashtable.prototype.as_array = function() {
  // create the destination array
  var i = 0; result = new Array(this.count);
  // iterate through the entire hashtable array, searching for entries
  for (var j = 0; j < this.table.length; j++) {
    var e = this.table[j];
    if (typeof e != ‘undefined’) {
      // found one! Add it to the result.
      result[i++] = e;
      // got everything already, so we can return early
      if (i == this.count) return result;
    }
  }
  // can only get here if the count was not reached, meaning
  // there were more fewer items in the table than the count said
  return result;
}

// use this to view the contents of the table
function dumptable(t) {
	console.log("--------" + t.table.length);
	for (var i = 0; i < t.table.length; i++) {
		var e = t.table[i];
		if (typeof e != 'undefined') {
			console.log("[" + i + "]: " + e.key + "/" + e.value);
		}
	}
}

var hashtable = new Hashtable();
hashtable.put("IL", "Illinois");
hashtable.put("VA", "Virginia");
hashtable.put("CA", "California");

console.log("Reading IL, VA, and CA from the table:");
console.log("IL: " + hashtable.get("IL"));
console.log("VA: " + hashtable.get("VA"));
console.log("CA: " + hashtable.get("CA"));

console.log("Reading again, after removing VA:");
hashtable.delete("VA");
console.log("IL: " + hashtable.get("IL"));
console.log("VA: " + hashtable.get("VA"));
console.log("CA: " + hashtable.get("CA"));