Skip to content

Commit 721cb40

Browse files
mgechevmgechev
committed
Merge pull request mgechev#74 from Jakehp/master
Implemented Hash table and spec.
2 parents fa8b1e1 + c75e494 commit 721cb40

File tree

2 files changed

+342
-0
lines changed

2 files changed

+342
-0
lines changed

‎src/data-structures/hash-table.js

Lines changed: 213 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,213 @@
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+
exports.Node = function (key, data) {
30+
this.key = key;
31+
this.data = data;
32+
this.next = undefined;
33+
this.prev = undefined;
34+
};
35+
36+
exports.Hashtable = function () {
37+
this.buckets = [];
38+
// The higher the bucket count; less likely for collisions.
39+
this.maxBucketCount = 100;
40+
};
41+
42+
/*
43+
Using simple non-crypto x->integer based hash.
44+
*/
45+
exports.Hashtable.prototype.hashCode = function (val) {
46+
var i;
47+
var hashCode = 0;
48+
var character;
49+
50+
// If value to be hashed is already an integer, return it.
51+
if (val.length === 0 || val.length === undefined) {
52+
return val;
53+
}
54+
55+
for (i = 0; i < val.length; i += 1) {
56+
character = val.charCodeAt(i);
57+
/*jshint -W016 */
58+
hashCode = ((hashCode << 5) - hashCode) + character;
59+
hashCode = hashCode & hashCode;
60+
/*jshint -W016 */
61+
}
62+
63+
return hashCode;
64+
};
65+
66+
exports.Hashtable.prototype.put = function (key, data, hashCode) {
67+
/*
68+
Make collision testing easy with optional hashCode parameter.
69+
That should not be used! Only by spec/tests.
70+
*/
71+
if (hashCode === undefined) {
72+
// Typical use
73+
hashCode = this.hashCode(key);
74+
} else if (hashCode.length > 0) {
75+
// Testing/Spec - String hash passed, convert to int based hash.
76+
hashCode = this.hashCode(hashCode);
77+
}
78+
// Adjust hash to fit within buckets.
79+
hashCode = hashCode % this.maxBucketCount;
80+
81+
var newNode = new exports.Node(key, data);
82+
83+
// No element exists at hash/index for given key -> put in table.
84+
if (this.buckets[hashCode] === undefined) {
85+
this.buckets[hashCode] = newNode;
86+
return;
87+
}
88+
89+
// Element exists at hash/index for given key, but, same key -> overwrite.
90+
if (this.buckets[hashCode].key === key) {
91+
this.buckets[hashCode].data = data;
92+
return;
93+
}
94+
95+
/*
96+
Item exists at hash/index for key, but different key.
97+
Handle collision.
98+
*/
99+
var first = this.buckets[hashCode];
100+
while (first.next !== undefined) {
101+
first = first.next;
102+
}
103+
first.next = newNode;
104+
newNode.prev = first;
105+
};
106+
107+
exports.Hashtable.prototype.get = function (key, hashCode) {
108+
/*
109+
Make collision testing easy with optional hashCode parameter.
110+
That should not be used! Only by spec/tests.
111+
*/
112+
if (hashCode === undefined) {
113+
// Typical use
114+
hashCode = this.hashCode(key);
115+
} else if (hashCode.length > 0) {
116+
// Testing/Spec - String hash passed, convert to int based hash.
117+
hashCode = this.hashCode(hashCode);
118+
}
119+
hashCode = hashCode % this.maxBucketCount;
120+
121+
if (this.buckets[hashCode] === undefined) {
122+
return undefined;
123+
} else if (
124+
this.buckets[hashCode].next === undefined &&
125+
this.buckets[hashCode].key === key
126+
) {
127+
return this.buckets[hashCode].data;
128+
} else {
129+
var first = this.buckets[hashCode];
130+
while (
131+
first !== undefined &&
132+
first.next !== undefined &&
133+
first.key !== key
134+
) {
135+
first = first.next;
136+
}
137+
138+
if (first.key === key) {
139+
return first.data;
140+
} else {
141+
return undefined;
142+
}
143+
}
144+
};
145+
146+
exports.Hashtable.prototype.remove = function (key, hashCode) {
147+
/*
148+
Make collision testing easy with optional hashCode parameter.
149+
That should not be used! Only by spec/tests.
150+
*/
151+
if (hashCode === undefined) {
152+
// Typical use
153+
hashCode = this.hashCode(key);
154+
} else if (hashCode.length > 0) {
155+
// Testing/Spec - String hash passed, convert to int based hash.
156+
hashCode = this.hashCode(hashCode);
157+
}
158+
hashCode = hashCode % this.maxBucketCount;
159+
160+
if (this.buckets[hashCode] === undefined) {
161+
return undefined;
162+
} else if (this.buckets[hashCode].next === undefined) {
163+
this.buckets[hashCode] = undefined;
164+
} else {
165+
var first = this.buckets[hashCode];
166+
167+
while (
168+
first !== undefined &&
169+
first.next !== undefined &&
170+
first.key !== key
171+
) {
172+
first = first.next;
173+
}
174+
175+
var removedValue = first.data;
176+
177+
// Removing (B)
178+
// (B) : only item in bucket
179+
if (first.prev === undefined && first.next === undefined) {
180+
first = undefined;
181+
return removedValue;
182+
}
183+
184+
// (B) - A - C: start link in bucket
185+
if (first.prev === undefined && first.next !== undefined) {
186+
first.data = first.next.data;
187+
first.key = first.next.key;
188+
if (first.next.next !== undefined) {
189+
first.next = first.next.next;
190+
} else {
191+
first.next = undefined;
192+
}
193+
return removedValue;
194+
}
195+
196+
// A - (B) : end link in bucket
197+
if (first.prev !== undefined && first.next === undefined) {
198+
first.prev.next = undefined;
199+
first = undefined;
200+
return removedValue;
201+
}
202+
203+
// A - (B) - C : middle link in bucket
204+
if (first.prev !== undefined && first.next !== undefined) {
205+
first.prev.next = first.next;
206+
first.next.prev = first.prev;
207+
first = undefined;
208+
return removedValue;
209+
}
210+
211+
}
212+
};
213+
})(typeof window === 'undefined' ? module.exports : window);

