In which we finish the chapter by providing answers to all the questions in the text.
Chapter 11½
Here are all the answers to the questions in this new chapter.
11½–1. Do it with class!
To implement an SBF using classes, we may use private (#) attributes, so only add and find will be visible. Assume we are importing the hashWithSeed function from another module. From our code (see below) we would only export StandardBloomFilter.
const EPSILON = 0.01;
const LN2 = Math.log(2);
const LN2_SQ = LN2 * LN2;
class StandardBloomFilter {
#b;
#h;
#bits;
constructor(n, eps = EPSILON) {
this.#b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
this.#h = Math.max(1, Math.round((this.#b / n) * LN2));
this.#bits = new Array(this.#b).fill(false);
}
#getIndices(value) {
return Array.from(
{ length: this.#h },
(_, i) => hashWithSeed(String(value), i) % this.#b
);
}
add(value) {
for (const idx of this.#getIndices(value)) {
this.#bits[idx] = true;
}
}
find(value) {
return this.#getIndices(value).every((idx) => this.#bits[idx] === true);
}
}
We can also hide internal details by using closures. When you create a new SBF by calling newClosureBloomFilter, you get an object with just the add and find methods; you cannot access b, h, or the bits array, for example.
const EPSILON = 0.01;
const LN2 = Math.log(2);
const LN2_SQ = LN2 * LN2;
const newClosureBloomFilter = (n, eps = EPSILON) => {
const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
const h = Math.max(1, Math.round((b / n) * LN2));
const bits = new Array(b).fill(false);
const getIndices = (value) =>
Array.from({ length: h }, (_, i) => hashWithSeed(String(value), i) % b);
const add = (value) => {
for (const idx of getIndices(value)) {
bits[idx] = true;
}
};
const find = (value) =>
getIndices(value).every((idx) => bits[idx] === true);
return { add, find };
};
11½–2. Getting down to bits
After calculating how many bits (b) we require, we can use an Uint8Array whose size is b/8 rounded up, since each entry in the array provides 8 bits. To access a given bit, first calculate which array entry it is in, then which bit to test. The modified functions are below.
const newStandardBloomFilter = (n, eps = EPSILON) => {
const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
const h = Math.max(1, Math.round((b / n) * LN2));
return {
b,
h,
➊ bits: new Uint8Array(Math.ceil(b / 8))
};
};
const add = (filter, value) => {
for (const idx of getIndices(filter, value)) {
➋ const byteIndex = idx >> 3;
➌ const bitMask = 1 << (idx & 7);
➍ filter.bits[byteIndex] |= bitMask;
}
};
const find = (filter, value) =>
getIndices(filter, value).every((idx) => {
const byteIndex = idx >> 3;
const bitMask = 1 << (idx & 7);
➎ return (filter.bits[byteIndex] & bitMask) !== 0;
});
The first change is that instead of creating a common array, we produce an Uint8Array; using Math.ceil deals with the case in which b is not divisible by 8, making the array just a tad bigger than needed. (The waste is minimal; just a few bits!) We can find which byte to modify by dividing idx by 8 ➋ which is achieved by using the >> binary right shift operator. Which bit to set is the remainder of idx divided by 8; this is also achieved by using a bitmask (AND-ing a number with 7 produces just the lower-order three bits.) Finally ➍ we use the binary | OR operator to set the needed bit. When doing a search ➎ everything works the same way, but we use the binary AND operator to test the required bit.
11½–3. A powerful solution
We wanted to ensure that the bitmap size and the 2nd hash function have no common divisors. If the bitmap size is a power of 2, its only factors are powers of 2. On the other hand, if the hash function is odd, it cannot be divided by 2. Thus, we are guaranteed that no loops can happen. The changed code is shown below; we just modify the sizing part.
➊ const nextPowerOfTwo = (n) => 2 ** Math.ceil(Math.log2(n));
const newDoubleHashingBloomFilterPowerOfTwo = (n, eps = EPSILON) => {
➋const b = nextPowerOfTwo(Math.ceil(-(n * Math.log(eps)) / LN2_SQ));
const h = Math.max(1, Math.round((b / n) * LN2));
return {
b,
h,
bits: new Array(b).fill(false)
};
};
The nextPowerOfTwo function ➊ finds the next highest power of two for a number. Pick a number; say 10. If you take the logarithm in base 2, you get 3.3219… so 2³ is less than 10, and 2⁴ is greater; the latter is the result we need. We use the function ➋ to determine the bitmap size.
The only disadvantage of this fix is that you may end up needing almost twice the size you'd really need. For instance, if you calculated that you needed a bitmap with 1,025 bits (just 1 beyond 2¹⁰ bits) you'd require a 2,048-sized one instead.
11½–4. Over the top?
A "stuck" counter will never go down to zero, so any value relying on that count to determine "present" will always show as present. In effect, the filter loses the ability to report items "absent" through that count again, even if all the items that caused the saturation are eventually deleted. This is a graceful degradation toward more false positives, which is what we tolerate, rather than toward false negatives, which we never allow.
11½–5. Why not make it simpler?
With the suggested change, all slots would share the same object with rem, isOcc, isCont, and isShifted attributes, instead of having separate, independent ones.
11½–6. Unneeded test?
After calling locateRun we know we are at the start of a run. We want to check later whether we reach the start of another run (and then fail the search) but we cannot fail this run. Excluding the test would cause the loop to immediately stop.
11½–7. Add it again, Sam
The current logic will not detect the repetition and will add the repeated remainder after the current ones equal it. In the loop ➏ we should specifically check for equality, and in that case simply return.
11½–8. It all comes out in the wash
For a given set of additions and removals (assuming you do not try to remove a value before it was added) the result is always the same. To figure this out, consider that if you have separate clusters, whatever you do in one doesn't affect the sequence of values in the other. Also, within a cluster, runs are in strict quotient order, and each run is in remainder order.
11½–9. If at first you fail…
This could also fail; you cannot guarantee that the second hash calculation won't also return 0. The probability is 1 in 2^(2_p_), but it's not zero.
11½–10. Let it Be
The CF would still work, but one value (the one in the final loop pass) that was previously there could be gone, and a new one may now be in the filter. There is a small possibility (1 in 2bs) that the last kicked value happened to be just the one we were trying to add, but the most likely result would be that some other value would end kicked out.
11½–11. Some like it short
The following code does the job; instead of destructuring indices into i1 and i2 and checking each bucket by hand, we keep the array and let .some test each index. It returns true as soon as one bucket contains the fingerprint, which is the same short-circuit behavior as the original ||. The code looks shorter, but it's still two lines!
const find = (filter, item) => {
const { fingerprint, indices } = twoBuckets(filter, item);
return indices.some(i => filter.buckets[i].includes(fingerprint));
};
Want to get the book?
If you want the original, complete book, you can find it at the publisher, No Starch Press, or at Amazon, Barnes & Noble, Books-A-Million, Bookshop, Powell's Books, Target, or Walmart, in either paperback or e-book format.
Top comments (0)