-
-
Save ausarenglish/ef3d07c85f902277d266c2e32fc3222f to your computer and use it in GitHub Desktop.
Simple Hash Table implemented with separate chaining then open addressing collision strategy
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 HashTable() { | |
this._bucketSize = 23; | |
this._buckets = []; | |
this._buckets.length = this._bucketSize; | |
} | |
HashTable.prototype.computeHash = function (key) { | |
var total = 0; | |
for (var i = 0; i < key.length; i++) { | |
total += key.charCodeAt(i); | |
} | |
return total % this._bucketsSize; | |
}; |
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
HashTable.prototype.put = function (key, value) { | |
if (typeof(key) !== 'number' && typeof(key) !== 'string') { | |
throw 'Invalid key type'; | |
} | |
var hash = this.computeHash(key); | |
if (this._buckets[hash] === undefined) { | |
this._buckets[hash] = {}; | |
this._buckets[hash][key] = value; | |
return; | |
} else if (this._buckets[hash].hasOwnProperty(key)) { | |
throw 'Duplicate not allowed'; | |
} | |
var bucketId = hash + 1; | |
do { | |
if (bucketId >= this._bucketSize) { | |
bucketId = 0; | |
} | |
if (this._buckets[bucketId] === undefined) { | |
this._buckets[bucketId] = {}; | |
this._buckets[bucketId][key] = value; | |
return; | |
} | |
bucketId++; | |
} while (bucketId !== hash); | |
throw 'HashTable is full, a rehash is needed'; | |
}; | |
HashTable.prototype.get = function (key) { | |
if (typeof(key) !== 'number' && typeof(key) !== 'string') { | |
return undefined; | |
} | |
var hash = this.computeHash(key); | |
if (this._buckets[hash] === undefined) { | |
return undefined; | |
} else if (this._buckets[hash].hasOwnProperty(key)) { | |
return this._buckets[hash][key]; | |
} | |
var bucketId = hash + 1; | |
do { | |
if (bucketId >= this._bucketSize) { | |
bucketId = 0; | |
} | |
if (this._buckets[bucketId] === undefined) { | |
return undefined; | |
} else if (this._buckets[bucketId].hasOwnProperty(key)) { | |
return this._buckets[hash][key]; | |
} | |
bucketId++; | |
} while (bucketId != hash); | |
return undefined; | |
}; |
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
HashTable.prototype.put = function (key, value) { | |
if (typeof(key) !== 'number' && typeof(key) !== 'string') { | |
throw 'Invalid key type'; | |
} | |
var hash = this.computeHash(key); | |
if (this._buckets[hash] === undefined) { | |
this._buckets[hash] = {}; | |
} | |
var chain = this._buckets[hash]; | |
if (chain.hasOwnProperty(key)) { | |
throw 'Duplicates not allowed'; | |
} | |
chain[key] = value; | |
}; | |
HashTable.prototype.get = function (key) { | |
if (typeof(key) !== 'number' && typeof(key) !== 'string') { | |
return undefined; | |
} | |
var hash = this.computeHash(key); | |
if (this._buckets[hash] === undefined) { | |
return undefined; | |
} | |
var chain = this._buckets[hash]; | |
if (chain.hasOwnProperty(key)) { | |
return chain[key]; | |
} | |
return undefined; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment