Bookmark this: tool.io/data-structure/bloom-filter/source-code
Bloom Filter Calculator Source Code
Browse the implementation files for Bloom Filter Calculator.tool.ts typescript
import { parseInteger } from '../../parse/integer/tool';
const hash = (value: string, seed: number): number => {
let state = (2166136261 ^ seed) >>> 0;
for (let index = 0; index < value.length; index += 1) {
state ^= value.charCodeAt(index);
state = Math.imul(state, 16777619);
}
return state >>> 0;
};
export const calculateBloomFilter = (
itemsInput: unknown,
queryInput: unknown,
bitCountInput: unknown,
hashCountInput: unknown
): string => {
if (
typeof itemsInput !== 'string' ||
typeof queryInput !== 'string' ||
!queryInput.trim()
)
return '';
const items = [
...new Set(
itemsInput
.split(/[,;\n]+/)
.map((item) => item.trim())
.filter(Boolean)
)
];
const query = queryInput.trim();
const bitCount = parseInteger(bitCountInput);
const hashCount = parseInteger(hashCountInput);
if (
!items.length ||
bitCount === null ||
bitCount < 8 ||
bitCount > 1_000_000 ||
hashCount === null ||
hashCount < 1 ||
hashCount > 32
)
return '';
const bits = new Uint8Array(bitCount);
const indexes = (value: string): number[] =>
Array.from(
{ length: hashCount },
(_, index) => hash(value, index + 1) % bitCount
);
for (const item of items)
for (const index of indexes(item)) bits[index] = 1;
const possiblyPresent = indexes(query).every(
(index) => bits[index] === 1
);
const setBits = bits.reduce((sum, bit) => sum + bit, 0);
const falsePositiveProbability =
(1 - Math.exp((-hashCount * items.length) / bitCount)) **
hashCount;
return JSON.stringify(
{
bitCount,
falsePositiveProbability: Number(
falsePositiveProbability.toPrecision(8)
),
hashCount,
itemCount: items.length,
possiblyPresent,
query,
setBits
},
null,
2
);
};
export const Tool: TypeTool = {
name: 'Bloom Filter Calculator',
slug: 'data-structure/bloom-filter',
intro:
'Build a deterministic Bloom filter, test an item, and estimate its false-positive probability.',
tool: calculateBloomFilter,
i: [
{
example: 'apple, banana, pear',
label: 'Items',
placeholder: 'Comma- or line-separated items',
render: 'textarea',
type: 'text'
},
{
example: 'banana',
label: 'Query',
placeholder: 'Item to test',
type: 'text'
},
{
example: '128',
label: 'Bits',
placeholder: 'Filter size in bits',
type: 'number'
},
{
example: '3',
label: 'Hash Functions',
placeholder: 'Number of hashes',
type: 'number'
}
],
o: [
{
example: '{ "possiblyPresent": true }',
label: 'Bloom Filter Result',
placeholder: 'Result will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'Bloom filter - Wikipedia',
url: 'https://en.wikipedia.org/wiki/Bloom_filter'
}
]
};
export default Tool;
Description
Browse the implementation files for Bloom Filter Calculator.