Skip to content

Instantly share code, notes, and snippets.

@yellowflash
Created May 16, 2018 15:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yellowflash/73d7cb04cfd8f04df13a61920c365a3c to your computer and use it in GitHub Desktop.
Save yellowflash/73d7cb04cfd8f04df13a61920c365a3c to your computer and use it in GitHub Desktop.
Hash map with linear probing
class Map {
constructor(loadfactor = 0.7) {
this.size = 0;
this.loadfactor = 0.7;
this.entries = new Array(1);
}
put(key, value) {
this.resizeIfNecessary();
for(var i = key.hashCode();; i++) {
const location = i % this.entries.length;
console.log(this.entries[location]);
if(!this.entries[location]) {
this.entries[location] = {key: key, value: value};
this.size++;
break;
} else if(this.entries[location].key === key) {
this.entries[location].value = value;
break;
}
}
}
get(key) {
const hash = key.hashCode()
for(var i = hash; i < (hash + this.entries.length); i++) {
const location = i % this.entries.length;
const entry = this.entries[location];
if(!entry) return null;
if(entry && entry.key === key) return entry.value;
}
}
resizeIfNecessary() {
if(this.entries.length * this.loadfactor > this.size) return;
const old = this.entries;
this.size = 0;
this.entries = new Array(old.length * 2);
for(var i = 0; i < old.length; i++) {
if(old[i]) this.put(old[i].key, old[i].value);
}
}
}
String.prototype.hashCode = () => 42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment