Created
May 5, 2018 00:24
-
-
Save 4db/3a312b4fe2196abdeee529b3be732a82 to your computer and use it in GitHub Desktop.
openaddressing
This file contains hidden or 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() { | |
| var vm = this; | |
| vm._bucketSize = 10; | |
| vm._buckets = []; | |
| vm._buckets.length = vm._bucketSize; | |
| vm.hashCode = function(str) { | |
| var hash = 0, i, chr; | |
| if (str.length === 0) return hash; | |
| for (i = 0; i < str.length; i++) { | |
| chr = str.charCodeAt(i); | |
| hash = ((hash << 5) - hash) + chr; | |
| hash |= 0; // Convert to 32bit integer | |
| } | |
| return hash % vm._bucketSize | |
| }; | |
| vm.get = function(key) { | |
| var hash = vm.hashCode(key); | |
| if (!vm._buckets[hash]) { | |
| return undefined; | |
| } | |
| if (vm._buckets[hash].hasOwnProperty(key)) { | |
| return vm._buckets[hash][key]; | |
| } | |
| var bucketId = hash + 1; | |
| while (bucketId != hash) { | |
| if (bucketId >= vm._bucketSize) { | |
| bucketId = 0; | |
| } | |
| if (vm._buckets[bucketId] === undefined) { | |
| return undefined; | |
| } | |
| if (vm._buckets[bucketId].hasOwnProperty(key)) { | |
| return vm._buckets[hash][key]; | |
| } | |
| bucketId++; | |
| }; | |
| return undefined; | |
| }; | |
| vm.put = function(key, value) { | |
| var hash = vm.hashCode(key); | |
| if (!vm._buckets[hash]) { | |
| vm._buckets[hash] = {}; | |
| vm._buckets[hash][key] = value; | |
| return; | |
| } | |
| if (vm._buckets[hash].hasOwnProperty(key)) { | |
| throw 'Duplicate not allowed'; | |
| } | |
| var bucketId = hash + 1; | |
| while (bucketId !== hash) { | |
| if (bucketId >= vm._bucketSize) { | |
| bucketId = 0; | |
| } | |
| if (!vm._buckets[bucketId]) { | |
| vm._buckets[bucketId] = {}; | |
| vm._buckets[bucketId][key] = value; | |
| return; | |
| } | |
| bucketId++; | |
| } | |
| throw 'HashTable is full, a rehash is needed'; | |
| }; | |
| } | |
| var hashTableObj = new HashTable(); | |
| for (var i = 0; i < 100; i++) { | |
| hashTableObj.put(`element${i}`, i); | |
| } | |
| console.log(hashTableObj); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Open Addressing vs. Chaining
Open Addressing: better cache performance (better memory usage, no pointers
needed)
Chaining: less sensitive to hash functions (OA requires extra care to avoid clustering)
and the load factor α (OA degrades past 70% or so and in any event cannot
support values larger than 1)