Skip to content

Instantly share code, notes, and snippets.

@JohnIrle

JohnIrle/HashTable.js

Last active August 15, 2020 21:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save JohnIrle/f40d8a983dd994da26e88e44c18036b4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save JohnIrle/f40d8a983dd994da26e88e44c18036b4 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. JohnIrle revised this gist Aug 15, 2020. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions HashTable.js
    View file
    Original file line number Diff line number Diff line change
    @@ -55,10 +55,10 @@ class HashTable {
    }

    const myTable = new HashTable();
    myTable.setItem("firstName", "bob");
    myTable.setItem("lastName", "lazar");
    myTable.setItem("age", 5);
    myTable.setItem("dob", "1/2/3");
    myTable.setItem("firstName", "John");
    myTable.setItem("lastName", "Irle");
    myTable.setItem("age", 30);
    myTable.setItem("dob", "08/15/2020");

    console.log(myTable.getItem("firstName"))
    console.log(myTable.getItem("lastName"))
  2. JohnIrle created this gist Aug 15, 2020.
    66 changes: 66 additions & 0 deletions HashTable.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,66 @@
    function hashStringToInt(s, tableSize) {
    let hash = 17;

    for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize
    }

    return hash;
    }

    class HashTable {
    table = new Array(3)
    numItems = 0;

    resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table.forEach(item => {
    if (item) {
    item.forEach(([key, value]) => {
    const idx = hashStringToInt(key, newTable.length);
    if (newTable[idx]) {
    newTable[idx].push([key, value]);
    } else {
    newTable[idx] = [[key, value]];
    }
    })
    }
    })
    this.table = newTable
    }

    setItem = (key, value) => {
    this.numItems++;
    const loadFactor = this.numItems/this.table.length;
    if (loadFactor > .8) {
    // resize
    this.resize();
    }
    const idx = hashStringToInt(key, this.table.length)
    if (this.table[idx]) {
    this.table[idx].push([key, value]);
    } else {
    this.table[idx] = [[key, value]];
    }
    }

    getItem = (key) => {
    const idx = hashStringToInt(key, this.table.length)
    if (!this.table[idx]) {
    return null;
    }

    return this.table[idx].find(x => x[0] === key)[1];
    }
    }

    const myTable = new HashTable();
    myTable.setItem("firstName", "bob");
    myTable.setItem("lastName", "lazar");
    myTable.setItem("age", 5);
    myTable.setItem("dob", "1/2/3");

    console.log(myTable.getItem("firstName"))
    console.log(myTable.getItem("lastName"))
    console.log(myTable.getItem("age"))
    console.log(myTable.getItem("dob"))