Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcd7cff6

Browse files
committed
Update jsdocs
2 parentsaa1c214 +4c16915 commitcd7cff6

8 files changed

+1195
-4
lines changed

‎data-structures_hash-table.js.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -297,7 +297,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
297297
<brclass="clear">
298298

299299
<footer>
300-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onSat Aug 15 201518:19:41 GMT+0300 (EEST)
300+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.2</a> onWed Jul 15 201517:47:03 GMT-0500 (Central Daylight Time)
301301
</footer>
302302

303303
<script>prettyPrint();</script>
Lines changed: 310 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,310 @@
1+
<!DOCTYPE html>
2+
<htmllang="en">
3+
<head>
4+
<metacharset="utf-8">
5+
<title>JSDoc: Source: data-structures/hash-table.js</title>
6+
7+
<scriptsrc="scripts/prettify/prettify.js"></script>
8+
<scriptsrc="scripts/prettify/lang-css.js"></script>
9+
<!--[if lt IE 9]>
10+
<script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
11+
<![endif]-->
12+
<linktype="text/css"rel="stylesheet"href="styles/prettify-tomorrow.css">
13+
<linktype="text/css"rel="stylesheet"href="styles/jsdoc-default.css">
14+
</head>
15+
16+
<body>
17+
18+
<divid="main">
19+
20+
<h1class="page-title">Source: data-structures/hash-table.js</h1>
21+
22+
23+
24+
25+
26+
27+
<section>
28+
<article>
29+
<preclass="prettyprint source linenums"><code>/**
30+
* Hash Table
31+
*
32+
* An associative array, that can map keys
33+
* (strings and numbers) to values in O(1).
34+
*
35+
* @example
36+
* var hash = require('path-to-algorithms/src/data-structures'+
37+
* '/hash-table');
38+
* var hashTable = new hash.Hashtable();
39+
*
40+
* hashTable.put(10, 'value');
41+
* hashTable.put('key', 10);
42+
*
43+
* console.log(hashTable.get(10)); // 'value'
44+
* console.log(hashTable.get('key')); // 10
45+
*
46+
* hashTable.remove(10);
47+
* hashTable.remove('key');
48+
*
49+
* console.log(hashTable.get(10)); // undefined
50+
* console.log(hashTable.get('key')); // undefined
51+
*
52+
* @module data-structures/hash-table
53+
*/
54+
(function (exports) {
55+
'use strict';
56+
57+
/**
58+
* Constructs a Node to store data and next/prev nodes in Hash table.
59+
*
60+
* @public
61+
* @constructor
62+
* @param {Number|String} key Key of the node.
63+
* @param {Number|String} data Data to be stored in hash table.
64+
*/
65+
exports.Node = function (key, data) {
66+
this.key = key;
67+
this.data = data;
68+
this.next = undefined;
69+
this.prev = undefined;
70+
};
71+
72+
/**
73+
* Construct a Hash table..
74+
*
75+
* @public
76+
* @constructor
77+
*/
78+
exports.Hashtable = function () {
79+
this.buckets = [];
80+
// The higher the bucket count; less likely for collisions.
81+
this.maxBucketCount = 100;
82+
};
83+
84+
/**
85+
* Simple non-crypto hash used to hash keys, which determines
86+
* while bucket the value will be placed in.
87+
* A javascript implementation of Java's 32bitint hash.
88+
*
89+
* @public
90+
* @method
91+
* @param {Number|String} val Key to be hashed.
92+
*/
93+
exports.Hashtable.prototype.hashCode = function (val) {
94+
var i;
95+
var hashCode = 0;
96+
var character;
97+
98+
// If value to be hashed is already an integer, return it.
99+
if (val.length === 0 || val.length === undefined) {
100+
return val;
101+
}
102+
103+
for (i = 0; i &lt; val.length; i += 1) {
104+
character = val.charCodeAt(i);
105+
/*jshint -W016 */
106+
hashCode = ((hashCode &lt;&lt; 5) - hashCode) + character;
107+
hashCode = hashCode &amp; hashCode;
108+
/*jshint -W016 */
109+
}
110+
111+
return hashCode;
112+
};
113+
114+
/**
115+
* Puts data into the table based on hashed key value.
116+
*
117+
* @public
118+
* @method
119+
* @param {Number|String} key Key for data.
120+
* @param {Number|String} data Data to be stored in table.
121+
*/
122+
exports.Hashtable.prototype.put = function (key, data, hashCode) {
123+
/*
124+
Make collision testing easy with optional hashCode parameter.
125+
That should not be used! Only by spec/tests.
126+
*/
127+
if (hashCode === undefined) {
128+
// Typical use
129+
hashCode = this.hashCode(key);
130+
} else if (hashCode.length> 0) {
131+
// Testing/Spec - String hash passed, convert to int based hash.
132+
hashCode = this.hashCode(hashCode);
133+
}
134+
// Adjust hash to fit within buckets.
135+
hashCode = hashCode % this.maxBucketCount;
136+
137+
var newNode = new exports.Node(key, data);
138+
139+
// No element exists at hash/index for given key -> put in table.
140+
if (this.buckets[hashCode] === undefined) {
141+
this.buckets[hashCode] = newNode;
142+
return;
143+
}
144+
145+
// Element exists at hash/index for given key, but, same key -> overwrite.
146+
if (this.buckets[hashCode].key === key) {
147+
this.buckets[hashCode].data = data;
148+
return;
149+
}
150+
151+
/*
152+
Item exists at hash/index for key, but different key.
153+
Handle collision.
154+
*/
155+
var first = this.buckets[hashCode];
156+
while (first.next !== undefined) {
157+
first = first.next;
158+
}
159+
first.next = newNode;
160+
newNode.prev = first;
161+
};
162+
163+
/**
164+
* Get's data from the table based on key.
165+
*
166+
* @public
167+
* @method
168+
* @param {Number|String} key Key for data to be retrieved.
169+
*/
170+
exports.Hashtable.prototype.get = function (key, hashCode) {
171+
/*
172+
Make collision testing easy with optional hashCode parameter.
173+
That should not be used! Only by spec/tests.
174+
*/
175+
if (hashCode === undefined) {
176+
// Typical use
177+
hashCode = this.hashCode(key);
178+
} else if (hashCode.length> 0) {
179+
// Testing/Spec - String hash passed, convert to int based hash.
180+
hashCode = this.hashCode(hashCode);
181+
}
182+
hashCode = hashCode % this.maxBucketCount;
183+
184+
if (this.buckets[hashCode] === undefined) {
185+
return undefined;
186+
} else if (
187+
this.buckets[hashCode].next === undefined &amp;&amp;
188+
this.buckets[hashCode].key === key
189+
) {
190+
return this.buckets[hashCode].data;
191+
} else {
192+
var first = this.buckets[hashCode];
193+
while (
194+
first !== undefined &amp;&amp;
195+
first.next !== undefined &amp;&amp;
196+
first.key !== key
197+
) {
198+
first = first.next;
199+
}
200+
201+
if (first.key === key) {
202+
return first.data;
203+
} else {
204+
return undefined;
205+
}
206+
}
207+
};
208+
209+
/**
210+
* Removes data from the table based on key.
211+
*
212+
* @public
213+
* @method
214+
* @param {Number|String} key Key of the data to be removed.
215+
*/
216+
exports.Hashtable.prototype.remove = function (key, hashCode) {
217+
/*
218+
Make collision testing easy with optional hashCode parameter.
219+
That should not be used! Only by spec/tests.
220+
*/
221+
if (hashCode === undefined) {
222+
// Typical use
223+
hashCode = this.hashCode(key);
224+
} else if (hashCode.length> 0) {
225+
// Testing/Spec - String hash passed, convert to int based hash.
226+
hashCode = this.hashCode(hashCode);
227+
}
228+
hashCode = hashCode % this.maxBucketCount;
229+
230+
if (this.buckets[hashCode] === undefined) {
231+
return undefined;
232+
} else if (this.buckets[hashCode].next === undefined) {
233+
this.buckets[hashCode] = undefined;
234+
} else {
235+
var first = this.buckets[hashCode];
236+
237+
while (
238+
first !== undefined &amp;&amp;
239+
first.next !== undefined &amp;&amp;
240+
first.key !== key
241+
) {
242+
first = first.next;
243+
}
244+
245+
var removedValue = first.data;
246+
247+
// Removing (B)
248+
// (B) : only item in bucket
249+
if (first.prev === undefined &amp;&amp; first.next === undefined) {
250+
first = undefined;
251+
return removedValue;
252+
}
253+
254+
// (B) - A - C: start link in bucket
255+
if (first.prev === undefined &amp;&amp; first.next !== undefined) {
256+
first.data = first.next.data;
257+
first.key = first.next.key;
258+
if (first.next.next !== undefined) {
259+
first.next = first.next.next;
260+
} else {
261+
first.next = undefined;
262+
}
263+
return removedValue;
264+
}
265+
266+
// A - (B) : end link in bucket
267+
if (first.prev !== undefined &amp;&amp; first.next === undefined) {
268+
first.prev.next = undefined;
269+
first = undefined;
270+
return removedValue;
271+
}
272+
273+
// A - (B) - C : middle link in bucket
274+
if (first.prev !== undefined &amp;&amp; first.next !== undefined) {
275+
first.prev.next = first.next;
276+
first.next.prev = first.prev;
277+
first = undefined;
278+
return removedValue;
279+
}
280+
281+
}
282+
};
283+
})(typeof window === 'undefined' ? module.exports : window);
284+
</code></pre>
285+
</article>
286+
</section>
287+
288+
289+
290+
291+
</div>
292+
293+
<nav>
294+
<h2><ahref="index.html">Home</a></h2><h3>Modules</h3><ul><li><ahref="module-combinatorics_cartesianproduct.html">combinatorics/cartesianproduct</a></li><li><ahref="module-combinatorics_combinations.html">combinatorics/combinations</a></li><li><ahref="module-combinatorics_permutations.html">combinatorics/permutations</a></li><li><ahref="module-combinatorics_variations-repetition.html">combinatorics/variations-repetition</a></li><li><ahref="module-data-structures_avl-tree.html">data-structures/avl-tree</a></li><li><ahref="module-data-structures_binary-search-tree.html">data-structures/binary-search-tree</a></li><li><ahref="module-data-structures_edge.html">data-structures/edge</a></li><li><ahref="module-data-structures_hash-table.html">data-structures/hash-table</a></li><li><ahref="module-data-structures_heap.html">data-structures/heap</a></li><li><ahref="module-data-structures_interval-tree.html">data-structures/interval-tree</a></li><li><ahref="module-data-structures_linked-list.html">data-structures/linked-list</a></li><li><ahref="module-data-structures_red-black-tree.html">data-structures/red-black-tree</a></li><li><ahref="module-data-structures_splay-tree.html">data-structures/splay-tree</a></li><li><ahref="module-data-structures_vertex.html">data-structures/vertex</a></li><li><ahref="module-graphs_others_topological-sort.html">graphs/others/topological-sort</a></li><li><ahref="module-graphs_searching_bfs.html">graphs/searching/bfs</a></li><li><ahref="module-graphs_searching_dfs.html">graphs/searching/dfs</a></li><li><ahref="module-graphs_shortest-path_bellman-ford.html">graphs/shortest-path/bellman-ford</a></li><li><ahref="module-graphs_shortest-path_dijkstra.html">graphs/shortest-path/dijkstra</a></li><li><ahref="module-graphs_shortest-path_floyd-warshall.html">graphs/shortest-path/floyd-warshall</a></li><li><ahref="module-graphs_spanning-trees_prim.html">graphs/spanning-trees/prim</a></li><li><ahref="module-others_fibonacci.html">others/fibonacci</a></li><li><ahref="module-others_hanoi.html">others/hanoi</a></li><li><ahref="module-others_levenshtein-distance.html">others/levenshtein-distance</a></li><li><ahref="module-others_minCoinsChange.html">others/minCoinsChange</a></li><li><ahref="module-primes_is-prime.html">primes/is-prime</a></li><li><ahref="module-primes_prime-factor-tree.html">primes/prime-factor-tree</a></li><li><ahref="module-primes_sieve-of-eratosthenes.html">primes/sieve-of-eratosthenes</a></li><li><ahref="module-searching_binarysearch.html">searching/binarysearch</a></li><li><ahref="module-searching_knuth-morris-pratt.html">searching/knuth-morris-pratt</a></li><li><ahref="module-searching_longest-increasing-subsequence.html">searching/longest-increasing-subsequence</a></li><li><ahref="module-searching_maximum-subarray.html">searching/maximum-subarray</a></li><li><ahref="module-searching_maximum-subarray-divide-and-conquer.html">searching/maximum-subarray-divide-and-conquer</a></li><li><ahref="module-searching_quickselect.html">searching/quickselect</a></li><li><ahref="module-searching_recursive-binarysearch.html">searching/recursive-binarysearch</a></li><li><ahref="module-sets_quickfind.html">sets/quickfind</a></li><li><ahref="module-sets_quickunion.html">sets/quickunion</a></li><li><ahref="module-sets_weightquickunion.html">sets/weightquickunion</a></li><li><ahref="module-shuffle_fisheryates.html">shuffle/fisheryates</a></li><li><ahref="module-shuffle_richarddurstenfeld.html">shuffle/richarddurstenfeld</a></li><li><ahref="module-sorting_3-way-string-quicksort.html">sorting/3-way-string-quicksort</a></li><li><ahref="module-sorting_bubblesort.html">sorting/bubblesort</a></li><li><ahref="module-sorting_bucketsort.html">sorting/bucketsort</a></li><li><ahref="module-sorting_countingsort.html">sorting/countingsort</a></li><li><ahref="module-sorting_heapsort.html">sorting/heapsort</a></li><li><ahref="module-sorting_insertion-binary-sort.html">sorting/insertion-binary-sort</a></li><li><ahref="module-sorting_insertionsort.html">sorting/insertionsort</a></li><li><ahref="module-sorting_lsd.html">sorting/lsd</a></li><li><ahref="module-sorting_mergesort.html">sorting/mergesort</a></li><li><ahref="module-sorting_mergesort_merge.html">sorting/mergesort/merge</a></li><li><ahref="module-sorting_msd.html">sorting/msd</a></li><li><ahref="module-sorting_oddeven-sort.html">sorting/oddeven-sort</a></li><li><ahref="module-sorting_quicksort-middle.html">sorting/quicksort-middle</a></li><li><ahref="module-sorting_recursive-insertionsort.html">sorting/recursive-insertionsort</a></li><li><ahref="module-sorting_selectionsort.html">sorting/selectionsort</a></li><li><ahref="module-sorting_shellsort.html">sorting/shellsort</a></li></ul><h3>Classes</h3><ul><li><ahref="module-data-structures_avl-tree.AVLTree.html">AVLTree</a></li><li><ahref="module-data-structures_avl-tree.Node.html">Node</a></li><li><ahref="module-data-structures_binary-search-tree.BinaryTree.html">BinaryTree</a></li><li><ahref="module-data-structures_binary-search-tree.Node.html">Node</a></li><li><ahref="module-data-structures_hash-table.Hashtable.html">Hashtable</a></li><li><ahref="module-data-structures_hash-table.Node.html">Node</a></li><li><ahref="module-data-structures_heap.Heap.html">Heap</a></li><li><ahref="module-data-structures_interval-tree.IntervalTree.html">IntervalTree</a></li><li><ahref="module-data-structures_interval-tree.Node.html">Node</a></li><li><ahref="module-data-structures_linked-list.LinkedList.html">LinkedList</a></li><li><ahref="module-data-structures_linked-list.Node.html">Node</a></li><li><ahref="module-data-structures_red-black-tree.RBTree.html">RBTree</a></li><li><ahref="module-data-structures_splay-tree.Node.html">Node</a></li><li><ahref="module-data-structures_splay-tree.SplayTree.html">SplayTree</a></li><li><ahref="module-graphs_spanning-trees_prim.Graph.html">Graph</a></li><li><ahref="module-sets_quickfind.QuickFind.html">QuickFind</a></li><li><ahref="module-sets_quickunion.QuickUnion.html">QuickUnion</a></li><li><ahref="module-sets_weightquickunion.QuickUnion.html">QuickUnion</a></li></ul>
295+
</nav>
296+
297+
<brclass="clear">
298+
299+
<footer>
300+
<<<<<<<HEAD
301+
Documentationgeneratedby<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> on Sat Aug 15 2015 18:19:41 GMT+0300 (EEST)
302+
=======
303+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.2</a> on Wed Jul 15 2015 17:47:03 GMT-0500 (Central Daylight Time)
304+
>>>>>>> 4c16915f2e7ce2c7db8f12d6451a11226ad8d04a
305+
</footer>
306+
307+
<script>prettyPrint();</script>
308+
<scriptsrc="scripts/linenumber.js"></script>
309+
</body>
310+
</html>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp