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

Commitecd8d22

Browse files
committed
Add new hash table methods.
1 parentf04626b commitecd8d22

File tree

2 files changed

+82
-12
lines changed

2 files changed

+82
-12
lines changed

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

Lines changed: 50 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,29 @@
11
importLinkedListfrom'../linked-list/LinkedList';
22

3+
// Hash table size directly affects on the number of collisions.
4+
// The bigger the hash table size the less collisions you'll get.
5+
// For demonstrating purposes hash table size is small to show how collisions
6+
// are being handled.
37
constdefaultHashTableSize=32;
48

59
exportdefaultclassHashTable{
10+
/**
11+
*@param {number} hashTableSize
12+
*/
613
constructor(hashTableSize=defaultHashTableSize){
714
// Create hash table of certain size and fill each bucket with empty linked list.
815
this.buckets=Array(hashTableSize).fill(null).map(()=>newLinkedList());
16+
17+
// Just to keep track of all actual keys in a fast way.
18+
this.keys={};
919
}
1020

11-
// Converts key string to hash number.
21+
/**
22+
* Converts key string to hash number.
23+
*
24+
*@param {string} key
25+
*@return {number}
26+
*/
1227
hash(key){
1328
consthash=Array.from(key).reduce(
1429
(hashAccumulator,keySymbol)=>(hashAccumulator+keySymbol.charCodeAt(0)),
@@ -19,8 +34,14 @@ export default class HashTable {
1934
returnhash%this.buckets.length;
2035
}
2136

22-
insert(key,value){
23-
constbucketLinkedList=this.buckets[this.hash(key)];
37+
/**
38+
*@param {string} key
39+
*@param {*} value
40+
*/
41+
set(key,value){
42+
constkeyHash=this.hash(key);
43+
this.keys[key]=keyHash;
44+
constbucketLinkedList=this.buckets[keyHash];
2445
constnode=bucketLinkedList.find({callback:nodeValue=>nodeValue.key===key});
2546

2647
if(!node){
@@ -32,8 +53,14 @@ export default class HashTable {
3253
}
3354
}
3455

56+
/**
57+
*@param {string} key
58+
*@return {*}
59+
*/
3560
delete(key){
36-
constbucketLinkedList=this.buckets[this.hash(key)];
61+
constkeyHash=this.hash(key);
62+
deletethis.keys[key];
63+
constbucketLinkedList=this.buckets[keyHash];
3764
constnode=bucketLinkedList.find({callback:nodeValue=>nodeValue.key===key});
3865

3966
if(node){
@@ -43,10 +70,29 @@ export default class HashTable {
4370
returnnull;
4471
}
4572

73+
/**
74+
*@param {string} key
75+
*@return {*}
76+
*/
4677
get(key){
4778
constbucketLinkedList=this.buckets[this.hash(key)];
4879
constnode=bucketLinkedList.find({callback:nodeValue=>nodeValue.key===key});
4980

5081
returnnode ?node.value.value :null;
5182
}
83+
84+
/**
85+
*@param {string} key
86+
*@return {boolean}
87+
*/
88+
has(key){
89+
returnObject.hasOwnProperty.call(this.keys,key);
90+
}
91+
92+
/**
93+
*@return {string[]}
94+
*/
95+
getKeys(){
96+
returnObject.keys(this.keys);
97+
}
5298
}

‎src/data-structures/hash-table/__test__/HashTable.test.js

Lines changed: 32 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -17,19 +17,23 @@ describe('HashTable', () => {
1717
expect(hashTable.hash('abc')).toBe(6);
1818
});
1919

20-
it('shouldinsert, read and delete data with collisions',()=>{
20+
it('shouldset, read and delete data with collisions',()=>{
2121
consthashTable=newHashTable(3);
2222

2323
expect(hashTable.hash('a')).toBe(1);
2424
expect(hashTable.hash('b')).toBe(2);
2525
expect(hashTable.hash('c')).toBe(0);
2626
expect(hashTable.hash('d')).toBe(1);
2727

28-
hashTable.insert('a','sky-old');
29-
hashTable.insert('a','sky');
30-
hashTable.insert('b','sea');
31-
hashTable.insert('c','earth');
32-
hashTable.insert('d','ocean');
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')).toBeFalsy();
35+
expect(hashTable.has('b')).toBeTruthy();
36+
expect(hashTable.has('c')).toBeTruthy();
3337

3438
conststringifier=value=>`${value.key}:${value.value}`;
3539

@@ -47,18 +51,38 @@ describe('HashTable', () => {
4751
expect(hashTable.get('a')).toBeNull();
4852
expect(hashTable.get('d')).toBe('ocean');
4953

50-
hashTable.insert('d','ocean-new');
54+
hashTable.set('d','ocean-new');
5155
expect(hashTable.get('d')).toBe('ocean-new');
5256
});
5357

5458
it('should be possible to add objects to hash table',()=>{
5559
consthashTable=newHashTable();
5660

57-
hashTable.insert('objectKey',{prop1:'a',prop2:'b'});
61+
hashTable.set('objectKey',{prop1:'a',prop2:'b'});
5862

5963
constobject=hashTable.get('objectKey');
6064
expect(object).toBeDefined();
6165
expect(object.prop1).toBe('a');
6266
expect(object.prop2).toBe('b');
6367
});
68+
69+
it('should track actual keys',()=>{
70+
consthashTable=newHashTable(3);
71+
72+
hashTable.set('a','sky-old');
73+
hashTable.set('a','sky');
74+
hashTable.set('b','sea');
75+
hashTable.set('c','earth');
76+
hashTable.set('d','ocean');
77+
78+
expect(hashTable.getKeys()).toEqual(['a','b','c','d']);
79+
expect(hashTable.has('a')).toBeTruthy();
80+
expect(hashTable.has('x')).toBeFalsy();
81+
82+
hashTable.delete('a');
83+
84+
expect(hashTable.has('a')).toBeFalsy();
85+
expect(hashTable.has('b')).toBeTruthy();
86+
expect(hashTable.has('x')).toBeFalsy();
87+
});
6488
});

0 commit comments

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