This package naively implements the data structure described in Invertible Bloom Lookup Tables by Goodrich & Mitzenmacher.

The examples in this file are run as the package's test suite.

Initialization

var IBLT = require('iblt')

var m = 10

var table = new IBLT({
  m: m,
  hashes: [single, double, triple]
})

var murmur = require('murmurhash').v3

function single (argument) {
  return murmur(Number(argument).toString()) % m
}

function double (argument) {
  return murmur(murmur(Number(argument).toString())) % m
}

function triple (argument) {
  return murmur(murmur(murmur(Number(argument).toString()))) % m
}

Insert, Get, Delete

table.insert(100, 123)
table.insert(200, 456)
table.insert(300, 789)

var assert = require('assert')

assert.equal(table.get(100), 123)
assert.equal(table.get(200), 456)
assert.equal(table.get(300), 789)

table.delete(300, 789)

assert.equal(table.get(300), null)

Clone and List Entries

var clone = table.clone()

assert(clone instanceof IBLT)

var entries = table.listEntries() // destructive

assert(entries.succeeded)

assert(entries.outputList.some(function (x) {
  return x[0] === 100 && x[1] === 123
}))

assert(entries.outputList.some(function (x) {
  return x[0] === 200 && x[1] === 456
}))

Cells

var cells = clone.T

assert(cells.every(function (cell) {
  return cell &&
    'count' in cell &&
    'keySum' in cell &&
    'valueSum' in cell
}))