‎test/data-structures/hash-table.spec.js

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
'use strict';
2+
3+
var mod = require('../../src/data-structures/hash-table.js');
4+
var Node = mod.Node;
5+
var Hashtable = mod.Hashtable;
6+
7+
describe('Node', function () {
8+
it('should be a constructor function', function () {
9+
expect(typeof Node).toBe('function');
10+
});
11+
});
12+
13+
describe('Hash table', function () {
14+
it('should be a constructor function.', function () {
15+
expect(typeof Hashtable).toBe('function');
16+
});
17+
it('should start with empty table.', function () {
18+
expect(new Hashtable().buckets.length).toBe(0);
19+
});
20+
it('should put() K(int):V in table properly.', function () {
21+
var hashTable = new Hashtable();
22+
hashTable.put(10, 'value');
23+
expect(hashTable.buckets[10].data).toBe('value');
24+
});
25+
it('should put() K(str):V in table properly.', function () {
26+
var hashTable = new Hashtable();
27+
hashTable.put('key', 'value');
28+
/*
29+
'key' hashCode()'s to 106079. Then the hash is adjusted to fit
30+
the number of configurable buckets (array size).
31+
106079 % 100 (100 is default maxBucketCount)
32+
result is 79.
33+
This is done to avoid using get() since it's untested at this point.
34+
*/
35+
expect(hashTable.buckets[79].data).toBe('value');
36+
});
37+
it('should put() multiple K(int):Vs with hash collisions in properly (1).', function () {
38+
var hashTable = new Hashtable();
39+
// Same hash so going to same bucket, but different keys. Collision.
40+
hashTable.put(10, 'value', 'someHash');
41+
hashTable.put(35, 'anotherValue', 'someHash');
42+
/*
43+
'someHash' hashCode()'s to 1504481314. Then the hash is adjusted to fit
44+
the number of configurable buckets (array size).
45+
1504481314 % 100 (100 is default maxBucketCount)
46+
result is 14.
47+
This is done to avoid using get() since it's untested at this point.
48+
*/
49+
expect(hashTable.buckets[14].data).toBe('value');
50+
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
51+
});
52+
it('should put() multiple K:Vs with hash collisions in properly (2).', function () {
53+
var hashTable = new Hashtable();
54+
hashTable.put(10, 'value', 'someHash');
55+
hashTable.put(35, 'anotherValue', 'someHash');
56+
hashTable.put(77, 'lastValue', 'someHash');
57+
expect(hashTable.buckets[14].data).toBe('value');
58+
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
59+
expect(hashTable.buckets[14].next.next.data).toBe('lastValue');
60+
});
61+
it('should get() a k:v from table properly.', function () {
62+
var hashTable = new Hashtable();
63+
hashTable.put(10, 'value');
64+
expect(hashTable.get(10)).toBe('value');
65+
});
66+
it('should get() a k:v with collisions from table properly (1).', function () {
67+
var hashTable = new Hashtable();
68+
hashTable.put(10, 'value', 'someHash');
69+
hashTable.put(35, 'anotherValue', 'someHash');
70+
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
71+
});
72+
it('should get() a k:v with collisions from table properly (2).', function () {
73+
var hashTable = new Hashtable();
74+
hashTable.put(10, 'value', 'someHash');
75+
hashTable.put(35, 'anotherValue', 'someHash');
76+
hashTable.put(77, 'lastValue', 'someHash');
77+
expect(hashTable.get(77, 'someHash')).toBe('lastValue');
78+
});
79+
it('should get() a k:v with collisions from table properly (3).', function () {
80+
var hashTable = new Hashtable();
81+
hashTable.put(10, 'value', 'someHash');
82+
hashTable.put(35, 'anotherValue', 'someHash');
83+
hashTable.put(77, 'lastValue', 'someHash');
84+
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
85+
});
86+
it('should get() a k:v with collisions from table properly (4).', function () {
87+
var hashTable = new Hashtable();
88+
hashTable.put(10, 'value', 'someHash');
89+
hashTable.put(35, 'anotherValue', 'someHash');
90+
hashTable.put(77, 'lastValue', 'someHash');
91+
expect(hashTable.get(10, 'someHash')).toBe('value');
92+
});
93+
it('should remove() a k:v from table properly.', function () {
94+
// remove only node/link in bucket : (B)
95+
var hashTable = new Hashtable();
96+
hashTable.put(10, 'value');
97+
hashTable.remove(10);
98+
expect(hashTable.get(10)).toBe(undefined);
99+
});
100+
it('should remove() a k:v with collisions from table properly (2).', function () {
101+
// remove start node/link in bucket : (B) - A
102+
var hashTable = new Hashtable();
103+
hashTable.put(10, 'value', 'someHash');
104+
hashTable.put(35, 'anotherValue', 'someHash');
105+
expect(hashTable.remove(10, 'someHash')).toBe('value');
106+
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
107+
expect(hashTable.get(10, 'someHash')).toBe(undefined);
108+
});
109+
it('should remove() a k:v with collisions from table properly (3).', function () {
110+
// remove start node/link in bucket : (B) - A - C
111+
var hashTable = new Hashtable();
112+
hashTable.put(10, 'value', 'someHash');
113+
hashTable.put(35, 'anotherValue', 'someHash');
114+
hashTable.put(66, 'lastValue', 'someHash');
115+
expect(hashTable.remove(10, 'someHash')).toBe('value');
116+
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
117+
expect(hashTable.get(66, 'someHash')).toBe('lastValue');
118+
});
119+
it('should remove() a k:v with collisions from table properly (4).', function () {
120+
// remove middle node/link in bucket : A - (B) - C
121+
var hashTable = new Hashtable();
122+
hashTable.put(10, 'value', 'someHash');
123+
hashTable.put(35, 'anotherValue', 'someHash');
124+
hashTable.put(66, 'lastValue', 'someHash');
125+
expect(hashTable.remove(35, 'someHash')).toBe('anotherValue');
126+
expect(hashTable.get(10, 'someHash')).toBe('value');
127+
expect(hashTable.get(66, 'someHash')).toBe('lastValue');
128+
});
129+
});

0 commit comments

Comments
 (0)