Trying to create a hash table in JS... Can't figure out how to write a "get" function-CodePudding

So I have been able to create a set function that seems to work correctly. The problem comes when I try to create a 'get' function that searches the hashtable passed on a 'key' passed in as an argument.

The hashing function takes a 'string' and 'size' argument, not a 'key' like all the examples I looked at trying to figure it out. Here is the hashing function I was given...

  function hashCode(string, size){
    let hash = 0;
    if (string.length == 0) return hash;
    for (let i = 0; i < string.length; i  ) {
      const letter = string.charCodeAt(i);
      hash = ((hash << 5) - hash)   letter;
      hash = hash & hash; // Convert to 32bit integer
    }
    return Math.abs(hash) % size ;
  }

Here is my 'set' 'HashTable' class function andthe 'set' function I wrote...

function HashTable() {
    this.SIZE = 16;
    this.storage = new Array(this.SIZE);
  }
  
  // stores a value in the storage array
  HashTable.prototype.set = function(key, value) {
    let index = hashCode(value, 16);
    if (!this.storage[index]) {
      this.storage[index] = [];
    }
    this.storage[index][key] = value
  };

I have tried a few different methods to make the 'get' function work. I have tried iterating through the array and using the .hasOwnProperty method and currently tried to just use dot notation in a loop to find the property (what is shown below). I can't seem to get it to work with the methods I listed and can't think of any other ways to find the key/value pair in the array without being able to get an index from the hashing function.

Here is the 'get' method I am working on...

HashTable.prototype.get = function(key) {
    this.storage.forEach((kvpair) => {
        if (kvpair.key) {
            return kvpair.key
        }
    })
  };

when I create a new instance of the class like this...

 let table = new HashTable;

and run the 'set' function...

table.set('key','value');

and console.log 'table' I get this...

HashTable {SIZE: 16, storage: [ , [ key: 'value' ], , , , , , , , , , , , , , ] }

when I attempt to run my 'get' method...

table.get('key')

undefined is logged to the console...

I am just unsure of how to make this 'get' function work without the index... I am obviously not retrieving the value correctly with my loop and dot notation...

Any tips, tricks, ideas, hints, or help will be greatly appreciated!

CodePudding user response：

I slightly changed your get function:

HashTable.prototype.get = function(key) {    
    var value = null
    this.storage.forEach((kvpair) => {
            if (kvpair.key) {
              value = kvpair.key;
            }
        })
    return value;
    };

I have no idea why this works and your code does not...

If anyone can explain why, thank you.

CodePudding user response：

The problem is that your get method doesn't have a return statement. True, the callback that is passed to forEach has a return statement, but that defines the return value of the callback, not of the get method.

Moreover, returning a value inside a forEach callback is useless: that returned value is going nowhere. forEach does not do anything with it.

Instead I would suggest using find:

HashTable.prototype.get = function(key) {
    return this.storage.find(kvpair => kvpair.key)?.key;
};

This will also iterate over the key/value pairs, but find is designed to stop the iteration as soon as the callback returns a truthy value. Since you want key to be truthy, it is enough to return kvpair.key inside that callback. Then find will return the kvpair for which this key is truthy. It then remains to grab again the key property.

The ?. operator will make sure that if the key is not found, and find will return undefined, that no error will occur, but that undefined will be returned instead of accessing a property on undefined.