Challenge: Create a Hash Table

Tell us what’s happening:
Describe your issue in detail here.

I reviewed the similar topics, and found nothing useful. The only tests I’m failing are the “The remove method should only remove the correct key value pair.” test and the “The hash table should handle collisions.”

In my opinion I am handling both of these, just not as the author of this problem probably intended. My approach is probably less slick, but it still gets the job done and I don’t really want to implement the provided solution in the Guide when I think that mine should be considered a pass. Can anyone explain to me why my code shouldn’t pass the two tests I’ve mentioned?

  **Your code so far**

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 = {};
// Only change code below this line
this.add = (key, value) => {
  if(this.collection[hash(key)] === undefined)
    this.collection[hash(key)] = value;
  else{
    let newKey = hash(key)+this.salt
    while(this.collection[newKey] !== undefined) newKey += this.salt;
    this.collection[newKey] = value;
  }
    
}
this.remove = (key) => {
  let newKey = hash(key)
  while(this.collection[newKey] !== undefined) newKey += this.salt;
  newKey -= this.salt
  if(this.collection[newKey] !== undefined) delete this.collection[newKey];
}
this.lookup = (key) => {
  let newKey = hash(key)
  while(this.collection[newKey] === undefined) newKey += this.salt;
  return this.collection[newKey]
}
this.salt = 13;
// Only change code above this line
};

let htbl = new HashTable();
htbl.add("key",1);
htbl.add("key",2);
htbl.add("key",3);
htbl.add("key",4);
htbl.add("key",5);
  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.45 Safari/537.36

Challenge: Create a Hash Table

Link to the challenge:

Your code fails to provide the correct behavior. Straight from the source of the test you are failing:

let test = new HashTable();

test.add('key', 'value');
test.add('yek', 'value');
test.add('altKey', 'value');

test.remove('yek');

console.log(test.lookup('key'));
console.log(test.lookup('yek'));
console.log(test.lookup('altKey'));

and

let test = new HashTable();

test.add('key1', 'value1');
test.add('1key', 'value2');
test.add('ke1y', 'value3');

console.log(test.lookup('key1'));
console.log(test.lookup('1key'));
console.log(test.lookup('ke1y'));
1 Like

You don’t code with an “opinion” you code with facts - meaning test cases :wink:

So create some test cases, think about what they SHOULD do and then see if they actually do that.
Your tests so far include a couple of .add(). I don’t see a .remove() and I don’t see any line of code that checks how you handle collisions.

2 Likes

I have 5 adds that use the same key, that’s a collision…
I was testing remove before. It’s impossible to determine what the “correct” one should be when you’re providing just a key… the whole point of handling collisions means that multiple entries have the same key, so it would be impossible to determine a single entry by key alone, but that’s what the criteria for the remove is, a key.

That is objectively false. The purpose of a hash table is to correctly find the stored value based upon the hash of the key.

1 Like

If you are hired to write some code, you cannot go to the customer and be like “Here is your code, also I made it so certain behavior is impossible to predict” :wink:

You want to find values, based on their key. People will NEVER search a value based on it’s key-value because that’s just completly pointless. So you gotta think how to resolve this. Spoiler: as it’s an introduction to hash-tables, I assume you resolve it by overriding (instead of researching open/closed adressing resolution for collisions). [Edit: the text tells you how to deal with the collisions]

And if the tests complaint about “remove” not working, it would be helpful if you included your test to show us, that it’s actually working right now.

1 Like

given the parameters of the problem, I suppose I was more frustrated that I couldn’t just adjust the hash, which seemed like the easiest way to ensure avoidance of collisions. My test cases were impractical for hash tables overall, and as such were providing me a false sense of correct functionality.

Thank you for your help.

I suppose I was more frustrated that I couldn’t just adjust the hash, which seemed like the easiest way to ensure avoidance of collisions. My test cases were impractical for hash tables overall, and as such were providing me a false sense of correct functionality.

Thank you for your help.

There exists no hash that perfectly avoids collisions. If you are hashing, then there will be collisions.

yeah, you’re right. I suppose I was just frustrated in general. I thought that I had a good idea and it didn’t work the way I expected, and so I found a means to prevent this particular hash from colliding for my specific test cases. I realize now that appropriate response requires either a list/buckets at specific hash values and storing the key to ensure that you aren’t duplicating keys and to ensure you remove the appropriate value when a specific key is entered.

Hashes must collide. They take a large range of values and map them to a smaller range of values. Mathematically that means collisions must occur.

I think people mix up hashing with uses of hashing, which makes this harder.

The only time you really need a salt is hashing for information hiding, such as hiding the true value of a stored password. In this case, collisions are fine, so long as it is nearly impossible to recover the original data from the hashed value.

For creating lookup tables, hashing just provides you with a way to map arbitrarily long keys to finite sized lookup tables. For that, collisions are bound to happen, but they are OK because everyone knows the key values so there is no problem storing a copy of the key value in the clear.

Hashing producing collisions with cryptographic signatures is problematic, but in those cases it is so difficult to create another value that intentionally collies with a given value, so we don’t worry too much (Unless there is a flaw in the hash function that makes that no longer true).

2 Likes