data-structures/hash-table.js

  1. /**
  2. * Hash Table
  3. *
  4. * An associative array, that can map keys
  5. * (strings and numbers) to values in O(1).
  6. *
  7. * @example
  8. * var hash = require('path-to-algorithms/src/data-structures'+
  9. * '/hash-table');
  10. * var hashTable = new hash.Hashtable();
  11. *
  12. * hashTable.put(10, 'value');
  13. * hashTable.put('key', 10);
  14. *
  15. * console.log(hashTable.get(10)); // 'value'
  16. * console.log(hashTable.get('key')); // 10
  17. *
  18. * hashTable.remove(10);
  19. * hashTable.remove('key');
  20. *
  21. * console.log(hashTable.get(10)); // undefined
  22. * console.log(hashTable.get('key')); // undefined
  23. *
  24. * @module data-structures/hash-table
  25. */
  26. (function (exports) {
  27. 'use strict';
  28. /**
  29. * Constructs a Node to store data and next/prev nodes in Hash table.
  30. *
  31. * @public
  32. * @constructor
  33. * @param {Number|String} key Key of the node.
  34. * @param {Number|String} data Data to be stored in hash table.
  35. */
  36. exports.Node = function (key, data) {
  37. this.key = key;
  38. this.data = data;
  39. this.next = undefined;
  40. this.prev = undefined;
  41. };
  42. /**
  43. * Construct a Hash table..
  44. *
  45. * @public
  46. * @constructor
  47. */
  48. exports.Hashtable = function () {
  49. this.buckets = [];
  50. // The higher the bucket count; less likely for collisions.
  51. this.maxBucketCount = 100;
  52. };
  53. /**
  54. * Simple non-crypto hash used to hash keys, which determines
  55. * while bucket the value will be placed in.
  56. * A javascript implementation of Java's 32bitint hash.
  57. *
  58. * @public
  59. * @method
  60. * @param {Number|String} val Key to be hashed.
  61. */
  62. exports.Hashtable.prototype.hashCode = function (val) {
  63. var i;
  64. var hashCode = 0;
  65. var character;
  66. // If value to be hashed is already an integer, return it.
  67. if (val.length === 0 || val.length === undefined) {
  68. return val;
  69. }
  70. for (i = 0; i < val.length; i += 1) {
  71. character = val.charCodeAt(i);
  72. /*jshint -W016 */
  73. hashCode = ((hashCode << 5) - hashCode) + character;
  74. hashCode = hashCode & hashCode;
  75. /*jshint -W016 */
  76. }
  77. return hashCode;
  78. };
  79. /**
  80. * Puts data into the table based on hashed key value.
  81. *
  82. * @public
  83. * @method
  84. * @param {Number|String} key Key for data.
  85. * @param {Number|String} data Data to be stored in table.
  86. */
  87. exports.Hashtable.prototype.put = function (key, data, hashCode) {
  88. /*
  89. Make collision testing easy with optional hashCode parameter.
  90. That should not be used! Only by spec/tests.
  91. */
  92. if (hashCode === undefined) {
  93. // Typical use
  94. hashCode = this.hashCode(key);
  95. } else if (hashCode.length > 0) {
  96. // Testing/Spec - String hash passed, convert to int based hash.
  97. hashCode = this.hashCode(hashCode);
  98. }
  99. // Adjust hash to fit within buckets.
  100. hashCode = hashCode % this.maxBucketCount;
  101. var newNode = new exports.Node(key, data);
  102. // No element exists at hash/index for given key -> put in table.
  103. if (this.buckets[hashCode] === undefined) {
  104. this.buckets[hashCode] = newNode;
  105. return;
  106. }
  107. // Element exists at hash/index for given key, but, same key -> overwrite.
  108. if (this.buckets[hashCode].key === key) {
  109. this.buckets[hashCode].data = data;
  110. return;
  111. }
  112. /*
  113. Item exists at hash/index for key, but different key.
  114. Handle collision.
  115. */
  116. var first = this.buckets[hashCode];
  117. while (first.next !== undefined) {
  118. first = first.next;
  119. }
  120. first.next = newNode;
  121. newNode.prev = first;
  122. };
  123. /**
  124. * Get's data from the table based on key.
  125. *
  126. * @public
  127. * @method
  128. * @param {Number|String} key Key for data to be retrieved.
  129. */
  130. exports.Hashtable.prototype.get = function (key, hashCode) {
  131. /*
  132. Make collision testing easy with optional hashCode parameter.
  133. That should not be used! Only by spec/tests.
  134. */
  135. if (hashCode === undefined) {
  136. // Typical use
  137. hashCode = this.hashCode(key);
  138. } else if (hashCode.length > 0) {
  139. // Testing/Spec - String hash passed, convert to int based hash.
  140. hashCode = this.hashCode(hashCode);
  141. }
  142. hashCode = hashCode % this.maxBucketCount;
  143. if (this.buckets[hashCode] === undefined) {
  144. return undefined;
  145. } else if (
  146. this.buckets[hashCode].next === undefined &&
  147. this.buckets[hashCode].key === key
  148. ) {
  149. return this.buckets[hashCode].data;
  150. } else {
  151. var first = this.buckets[hashCode];
  152. while (
  153. first !== undefined &&
  154. first.next !== undefined &&
  155. first.key !== key
  156. ) {
  157. first = first.next;
  158. }
  159. if (first.key === key) {
  160. return first.data;
  161. } else {
  162. return undefined;
  163. }
  164. }
  165. };
  166. /**
  167. * Removes data from the table based on key.
  168. *
  169. * @public
  170. * @method
  171. * @param {Number|String} key Key of the data to be removed.
  172. */
  173. exports.Hashtable.prototype.remove = function (key, hashCode) {
  174. /*
  175. Make collision testing easy with optional hashCode parameter.
  176. That should not be used! Only by spec/tests.
  177. */
  178. if (hashCode === undefined) {
  179. // Typical use
  180. hashCode = this.hashCode(key);
  181. } else if (hashCode.length > 0) {
  182. // Testing/Spec - String hash passed, convert to int based hash.
  183. hashCode = this.hashCode(hashCode);
  184. }
  185. hashCode = hashCode % this.maxBucketCount;
  186. if (this.buckets[hashCode] === undefined) {
  187. return undefined;
  188. } else if (this.buckets[hashCode].next === undefined) {
  189. this.buckets[hashCode] = undefined;
  190. } else {
  191. var first = this.buckets[hashCode];
  192. while (
  193. first !== undefined &&
  194. first.next !== undefined &&
  195. first.key !== key
  196. ) {
  197. first = first.next;
  198. }
  199. var removedValue = first.data;
  200. // Removing (B)
  201. // (B) : only item in bucket
  202. if (first.prev === undefined && first.next === undefined) {
  203. first = undefined;
  204. return removedValue;
  205. }
  206. // (B) - A - C: start link in bucket
  207. if (first.prev === undefined && first.next !== undefined) {
  208. first.data = first.next.data;
  209. first.key = first.next.key;
  210. if (first.next.next !== undefined) {
  211. first.next = first.next.next;
  212. } else {
  213. first.next = undefined;
  214. }
  215. return removedValue;
  216. }
  217. // A - (B) : end link in bucket
  218. if (first.prev !== undefined && first.next === undefined) {
  219. first.prev.next = undefined;
  220. first = undefined;
  221. return removedValue;
  222. }
  223. // A - (B) - C : middle link in bucket
  224. if (first.prev !== undefined && first.next !== undefined) {
  225. first.prev.next = first.next;
  226. first.next.prev = first.prev;
  227. first = undefined;
  228. return removedValue;
  229. }
  230. }
  231. };
  232. })(typeof window === 'undefined' ? module.exports : window);