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

Commit610b120

Browse files
committed
BloomFilter minor fixes.
1 parentb33b1fe commit610b120

File tree

2 files changed

+64
-37
lines changed

2 files changed

+64
-37
lines changed

‎src/data-structures/bloom-filter/BloomFilter.js

Lines changed: 26 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
exportdefaultclassBloomFilter{
22
/**
3-
*@param {number} size
3+
*@param {number} size - the size of the storage.
44
*/
55
constructor(size=100){
66
// Bloom filter size directly affects the likelihood of false positives.
@@ -15,7 +15,7 @@ export default class BloomFilter {
1515
insert(item){
1616
consthashValues=this.getHashValues(item);
1717

18-
// Set each hashValue index to true
18+
// Set each hashValue index to true.
1919
hashValues.forEach(val=>this.storage.setValue(val));
2020
}
2121

@@ -26,8 +26,8 @@ export default class BloomFilter {
2626
mayContain(item){
2727
consthashValues=this.getHashValues(item);
2828

29-
for(leti=0;i<hashValues.length;i+=1){
30-
if(!this.storage.getValue(hashValues[i])){
29+
for(lethashIndex=0;hashIndex<hashValues.length;hashIndex+=1){
30+
if(!this.storage.getValue(hashValues[hashIndex])){
3131
// We know that the item was definitely not inserted.
3232
returnfalse;
3333
}
@@ -50,7 +50,7 @@ export default class BloomFilter {
5050
conststorage=[];
5151

5252
// Initialize all indexes to false
53-
for(leti=0;i<size;i+=1){
53+
for(letstorageCellIndex=0;storageCellIndex<size;storageCellIndex+=1){
5454
storage.push(false);
5555
}
5656

@@ -67,14 +67,14 @@ export default class BloomFilter {
6767
}
6868

6969
/**
70-
*@param {string}str
70+
*@param {string}item
7171
*@return {number}
7272
*/
73-
hash1(str){
73+
hash1(item){
7474
lethash=0;
7575

76-
for(leti=0;i<str.length;i+=1){
77-
constchar=str.charCodeAt(i);
76+
for(letcharIndex=0;charIndex<item.length;charIndex+=1){
77+
constchar=item.charCodeAt(charIndex);
7878
hash=(hash<<5)+hash+char;
7979
hash&=hash;// Convert to 32bit integer
8080
hash=Math.abs(hash);
@@ -84,44 +84,48 @@ export default class BloomFilter {
8484
}
8585

8686
/**
87-
*@param {string}str
87+
*@param {string}item
8888
*@return {number}
8989
*/
90-
hash2(str){
90+
hash2(item){
9191
lethash=5381;
9292

93-
for(leti=0;i<str.length;i+=1){
94-
constchar=str.charCodeAt(i);
93+
for(letcharIndex=0;charIndex<item.length;charIndex+=1){
94+
constchar=item.charCodeAt(charIndex);
9595
hash=(hash<<5)+hash+char;/* hash * 33 + c */
9696
}
9797

98-
returnhash%this.size;
98+
returnMath.abs(hash%this.size);
9999
}
100100

101101
/**
102-
*@param {string}str
102+
*@param {string}item
103103
*@return {number}
104104
*/
105-
hash3(str){
105+
hash3(item){
106106
lethash=0;
107107

108-
for(leti=0;i<str.length;i+=1){
109-
constchar=str.charCodeAt(i);
108+
for(letcharIndex=0;charIndex<item.length;charIndex+=1){
109+
constchar=item.charCodeAt(charIndex);
110110
hash=(hash<<5)-hash;
111111
hash+=char;
112112
hash&=hash;// Convert to 32bit integer
113113
}
114114

115-
returnhash%this.size;
115+
returnMath.abs(hash%this.size);
116116
}
117117

118118
/**
119-
* Runs all 3 hash functions on the input and returns an array of results
119+
* Runs all 3 hash functions on the input and returns an array of results.
120120
*
121-
*@param {string}str
121+
*@param {string}item
122122
*@return {number[]}
123123
*/
124124
getHashValues(item){
125-
return[this.hash1(item),Math.abs(this.hash2(item)),Math.abs(this.hash3(item))];
125+
return[
126+
this.hash1(item),
127+
this.hash2(item),
128+
this.hash3(item),
129+
];
126130
}
127131
}
Lines changed: 38 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,62 @@
11
importBloomFilterfrom'../BloomFilter';
22

3-
describe('Bloom Filter',()=>{
3+
describe('BloomFilter',()=>{
44
letbloomFilter;
5-
constpeople=['Bruce Wayne','Clark Kent','Barry Allen'];
5+
constpeople=[
6+
'Bruce Wayne',
7+
'Clark Kent',
8+
'Barry Allen',
9+
];
610

711
beforeEach(()=>{
812
bloomFilter=newBloomFilter();
913
});
1014

11-
it('Should have methods named "insert" and "mayContain"',()=>{
15+
it('should have methods named "insert" and "mayContain"',()=>{
1216
expect(typeofbloomFilter.insert).toBe('function');
1317
expect(typeofbloomFilter.mayContain).toBe('function');
1418
});
1519

16-
it('Should create a new filter store with the appropriate methods',()=>{
20+
it('should create a new filter store with the appropriate methods',()=>{
1721
conststore=bloomFilter.createStore(18);
1822
expect(typeofstore.getValue).toBe('function');
1923
expect(typeofstore.setValue).toBe('function');
2024
});
2125

22-
it('Should hash deterministically with all 3 hash functions',()=>{
23-
conststr='abc';
24-
expect(bloomFilter.hash1(str)).toEqual(bloomFilter.hash1(str));
25-
expect(bloomFilter.hash2(str)).toEqual(bloomFilter.hash2(str));
26-
expect(bloomFilter.hash3(str)).toEqual(bloomFilter.hash3(str));
26+
it('should hash deterministically with all 3 hash functions',()=>{
27+
conststr1='apple';
28+
29+
expect(bloomFilter.hash1(str1)).toEqual(bloomFilter.hash1(str1));
30+
expect(bloomFilter.hash2(str1)).toEqual(bloomFilter.hash2(str1));
31+
expect(bloomFilter.hash3(str1)).toEqual(bloomFilter.hash3(str1));
32+
33+
expect(bloomFilter.hash1(str1)).toBe(14);
34+
expect(bloomFilter.hash2(str1)).toBe(43);
35+
expect(bloomFilter.hash3(str1)).toBe(10);
36+
37+
conststr2='orange';
38+
39+
expect(bloomFilter.hash1(str2)).toEqual(bloomFilter.hash1(str2));
40+
expect(bloomFilter.hash2(str2)).toEqual(bloomFilter.hash2(str2));
41+
expect(bloomFilter.hash3(str2)).toEqual(bloomFilter.hash3(str2));
42+
43+
expect(bloomFilter.hash1(str2)).toBe(0);
44+
expect(bloomFilter.hash2(str2)).toBe(61);
45+
expect(bloomFilter.hash3(str2)).toBe(10);
2746
});
2847

29-
it('Should create an array with 3 hash values',()=>{
30-
expect(bloomFilter.getHashValues('abc').length).toEqual(3);
48+
it('should create an array with 3 hash values',()=>{
49+
expect(bloomFilter.getHashValues('abc').length).toBe(3);
50+
expect(bloomFilter.getHashValues('abc')).toEqual([66,63,54]);
3151
});
3252

33-
it('Should insert strings correctly and return true when checking for inserted values',()=>{
53+
it('should insert strings correctly and return true when checking for inserted values',()=>{
3454
people.forEach(person=>bloomFilter.insert(person));
35-
expect(bloomFilter.mayContain('Bruce Wayne')).toBe(true);
36-
expect(bloomFilter.mayContain('Clark Kent')).toBe(true);
37-
expect(bloomFilter.mayContain('Barry Allen')).toBe(true);
55+
56+
expect(bloomFilter.mayContain('Bruce Wayne')).toBeTruthy();
57+
expect(bloomFilter.mayContain('Clark Kent')).toBeTruthy();
58+
expect(bloomFilter.mayContain('Barry Allen')).toBeTruthy();
59+
60+
expect(bloomFilter.mayContain('Tony Stark')).toBeFalsy();
3861
});
3962
});

0 commit comments

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