Custom Hashable implementation in Javascript

Question

I am fairly ~~stupid~~ new to programming. I want to implement a simple hashtable in javascript (for educational purposes). Everything works correctly, except when I try to overwrite some value it holds the previous value. For example when I try hashTable.set(cherry, 100), then hashTable.set(cherry, 4) and then hashTable.get(cherry) gives me 100 instead of 4. I've tried going over it with debugger, but turns out debugger doesn't help if you are fairly ~~stupid~~ new to programming. Heres the code:

    class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  set(key, value) {
    const address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    if (Array.isArray(this.data[address])) {
      for (let arr of this.data[address].values()) {
        if (arr[0] === key) {
          const arr1 = arr[1];
          arr[1] === value;
          return;
        }
      }
    }
    this.data[address].push([key, value]);
  }
  get(key) {
    const address = this._hash(key);
    const currentNode = this.data[address];
    if (currentNode) {
      for (let arr of currentNode) {
        if (arr[0] === key) {
          return arr[1];
        }
      }
    }
    return undefined;
  }
}

const myHashTable = new HashTable(2);
myHashTable.set("cherry", 100);
myHashTable.set("cherry", 4);
console.log(myHashTable.get("cherry")); // returns 100 instead of 4
myHashTable.set("peach", 9);
console.log(myHashTable.get("peach"));
myHashTable.set("apple", 2);
console.log(myHashTable.get("apple"));

The following two lines need some work: const arr1 = arr[1]; and arr[1] === value; — user3386109
– user3386109, Commented Nov 20, 2021 at 8:22
@user3386109 const arr1 = arr[1] was just for debugging purposes. I just wanted to see the value of arr[1] in the debugger. But damn it. I wrote x = y instead of x === y in if statements for my whole life, but never vice versa. Now I have officially made the stupidest possible mistake in programming. Thanks for noticing)) — Hayk
– Hayk, Commented Nov 20, 2021 at 9:08
Funny how the mind works. You see what you meant to write, anybody else sees what you actually wrote. So sometimes you just need an extra set of eyes on the code. Cheers! — user3386109
– user3386109, Commented Nov 20, 2021 at 19:13

user1984 · Accepted Answer · 2021-11-20 08:32:56Z

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  set(key, value) {
    const address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }

    for (let el of this.data[address]) {
      if (el[0] === key) {
        el[1] = value;
        return;
      }
    }
    this.data[address].push([key, value]);
  }
  get(key) {
    const address = this._hash(key);
    const currentNode = this.data[address];
    if (currentNode) {
      for (let arr of currentNode) {
        if (arr[0] === key) {
          return arr[1];
        }
      }
    }
    return undefined;
  }
}

const myHashTable = new HashTable(2);
myHashTable.set("cherry", 100);
myHashTable.set("cherry", 4);
console.log(myHashTable.get("cherry")); // returns 100 instead of 4
myHashTable.set("peach", 9);
console.log(myHashTable.get("peach"));
myHashTable.set("apple", 2);
console.log(myHashTable.get("apple"));

You were doing some funky stuff in the set function. That's what I changed. Now, it looks through the elements of this.data at address and checks the first element to make sure the key is not the same. If so, it just updates the value and returns early. I think that was what you had in mind.

To make this a better solution, I suggest you add a capacity to the underlying array and when the density reaches some percentage, you grow the underlaying array to reduce hash collisions.

Collectives™ on Stack Overflow

Custom Hashable implementation in Javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related