Edit in JSFiddle

var idCounter = 0;
// First we need a function that will generate a unique string every time it's called
function uniqueId() {
  return (++idCounter).toString();
}

describe('uniqueId', function() {
  it('never gives the same value twice', function() {
    expect(function() { 
      return uniqueId() !== uniqueId()
    }).forAll();
  });
});
/* Then we need a function that can transform any js value into a string, such that:
1. Every time the same value is passed, the same value is returned
2. Different values have different strings
3. The same object returns the same value even after it is modified */
function hashKey(value) {
  var type = typeof value;
  var uid;
  if (type === 'object' && value !== null) {
    uid = value.$$hashKey;
    if (typeof uid === 'function') {
      uid = value.$$hashKey();
    } else if (uid === undefined) {
      uid = value.$$hashKey = uniqueId();
    }
  } else {
    uid = value;
  }
  return type + ':' + uid;
}

describe('hashKey', function() {
  it('can turn anything into a string', function() {
    expect(function(anything) { 
      return typeof hashKey(anything) === 'string';
    }).forAll(qc.any);
  });
  it('any object will produce the same hash key', function() {
    expect(function(anything) { 
      return hashKey(anything) === hashKey(anything);
    }).forAll(qc.any);
  });
  it('same object will have the same hash key even after modificatoin', function() {
    expect(function(obj, key, val) {
      var origKey = hashKey(obj);
      obj[key] = val;
      return hashKey(obj) === origKey;
    }).forAll(qc.object, qc.string, qc.any);
  });
});

// Finally we want a datastructure that can store values for keys,
// but we want the keys to be any datatype:
function HashMap() { }

HashMap.prototype = {
  put: function(key, value) {
    this[hashKey(key)] = value;
  },
  get: function(key) {
    return this[hashKey(key)];
  },
  remove: function(key) {
    key = hashKey(key);
    var value = this[key];
    delete this[key];
    return value;
  }
};

describe('HashMap', function() {
  it('a value stored can be retrieved', function() {
    expect(function(hm, key, val) {
      hm.put(key, val);
      return hm.get(key) === val;
    }).forAll(hashMaps, qc.any, qc.any);
  });
  it('a value stored can be deleted', function() {
    expect(function(hm, key, val) {
      hm.put(key, val);
      hm.remove(key);
      return hm.get(key) === undefined;
    }).forAll(hashMaps, qc.any, qc.any)
  });
  it('a delete returns original value', function() {
    expect(function(hm, key, val) {
      hm.put(key, val);
      return hm.remove(key) === val;
    }).forAll(hashMaps, qc.any, qc.any)
  });
});

function hashMaps(size) {
  var hm = new HashMap();
  for(var i = 0, l = qc.intUpto(size); i <= l; i++) {
    hm.put(qc.any(size), qc.any(size));
  }
  return hm;
};