Skip to content

Commit 8309a58

Browse files
JakeHPJakeHP
committed
Merge pull request mgechev#79 from Jakehp/master
Added specs for string based keys.
2 parents 5a84957 + 90ff3f1 commit 8309a58

File tree

1 file changed

+103
-11
lines changed

1 file changed

+103
-11
lines changed

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

Lines changed: 103 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ describe('Hash table', function () {
2222
hashTable.put(10, 'value');
2323
expect(hashTable.buckets[10].data).toBe('value');
2424
});
25-
it('should put() K(str):V in table properly.', function () {
25+
it('should put() K(string):V in table properly.', function () {
2626
var hashTable = new Hashtable();
2727
hashTable.put('key', 'value');
2828
/*
@@ -49,7 +49,7 @@ describe('Hash table', function () {
4949
expect(hashTable.buckets[14].data).toBe('value');
5050
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
5151
});
52-
it('should put() multiple K:Vs with hash collisions in properly (2).', function () {
52+
it('should put() multiple K(int):Vs with hash collisions in properly (2).', function () {
5353
var hashTable = new Hashtable();
5454
hashTable.put(10, 'value', 'someHash');
5555
hashTable.put(35, 'anotherValue', 'someHash');
@@ -58,46 +58,102 @@ describe('Hash table', function () {
5858
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
5959
expect(hashTable.buckets[14].next.next.data).toBe('lastValue');
6060
});
61-
it('should get() a k:v from table properly.', function () {
61+
it('should put() multiple K(string):Vs with hash collisions in properly (1).', function () {
62+
var hashTable = new Hashtable();
63+
// Same hash so going to same bucket, but different keys. Collision.
64+
hashTable.put('keyA', 'value', 'someHash');
65+
hashTable.put('keyB', 'anotherValue', 'someHash');
66+
/*
67+
'someHash' hashCode()'s to 1504481314. Then the hash is adjusted to fit
68+
the number of configurable buckets (array size).
69+
1504481314 % 100 (100 is default maxBucketCount)
70+
result is 14.
71+
This is done to avoid using get() since it's untested at this point.
72+
*/
73+
expect(hashTable.buckets[14].data).toBe('value');
74+
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
75+
});
76+
it('should put() multiple K(string):Vs with hash collisions in properly (2).', function () {
77+
var hashTable = new Hashtable();
78+
hashTable.put('keyA', 'value', 'someHash');
79+
hashTable.put('keyB', 'anotherValue', 'someHash');
80+
hashTable.put('keyC', 'lastValue', 'someHash');
81+
expect(hashTable.buckets[14].data).toBe('value');
82+
expect(hashTable.buckets[14].next.data).toBe('anotherValue');
83+
expect(hashTable.buckets[14].next.next.data).toBe('lastValue');
84+
});
85+
it('should get() a K(int):V from table properly.', function () {
6286
var hashTable = new Hashtable();
6387
hashTable.put(10, 'value');
6488
expect(hashTable.get(10)).toBe('value');
6589
});
66-
it('should get() a k:v with collisions from table properly (1).', function () {
90+
it('should get() a K(string):V from table properly.', function () {
91+
var hashTable = new Hashtable();
92+
hashTable.put('keyA', 'value');
93+
expect(hashTable.get('keyA')).toBe('value');
94+
});
95+
it('should get() a K(int):V with collisions from table properly (1).', function () {
6796
var hashTable = new Hashtable();
6897
hashTable.put(10, 'value', 'someHash');
6998
hashTable.put(35, 'anotherValue', 'someHash');
7099
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
71100
});
72-
it('should get() a k:v with collisions from table properly (2).', function () {
101+
it('should get() a K(int):V with collisions from table properly (2).', function () {
73102
var hashTable = new Hashtable();
74103
hashTable.put(10, 'value', 'someHash');
75104
hashTable.put(35, 'anotherValue', 'someHash');
76105
hashTable.put(77, 'lastValue', 'someHash');
77106
expect(hashTable.get(77, 'someHash')).toBe('lastValue');
78107
});
79-
it('should get() a k:v with collisions from table properly (3).', function () {
108+
it('should get() a K(int):V with collisions from table properly (3).', function () {
80109
var hashTable = new Hashtable();
81110
hashTable.put(10, 'value', 'someHash');
82111
hashTable.put(35, 'anotherValue', 'someHash');
83112
hashTable.put(77, 'lastValue', 'someHash');
84113
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
85114
});
86-
it('should get() a k:v with collisions from table properly (4).', function () {
115+
it('should get() a K(int):V with collisions from table properly (4).', function () {
87116
var hashTable = new Hashtable();
88117
hashTable.put(10, 'value', 'someHash');
89118
hashTable.put(35, 'anotherValue', 'someHash');
90119
hashTable.put(77, 'lastValue', 'someHash');
91120
expect(hashTable.get(10, 'someHash')).toBe('value');
92121
});
93-
it('should remove() a k:v from table properly.', function () {
122+
it('should get() a K(string):V with collisions from table properly (1).', function () {
123+
var hashTable = new Hashtable();
124+
hashTable.put('keyA', 'value', 'someHash');
125+
hashTable.put('keyB', 'anotherValue', 'someHash');
126+
expect(hashTable.get('keyB', 'someHash')).toBe('anotherValue');
127+
});
128+
it('should get() a K(string):V with collisions from table properly (2).', function () {
129+
var hashTable = new Hashtable();
130+
hashTable.put('keyA', 'value', 'someHash');
131+
hashTable.put('keyB', 'anotherValue', 'someHash');
132+
hashTable.put('keyC', 'lastValue', 'someHash');
133+
expect(hashTable.get('keyC', 'someHash')).toBe('lastValue');
134+
});
135+
it('should get() a K(string):V with collisions from table properly (3).', function () {
136+
var hashTable = new Hashtable();
137+
hashTable.put('keyA', 'value', 'someHash');
138+
hashTable.put('keyB', 'anotherValue', 'someHash');
139+
hashTable.put('keyC', 'lastValue', 'someHash');
140+
expect(hashTable.get('keyB', 'someHash')).toBe('anotherValue');
141+
});
142+
it('should get() a K(string):V with collisions from table properly (4).', function () {
143+
var hashTable = new Hashtable();
144+
hashTable.put('keyA', 'value', 'someHash');
145+
hashTable.put('keyB', 'anotherValue', 'someHash');
146+
hashTable.put('keyC', 'lastValue', 'someHash');
147+
expect(hashTable.get('keyA', 'someHash')).toBe('value');
148+
});
149+
it('should remove() a K(int):V from table properly (1).', function () {
94150
// remove only node/link in bucket : (B)
95151
var hashTable = new Hashtable();
96152
hashTable.put(10, 'value');
97153
hashTable.remove(10);
98154
expect(hashTable.get(10)).toBe(undefined);
99155
});
100-
it('should remove() a k:v with collisions from table properly (2).', function () {
156+
it('should remove() a K(int):V with collisions from table properly (2).', function () {
101157
// remove start node/link in bucket : (B) - A
102158
var hashTable = new Hashtable();
103159
hashTable.put(10, 'value', 'someHash');
@@ -106,7 +162,7 @@ describe('Hash table', function () {
106162
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
107163
expect(hashTable.get(10, 'someHash')).toBe(undefined);
108164
});
109-
it('should remove() a k:v with collisions from table properly (3).', function () {
165+
it('should remove() a K(int):V with collisions from table properly (3).', function () {
110166
// remove start node/link in bucket : (B) - A - C
111167
var hashTable = new Hashtable();
112168
hashTable.put(10, 'value', 'someHash');
@@ -116,7 +172,7 @@ describe('Hash table', function () {
116172
expect(hashTable.get(35, 'someHash')).toBe('anotherValue');
117173
expect(hashTable.get(66, 'someHash')).toBe('lastValue');
118174
});
119-
it('should remove() a k:v with collisions from table properly (4).', function () {
175+
it('should remove() a K(int):V with collisions from table properly (4).', function () {
120176
// remove middle node/link in bucket : A - (B) - C
121177
var hashTable = new Hashtable();
122178
hashTable.put(10, 'value', 'someHash');
@@ -126,4 +182,40 @@ describe('Hash table', function () {
126182
expect(hashTable.get(10, 'someHash')).toBe('value');
127183
expect(hashTable.get(66, 'someHash')).toBe('lastValue');
128184
});
185+
it('should remove() a K(string):V from table properly (1).', function () {
186+
// remove only node/link in bucket : (B)
187+
var hashTable = new Hashtable();
188+
hashTable.put('keyA', 'value');
189+
hashTable.remove('keyA');
190+
expect(hashTable.get('keyA')).toBe(undefined);
191+
});
192+
it('should remove() a K(string):V with collisions from table properly (2).', function () {
193+
// remove start node/link in bucket : (B) - A
194+
var hashTable = new Hashtable();
195+
hashTable.put('keyA', 'value', 'someHash');
196+
hashTable.put('keyB', 'anotherValue', 'someHash');
197+
expect(hashTable.remove('keyA', 'someHash')).toBe('value');
198+
expect(hashTable.get('keyB', 'someHash')).toBe('anotherValue');
199+
expect(hashTable.get('keyA', 'someHash')).toBe(undefined);
200+
});
201+
it('should remove() a K(string):V with collisions from table properly (3).', function () {
202+
// remove start node/link in bucket : (B) - A - C
203+
var hashTable = new Hashtable();
204+
hashTable.put('keyA', 'value', 'someHash');
205+
hashTable.put('keyB', 'anotherValue', 'someHash');
206+
hashTable.put('keyC', 'lastValue', 'someHash');
207+
expect(hashTable.remove('keyA', 'someHash')).toBe('value');
208+
expect(hashTable.get('keyB', 'someHash')).toBe('anotherValue');
209+
expect(hashTable.get('keyC', 'someHash')).toBe('lastValue');
210+
});
211+
it('should remove() a K(string):V with collisions from table properly (4).', function () {
212+
// remove middle node/link in bucket : A - (B) - C
213+
var hashTable = new Hashtable();
214+
hashTable.put('keyA', 'value', 'someHash');
215+
hashTable.put('keyB', 'anotherValue', 'someHash');
216+
hashTable.put('keyC', 'lastValue', 'someHash');
217+
expect(hashTable.remove('keyB', 'someHash')).toBe('anotherValue');
218+
expect(hashTable.get('keyA', 'someHash')).toBe('value');
219+
expect(hashTable.get('keyC', 'someHash')).toBe('lastValue');
220+
});
129221
});

0 commit comments

Comments
 (0)