Advertisement
rgruber

Bloom filter implementation in JavaScript

Jan 26th, 2023
685
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Bloom filter implementation in JavaScript
  2.  
  3. class BloomFilter {
  4.   constructor(size) {
  5.     this.array = new Array(size).fill(0);
  6.     this.indexes = [];
  7.   }
  8.  
  9.   hash(string) {
  10.     let hash = 0;
  11.     for (let i = 0; i < string.length; i++) {
  12.       const char = string.charCodeAt(i);
  13.       hash = (hash << 5) - hash + char;
  14.       hash &= hash;
  15.     }
  16.     return hash;
  17.   }
  18.  
  19.   getIndexes(string) {
  20.     const hash1 = Math.abs(this.hash(string)) % this.array.length;
  21.     const hash2 = Math.abs(this.hash(string + '1')) % this.array.length;
  22.     return [hash1, hash2];
  23.   }
  24.  
  25.   add(string) {
  26.     this.indexes = this.getIndexes(string);
  27.     for (let i = 0; i < this.indexes.length; i++) {
  28.       const index = this.indexes[i];
  29.       this.array[index] = 1;
  30.     }
  31.   }
  32.  
  33.   contains(string) {
  34.     this.indexes = this.getIndexes(string);
  35.     for (let i = 0; i < this.indexes.length; i++) {
  36.       const index = this.indexes[i];
  37.       if (this.array[index] === 0) {
  38.         return false;
  39.       }
  40.     }
  41.     return true;
  42.   }
  43.  
  44.   export() {
  45.     return this.array;
  46.   }
  47.  
  48.   import(array) {
  49.     if (array.length !== this.array.length) {
  50.       throw 'Cannot import array of different size';
  51.     }
  52.     this.array = array;
  53.   }
  54. }
  55.  
  56. module.exports = BloomFilter;
Tags: Bloom filter
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement