Skip to content

Instantly share code, notes, and snippets.

@jstejada
Created March 19, 2015 01:07
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jstejada/a4ac71c4efbc6e411306 to your computer and use it in GitHub Desktop.
Save jstejada/a4ac71c4efbc6e411306 to your computer and use it in GitHub Desktop.
Hash Table in javascript
function _hash(key, size) {
key = key.toString();
var hash = 5381;
for(var i in key){
var c = key[i];
hash = ((hash << 5) + hash) + c.charCodeAt(0); /* hash * 33 + c */
}
return hash % size;
}
function _loadFactor(elements, bucketsSize) {
return elements / (bucketsSize*1.0);
}
function _addEntry(idx, entry, buckets) {
if(buckets[idx] != null){
buckets[idx].push(entry);
} else {
buckets[idx] = [entry];
}
}
function _findEntryIn(bucket, key){
if(bucket != null) {
var found = null;
var idx = null;
bucket.some(function(entry, i){
if(entry.key == key){
found = entry;
idx = i;
return true;
}
});
return [found, idx];
}
return null;
}
function _rehash(ht, newBucketsSize){
var newBuckets = Array(newBucketsSize);
ht.buckets.forEach(function(bucket){
if(bucket != null){
bucket.forEach(function(entry){
var idx = _hash(entry.key, newBuckets.length);
_addEntry(idx, entry, newBuckets);
});
}
});
ht.buckets = newBuckets;
}
function BucketEntry(key, val) {
this.key = key;
this.val = val;
}
function HashTable(n) {
n = typeof n !== 'undefined' ? n*10 : 1000;
this.buckets = new Array(n);
this.size = 0;
}
HashTable.prototype.put = function(key, val){
var idx = _hash(key, this.buckets.length);
var entry = new BucketEntry(key, val);
_addEntry(idx, entry, this.buckets);
this.size++;
if(_loadFactor(this.size, this.buckets.length) > 0.75){
_rehash(this, this.buckets.length*2);
}
return val;
};
HashTable.prototype.get = function(key){
var idx = _hash(key, this.buckets.length);
var entry = _findEntryIn(this.buckets[idx], key)[0];
if(entry != null){
return entry.val;
}
return null;
};
HashTable.prototype.del = function(key){
var idx = _hash(key, this.buckets.length);
var bucket = this.buckets[idx];
var res = _findEntryIn(bucket, key);
var entry = res[0];
if(entry != null) {
var pos = res[1];
var removed = bucket.splice(pos, 1)[0].val;
this.size--;
if(_loadFactor(this.size, this.buckets.length) < 0.1){
_rehash(this, this.buckets.length/2);
}
return removed;
}
return false;
};
HashTable.prototype.contains = function(key){
var idx = _hash(key, this.buckets.length);
var entry = _findEntryIn(this.buckets[idx], key)[0];
if(entry != null){
return true;
}
return false;
};
module.exports = HashTable;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment