Created
March 19, 2015 01:07
-
-
Save jstejada/a4ac71c4efbc6e411306 to your computer and use it in GitHub Desktop.
Hash Table in javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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