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

Commit d7a3918

Browse files
Implement load factor dynamic resizing
1 parent dc1047d commit d7a3918

File tree

2 files changed

+161
-0
lines changed

2 files changed

+161
-0
lines changed
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
import HashTable from './HashTable';
2+
import LinkedList from '../linked-list/LinkedList';
3+
4+
const defaultHashTableSize = 8;
5+
6+
export default class DynamicHashTable extends HashTable {
7+
/**
8+
* @param {number} hashTableSize
9+
*/
10+
constructor(hashTableSize = defaultHashTableSize, loadFactor = 0.75) {
11+
super(hashTableSize);
12+
13+
// resize parameters
14+
this.capacity = hashTableSize;
15+
this.loadFactor = loadFactor;
16+
this.calculateThreshold();
17+
18+
// track the number of entries
19+
this.size = 0;
20+
}
21+
22+
/**
23+
* @param {string} key
24+
* @param {*} value
25+
*/
26+
set(key, value) {
27+
super.set(key, value);
28+
this.size += 1;
29+
30+
if (this.size > this.threshold) {
31+
this.resize();
32+
}
33+
}
34+
35+
/**
36+
* @param {string} key
37+
* @return {*}
38+
*/
39+
delete(key) {
40+
this.size -= 1;
41+
return super.delete(key);
42+
}
43+
44+
/**
45+
* Creates new bucket array, twice as big as original.
46+
* Rehashes all entries
47+
*/
48+
resize() {
49+
// double capacity
50+
this.capacity *= 2;
51+
this.calculateThreshold();
52+
53+
// create new bucket array
54+
const originalBuckets = this.buckets;
55+
this.buckets = Array(this.capacity).fill(null).map(() => new LinkedList());
56+
this.keys = {};
57+
58+
// rehash all entries
59+
Object.values(originalBuckets).forEach((list) => {
60+
let currentNode = list.head;
61+
while (currentNode) {
62+
const { key, value } = currentNode.value;
63+
this.set(key, value);
64+
currentNode = currentNode.next;
65+
}
66+
});
67+
}
68+
69+
calculateThreshold() {
70+
this.threshold = this.capacity * this.loadFactor;
71+
}
72+
}
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
import HashTable from '../DynamicHashTable';
2+
3+
describe('HashTable', () => {
4+
it('should create hash table of certain size', () => {
5+
const defaultHashTable = new HashTable();
6+
expect(defaultHashTable.buckets.length).toBe(8);
7+
8+
const biggerHashTable = new HashTable(64);
9+
expect(biggerHashTable.buckets.length).toBe(64);
10+
});
11+
12+
it('should generate proper hash for specified keys', () => {
13+
const hashTable = new HashTable();
14+
15+
expect(hashTable.hash('a')).toBe(1);
16+
expect(hashTable.hash('b')).toBe(2);
17+
expect(hashTable.hash('abc')).toBe(6);
18+
});
19+
20+
it('should set, read and delete data with collisions', () => {
21+
const hashTable = new HashTable(3);
22+
23+
expect(hashTable.hash('a')).toBe(1);
24+
expect(hashTable.hash('b')).toBe(2);
25+
expect(hashTable.hash('c')).toBe(0);
26+
expect(hashTable.hash('d')).toBe(1);
27+
28+
hashTable.set('a', 'sky-old');
29+
hashTable.set('a', 'sky');
30+
hashTable.set('b', 'sea');
31+
hashTable.set('c', 'earth');
32+
hashTable.set('d', 'ocean');
33+
34+
expect(hashTable.has('x')).toBe(false);
35+
expect(hashTable.has('b')).toBe(true);
36+
expect(hashTable.has('c')).toBe(true);
37+
38+
// const stringifier = value => `${value.key}:${value.value}`;
39+
40+
// expect(hashTable.buckets[0].toString(stringifier)).toBe('c:earth');
41+
// expect(hashTable.buckets[1].toString(stringifier)).toBe('a:sky,d:ocean');
42+
// expect(hashTable.buckets[2].toString(stringifier)).toBe('b:sea');
43+
44+
expect(hashTable.get('a')).toBe('sky');
45+
expect(hashTable.get('d')).toBe('ocean');
46+
expect(hashTable.get('x')).not.toBeDefined();
47+
48+
hashTable.delete('a');
49+
50+
expect(hashTable.delete('not-existing')).toBeNull();
51+
52+
expect(hashTable.get('a')).not.toBeDefined();
53+
expect(hashTable.get('d')).toBe('ocean');
54+
55+
hashTable.set('d', 'ocean-new');
56+
expect(hashTable.get('d')).toBe('ocean-new');
57+
});
58+
59+
it('should be possible to add objects to hash table', () => {
60+
const hashTable = new HashTable();
61+
62+
hashTable.set('objectKey', { prop1: 'a', prop2: 'b' });
63+
64+
const object = hashTable.get('objectKey');
65+
expect(object).toBeDefined();
66+
expect(object.prop1).toBe('a');
67+
expect(object.prop2).toBe('b');
68+
});
69+
70+
it('should track actual keys', () => {
71+
const hashTable = new HashTable(3);
72+
73+
hashTable.set('a', 'sky-old');
74+
hashTable.set('a', 'sky');
75+
hashTable.set('b', 'sea');
76+
hashTable.set('c', 'earth');
77+
hashTable.set('d', 'ocean');
78+
79+
expect(hashTable.getKeys()).toEqual(['a', 'b', 'c', 'd']);
80+
expect(hashTable.has('a')).toBe(true);
81+
expect(hashTable.has('x')).toBe(false);
82+
83+
hashTable.delete('a');
84+
85+
expect(hashTable.has('a')).toBe(false);
86+
expect(hashTable.has('b')).toBe(true);
87+
expect(hashTable.has('x')).toBe(false);
88+
});
89+
});

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /