Hash table collision handling

I’m working on the Learn Data Structures \ Create a Hash table, and I’m getting all the checkmarks except “The hash table should handle collisions.” … what exactly is that supposed to look like? The directions say only that "One way to handle collisions is to just store both key-value pairs at that index. Then, upon lookup of either, you would have to iterate through the bucket of items to find the key you are looking for. " It looks like array is not what they’re looking for…

var called = 0;
var hash = string => {
  called++;
  var hashed = 0;
  for (var i = 0; i < string.length; i++) {
    hashed += string.charCodeAt(i);
  }
  return hashed;
};
var HashTable = function() {
  this.collection = {};
  // change code below this line
  this.add = (key, value) => {
    let k = hash(key)
//    console.log(key)
    if (this.collection[k]==undefined) {
      this.collection[k] = value
//      console.log(this.collection)
    } else {
      console.log("!")
      if (typeof this.collection[k] !== "object") {
        this.collection[k] = [(key, this.collection[k]), (key, value)]
      } else {
        console.log("~")
        this.collection[k] = [...this.collection[k], (key, value)]
      }
      console.log(this.collection)
    }
    return key
  }
  this.remove = (key) => {
    let k = hash(key)
    delete this.collection[k]
  }
  this.lookup = (key) => {
    let k = hash(key);
    if (this.collection.hasOwnProperty(k)){
      //console.log(this.collection[k])
      return this.collection[k]
    } else {
      return null
    }
  }
  // change code above this line
};

I’m not sure exactly what you’re trying to do with the (key, value) part of this line (and similar constructs elsewhere), but it does not create a tuple in javascript, if that was your intent.

You may want to log what you’re actually creating at collection[k] to better understand the behavior you’ve currently implemented. That should push you a tiny bit further toward a working solution.

By handling collisions, using the current has definition and a valid HashTable function, the following code:

var test = new HashTable()
test.add('key1', 'value1');
test.add('1key', 'value2');
test.add('ke1y', 'value3');
console.log(test.collection);

would produce the following collection object:

{
  '378': {
    'key1': 'value1',
    '1key': 'value2',
    'ke1y': 'value3'
  }
}
1 Like

I’m not sure, if you wrote hash function or it was pre-written, but it needs some improvements:

  1. You might want to have second argument as a size of your hash map - this would make it look more compact
  2. hashed += string.charCodeAt(i); - this is not good… as @RandellDawson pointed out, this would cause A LOT of collisions, try something like this:
const hash = (str, max) => {
  let hashed = 0;
  for (let i = 0; i < str.length; i++) {
    hashed = (hashed << 5) + hashed + str.charCodeAt(i);
  }
  return hashed % max;
}; 

And try to make your hash table size of prime number :wink: this would make it really good :+1:

console.log(hash('1key', 53)); // 26
console.log(hash('k1ey', 53)); // 2
console.log(hash('ke1y', 53)); // 6
console.log(hash('key1', 53)); // 31

@snigo The hash is already pre-defined (to cause collisions).

Make sense :+1: :+1: :+1: