Bloom and cuckoo filters: membership at scale

Python 3.14 · main.py

M64 = 0xFFFFFFFFFFFFFFFF
BITS, HASHES = 48, 3
ADDED = "apple banana cherry grape lemon mango peach plum".split()
NEVER_ADDED = (
    "kiwi lime melon orange pear fig date guava papaya quince olive berry".split()
)


def hash64(text: str) -> int:
    # FNV-1a, then a mixing step so that similar words land far apart.
    h = 0xCBF29CE484222325
    for byte in text.encode():
        h = ((h ^ byte) * 0x100000001B3) & M64
    h = ((h ^ (h >> 30)) * 0xBF58476D1CE4E5B9) & M64
    h = ((h ^ (h >> 27)) * 0x94D049BB133111EB) & M64
    return h ^ (h >> 31)


def positions(word: str) -> list[int]:
    # k positions from one hash: h1 + i * h2 (double hashing).
    h = hash64(word)
    h1, h2 = h & 0xFFFFFFFF, (h >> 32) | 1
    return [(h1 + i * h2) % BITS for i in range(HASHES)]


bits = [0] * BITS
for word in ADDED:
    for p in positions(word):
        bits[p] = 1
print(
    f"{BITS} bits, {HASHES} hash functions, {len(ADDED)} words added, {sum(bits)} bits set"
)
for word in ADDED + NEVER_ADDED:
    ps = positions(word)
    zeros = [p for p in ps if bits[p] == 0]
    if zeros:
        answer = f"no (bit {zeros[0]} is 0)"
    else:
        answer = "maybe (it was added)" if word in ADDED else "maybe: a false positive"
    shown = ", ".join(f"{p:>2}" for p in ps)
    print(f"  {word:<7} bits {shown}   {answer}")

In Python: Python's integers never overflow, so every product is cut back to 64 bits with & M64, the wrap-around the other languages get from their 64-bit types.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const M64 = (1n << 64n) - 1n;
const BITS = 48;
const HASHES = 3;
const ADDED = "apple banana cherry grape lemon mango peach plum".split(" ");
const NEVER_ADDED = "kiwi lime melon orange pear fig date guava papaya quince olive berry".split(
  " ",
);

function hash64(text) {
  // FNV-1a, then a mixing step so that similar words land far apart.
  let h = 0xcbf29ce484222325n;
  for (let i = 0; i < text.length; i++) {
    h = ((h ^ BigInt(text.charCodeAt(i))) * 0x100000001b3n) & M64;
  }
  h = ((h ^ (h >> 30n)) * 0xbf58476d1ce4e5b9n) & M64;
  h = ((h ^ (h >> 27n)) * 0x94d049bb133111ebn) & M64;
  return h ^ (h >> 31n);
}

function positions(word) {
  // k positions from one hash: h1 + i * h2 (double hashing).
  const h = hash64(word);
  const [h1, h2] = [h & 0xffffffffn, (h >> 32n) | 1n];
  return Array.from({ length: HASHES }, (_, i) => Number((h1 + BigInt(i) * h2) % BigInt(BITS)));
}

const bits = new Array(BITS).fill(0);
for (const word of ADDED) {
  for (const p of positions(word)) bits[p] = 1;
}
const ones = bits.reduce((sum, b) => sum + b, 0);
console.log(
  `${BITS} bits, ${HASHES} hash functions, ${ADDED.length} words added, ${ones} bits set`,
);
for (const word of [...ADDED, ...NEVER_ADDED]) {
  const ps = positions(word);
  const zeros = ps.filter((p) => bits[p] === 0);
  let answer = ADDED.includes(word) ? "maybe (it was added)" : "maybe: a false positive";
  if (zeros.length > 0) answer = `no (bit ${zeros[0]} is 0)`;
  const shown = ps.map((p) => String(p).padStart(2)).join(", ");
  console.log(`  ${word.padEnd(7)} bits ${shown}   ${answer}`);
}

In JavaScript: A Number holds only 53 bits exactly, so the hash is a BigInt masked to 64 bits. The words are ASCII, so each charCodeAt is one UTF-8 byte.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.stream.IntStream;

public class Main {
  static final int BITS = 48;
  static final int HASHES = 3;
  static final List<String> ADDED =
      List.of("apple banana cherry grape lemon mango peach plum".split(" "));
  static final List<String> NEVER_ADDED =
      List.of("kiwi lime melon orange pear fig date guava papaya quince olive berry".split(" "));

  static long hash64(String text) {
    // FNV-1a, then a mixing step so that similar words land far apart.
    long h = 0xCBF29CE484222325L;
    for (byte b : text.getBytes(StandardCharsets.UTF_8)) {
      h = (h ^ (b & 0xFF)) * 0x100000001B3L;
    }
    h = (h ^ (h >>> 30)) * 0xBF58476D1CE4E5B9L;
    h = (h ^ (h >>> 27)) * 0x94D049BB133111EBL;
    return h ^ (h >>> 31);
  }

  static int[] positions(String word) {
    // k positions from one hash: h1 + i * h2 (double hashing).
    long h = hash64(word);
    long h1 = h & 0xFFFFFFFFL;
    long h2 = (h >>> 32) | 1;
    return IntStream.range(0, HASHES).map(i -> (int) ((h1 + i * h2) % BITS)).toArray();
  }

  public static void main(String[] args) {
    Locale.setDefault(Locale.ROOT);
    int[] bits = new int[BITS];
    for (String word : ADDED) {
      for (int p : positions(word)) {
        bits[p] = 1;
      }
    }
    int ones = IntStream.of(bits).sum();
    System.out.println(
        BITS
            + " bits, "
            + HASHES
            + " hash functions, "
            + ADDED.size()
            + " words added, "
            + ones
            + " bits set");
    List<String> words = new ArrayList<>(ADDED);
    words.addAll(NEVER_ADDED);
    for (String word : words) {
      int[] ps = positions(word);
      int[] zeros = IntStream.of(ps).filter(p -> bits[p] == 0).toArray();
      String answer = ADDED.contains(word) ? "maybe (it was added)" : "maybe: a false positive";
      if (zeros.length > 0) {
        answer = "no (bit " + zeros[0] + " is 0)";
      }
      List<String> shown = IntStream.of(ps).mapToObj(p -> String.format("%2d", p)).toList();
      System.out.printf("  %-7s bits %s   %s%n", word, String.join(", ", shown), answer);
    }
  }
}

In Java: Java has no unsigned long, but multiplication wraps around modulo 2⁶⁴ all the same; >>> shifts in zeros where >> would copy the sign bit.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <cstdint>
#include <format>
#include <print>
#include <string>
#include <string_view>
#include <vector>

constexpr int BITS = 48;
constexpr int HASHES = 3;
constexpr std::string_view ADDED[] = {"apple", "banana", "cherry", "grape",
                                      "lemon", "mango",  "peach",  "plum"};
constexpr std::string_view NEVER_ADDED[] = {
    "kiwi", "lime",  "melon",  "orange", "pear",  "fig",
    "date", "guava", "papaya", "quince", "olive", "berry"};

std::uint64_t hash64(std::string_view text) {
  // FNV-1a, then a mixing step so that similar words land far apart.
  std::uint64_t h = 0xCBF29CE484222325ULL;
  for (const unsigned char byte : text) {
    h = (h ^ byte) * 0x100000001B3ULL;
  }
  h = (h ^ (h >> 30)) * 0xBF58476D1CE4E5B9ULL;
  h = (h ^ (h >> 27)) * 0x94D049BB133111EBULL;
  return h ^ (h >> 31);
}

std::vector<int> positions(std::string_view word) {
  // k positions from one hash: h1 + i * h2 (double hashing).
  const std::uint64_t h = hash64(word);
  const std::uint64_t h1 = h & 0xFFFFFFFFULL, h2 = (h >> 32) | 1;
  std::vector<int> out;
  for (std::uint64_t i = 0; i < HASHES; i++) {
    out.push_back(static_cast<int>((h1 + i * h2) % BITS));
  }
  return out;
}

void check(const std::vector<int> &bits, std::string_view word) {
  const auto ps = positions(word);
  const auto zero =
      std::ranges::find_if(ps, [&](int p) { return bits[p] == 0; });
  std::string answer = std::ranges::contains(ADDED, word)
                           ? "maybe (it was added)"
                           : "maybe: a false positive";
  if (zero != ps.end()) {
    answer = std::format("no (bit {} is 0)", *zero);
  }
  std::string shown;
  for (const int p : ps) {
    shown += std::format("{}{:>2}", shown.empty() ? "" : ", ", p);
  }
  std::println("  {:<7} bits {}   {}", word, shown, answer);
}

int main() {
  std::vector<int> bits(BITS, 0);
  for (const auto word : ADDED) {
    for (const int p : positions(word)) {
      bits[p] = 1;
    }
  }
  std::println("{} bits, {} hash functions, {} words added, {} bits set", BITS,
               HASHES, std::size(ADDED), std::ranges::count(bits, 1));
  for (const auto word : ADDED) {
    check(bits, word);
  }
  for (const auto word : NEVER_ADDED) {
    check(bits, word);
  }
}

In C++: std::uint64_t arithmetic wraps around modulo 2⁶⁴, exactly what FNV-1a needs, and std::ranges::contains, new in C++23, tells an added word from one never added.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

using System.Text;

const int Bits = 48;
const int Hashes = 3;
var added = "apple banana cherry grape lemon mango peach plum".Split(' ');
var neverAdded = "kiwi lime melon orange pear fig date guava papaya quince olive berry".Split(' ');

var bits = new int[Bits];
foreach (var word in added)
{
    foreach (var p in Positions(word))
    {
        bits[p] = 1;
    }
}
Console.WriteLine(
    $"{Bits} bits, {Hashes} hash functions, {added.Length} words added, {bits.Sum()} bits set");
foreach (var word in added.Concat(neverAdded))
{
    var ps = Positions(word);
    var zeros = ps.Where(p => bits[p] == 0).ToArray();
    var answer = added.Contains(word) ? "maybe (it was added)" : "maybe: a false positive";
    if (zeros.Length > 0)
    {
        answer = $"no (bit {zeros[0]} is 0)";
    }
    var shown = string.Join(", ", ps.Select(p => $"{p,2}"));
    Console.WriteLine($"  {word,-7} bits {shown}   {answer}");
}

static ulong Hash64(string text)
{
    // FNV-1a, then a mixing step so that similar words land far apart.
    ulong h = 0xCBF29CE484222325;
    foreach (var b in Encoding.UTF8.GetBytes(text))
    {
        h = (h ^ b) * 0x100000001B3;
    }
    h = (h ^ (h >> 30)) * 0xBF58476D1CE4E5B9;
    h = (h ^ (h >> 27)) * 0x94D049BB133111EB;
    return h ^ (h >> 31);
}

static int[] Positions(string word)
{
    // k positions from one hash: h1 + i * h2 (double hashing).
    var h = Hash64(word);
    var (h1, h2) = (h & 0xFFFFFFFF, (h >> 32) | 1);
    return Enumerable.Range(0, Hashes).Select(i => (int)((h1 + (ulong)i * h2) % Bits)).ToArray();
}

In C#: ulong arithmetic wraps around in C#'s default unchecked context; Hash64 and Positions are static local functions below the top-level statements.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdint.h>
#include <stdio.h>

enum { BITS = 48, HASHES = 3, ADDED = 8, WORDS = 20 };
static const char *const words[WORDS] = {
    "apple", "banana", "cherry", "grape",  "lemon",  "mango", "peach",
    "plum",  "kiwi",   "lime",   "melon",  "orange", "pear",  "fig",
    "date",  "guava",  "papaya", "quince", "olive",  "berry"};

static uint64_t hash64(const char *text) {
  // FNV-1a, then a mixing step so that similar words land far apart.
  uint64_t h = 0xCBF29CE484222325u;
  for (const unsigned char *p = (const unsigned char *)text; *p != '\0'; p++) {
    h = (h ^ *p) * 0x100000001B3u;
  }
  h = (h ^ (h >> 30)) * 0xBF58476D1CE4E5B9u;
  h = (h ^ (h >> 27)) * 0x94D049BB133111EBu;
  return h ^ (h >> 31);
}

static void positions(const char *word, int out[HASHES]) {
  // k positions from one hash: h1 + i * h2 (double hashing).
  const uint64_t h = hash64(word);
  const uint64_t h1 = h & 0xFFFFFFFFu, h2 = (h >> 32) | 1;
  for (int i = 0; i < HASHES; i++) {
    out[i] = (int)((h1 + (uint64_t)i * h2) % BITS);
  }
}

int main(void) {
  int bits[BITS] = {0};
  int ps[HASHES];
  int ones = 0;
  for (int w = 0; w < ADDED; w++) {
    positions(words[w], ps);
    for (int j = 0; j < HASHES; j++) {
      ones += !bits[ps[j]];
      bits[ps[j]] = 1;
    }
  }
  printf("%d bits, %d hash functions, %d words added, %d bits set\n", BITS,
         HASHES, ADDED, ones);
  for (int w = 0; w < WORDS; w++) {
    positions(words[w], ps);
    printf("  %-7s bits", words[w]);
    int zero = -1;
    for (int j = 0; j < HASHES; j++) {
      printf("%s%2d", j == 0 ? " " : ", ", ps[j]);
      if (zero < 0 && bits[ps[j]] == 0) {
        zero = ps[j];
      }
    }
    if (zero >= 0) {
      printf("   no (bit %d is 0)\n", zero);
    } else {
      printf("   %s\n",
             w < ADDED ? "maybe (it was added)" : "maybe: a false positive");
    }
  }
  return 0;
}

In C: The 20 words sit in one array with the 8 added words first, so a word's index says whether it was added; uint64_t wraps around modulo 2⁶⁴.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const BITS = 48;
const HASHES = 3;
const ADDED = ['apple', 'banana', 'cherry', 'grape', 'lemon', 'mango', 'peach', 'plum'];
const NEVER_ADDED = [
    'kiwi', 'lime', 'melon', 'orange', 'pear', 'fig',
    'date', 'guava', 'papaya', 'quince', 'olive', 'berry',
];

/** The low 64 bits of $a * $b, in 16-bit digits: an int product that overflows becomes a float. */
function mul64(int $a, int $b): int
{
    [$result, $carry] = [0, 0];
    for ($k = 0; $k < 4; $k++) {
        $sum = $carry;
        for ($i = 0; $i <= $k; $i++) {
            $sum += (($a >> (16 * $i)) & 0xFFFF) * (($b >> (16 * ($k - $i))) & 0xFFFF);
        }
        $result |= ($sum & 0xFFFF) << (16 * $k);
        $carry = $sum >> 16;
    }
    return $result;
}

/** A right shift that fills with zeros, where >> copies the sign bit. */
function shr(int $x, int $n): int
{
    return ($x >> $n) & (PHP_INT_MAX >> ($n - 1));
}

function hash64(string $text): int
{
    // FNV-1a, then a mixing step so that similar words land far apart.
    $h = (0xCBF29CE4 << 32) | 0x84222325;
    foreach (str_split($text) as $ch) {
        $h = mul64($h ^ ord($ch), 0x100000001B3);
    }
    $h = mul64($h ^ shr($h, 30), (0xBF58476D << 32) | 0x1CE4E5B9);
    $h = mul64($h ^ shr($h, 27), (0x94D049BB << 32) | 0x133111EB);
    return $h ^ shr($h, 31);
}

/** @return list<int> */
function positions(string $word): array
{
    // k positions from one hash: h1 + i * h2 (double hashing).
    $h = hash64($word);
    [$h1, $h2] = [$h & 0xFFFFFFFF, shr($h, 32) | 1];
    return array_map(fn(int $i): int => ($h1 + $i * $h2) % BITS, range(0, HASHES - 1));
}

$bits = array_fill(0, BITS, 0);
foreach (ADDED as $word) {
    foreach (positions($word) as $p) {
        $bits[$p] = 1;
    }
}
printf(
    "%d bits, %d hash functions, %d words added, %d bits set\n",
    BITS,
    HASHES,
    count(ADDED),
    array_sum($bits),
);
foreach ([...ADDED, ...NEVER_ADDED] as $word) {
    $ps = positions($word);
    $zeros = array_values(array_filter($ps, fn(int $p): bool => $bits[$p] === 0));
    $answer = in_array($word, ADDED, true) ? 'maybe (it was added)' : 'maybe: a false positive';
    if ($zeros !== []) {
        $answer = "no (bit {$zeros[0]} is 0)";
    }
    $shown = implode(', ', array_map(fn(int $p): string => sprintf('%2d', $p), $ps));
    printf("  %-7s bits %s   %s\n", $word, $shown, $answer);
}

In PHP: PHP turns an integer product past 2⁶³ into a float, so mul64 multiplies in 16-bit digits and keeps the low 64 bits, and shr shifts in zeros where >> copies the sign bit.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. To run it yourself: php main.php

Rust 1.99 · main.rs

const BITS: usize = 48;
const HASHES: u64 = 3;
const ADDED: &str = "apple banana cherry grape lemon mango peach plum";
const NEVER_ADDED: &str = "kiwi lime melon orange pear fig date guava papaya quince olive berry";

fn hash64(text: &str) -> u64 {
    // FNV-1a, then a mixing step so that similar words land far apart.
    let mut h: u64 = 0xCBF2_9CE4_8422_2325;
    for byte in text.bytes() {
        h = (h ^ u64::from(byte)).wrapping_mul(0x0100_0000_01B3);
    }
    h = (h ^ (h >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    h = (h ^ (h >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    h ^ (h >> 31)
}

fn positions(word: &str) -> Vec<usize> {
    // k positions from one hash: h1 + i * h2 (double hashing).
    let h = hash64(word);
    let (h1, h2) = (h & 0xFFFF_FFFF, (h >> 32) | 1);
    (0..HASHES)
        .map(|i| ((h1 + i * h2) % BITS as u64) as usize)
        .collect()
}

fn main() {
    let added: Vec<&str> = ADDED.split(' ').collect();
    let mut bits = [0u8; BITS];
    for word in &added {
        for p in positions(word) {
            bits[p] = 1;
        }
    }
    let ones = bits.iter().filter(|&&b| b == 1).count();
    let n = added.len();
    println!("{BITS} bits, {HASHES} hash functions, {n} words added, {ones} bits set");
    for word in ADDED.split(' ').chain(NEVER_ADDED.split(' ')) {
        let ps = positions(word);
        let answer = match ps.iter().find(|&&p| bits[p] == 0) {
            Some(zero) => format!("no (bit {zero} is 0)"),
            None if added.contains(&word) => "maybe (it was added)".to_string(),
            None => "maybe: a false positive".to_string(),
        };
        let shown: Vec<String> = ps.iter().map(|p| format!("{p:>2}")).collect();
        println!("  {word:<7} bits {}   {answer}", shown.join(", "));
    }
}

In Rust: wrapping_mul makes the 64-bit wrap-around explicit, where a plain * would stop a debug build with an overflow panic.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const M64 = (1n << 64n) - 1n;
const BITS = 48;
const HASHES = 3;
const ADDED = "apple banana cherry grape lemon mango peach plum".split(" ");
const NEVER_ADDED = "kiwi lime melon orange pear fig date guava papaya quince olive berry".split(
  " ",
);

function hash64(text: string): bigint {
  // FNV-1a, then a mixing step so that similar words land far apart.
  let h = 0xcbf29ce484222325n;
  for (let i = 0; i < text.length; i++) {
    h = ((h ^ BigInt(text.charCodeAt(i))) * 0x100000001b3n) & M64;
  }
  h = ((h ^ (h >> 30n)) * 0xbf58476d1ce4e5b9n) & M64;
  h = ((h ^ (h >> 27n)) * 0x94d049bb133111ebn) & M64;
  return h ^ (h >> 31n);
}

function positions(word: string): number[] {
  // k positions from one hash: h1 + i * h2 (double hashing).
  const h = hash64(word);
  const [h1, h2] = [h & 0xffffffffn, (h >> 32n) | 1n];
  return Array.from({ length: HASHES }, (_, i) => Number((h1 + BigInt(i) * h2) % BigInt(BITS)));
}

const bits: number[] = new Array<number>(BITS).fill(0);
for (const word of ADDED) {
  for (const p of positions(word)) bits[p] = 1;
}
const ones = bits.reduce((sum, b) => sum + b, 0);
console.log(
  `${BITS} bits, ${HASHES} hash functions, ${ADDED.length} words added, ${ones} bits set`,
);
for (const word of [...ADDED, ...NEVER_ADDED]) {
  const ps = positions(word);
  const zeros = ps.filter((p) => bits[p] === 0);
  let answer = ADDED.includes(word) ? "maybe (it was added)" : "maybe: a false positive";
  if (zeros.length > 0) answer = `no (bit ${zeros[0]} is 0)`;
  const shown = ps.map((p) => String(p).padStart(2)).join(", ");
  console.log(`  ${word.padEnd(7)} bits ${shown}   ${answer}`);
}

In TypeScript: The hash is a bigint, because a number holds only 53 bits exactly; bigint literals such as 0x100000001b3n need a target of ES2020 or later.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"slices"
	"strings"
)

const (
	bitCount  = 48
	hashCount = 3
)

var (
	added      = strings.Fields("apple banana cherry grape lemon mango peach plum")
	neverAdded = strings.Fields(
		"kiwi lime melon orange pear fig date guava papaya quince olive berry")
)

func hash64(text string) uint64 {
	// FNV-1a, then a mixing step so that similar words land far apart.
	h := uint64(0xCBF29CE484222325)
	for i := 0; i < len(text); i++ {
		h = (h ^ uint64(text[i])) * 0x100000001B3
	}
	h = (h ^ (h >> 30)) * 0xBF58476D1CE4E5B9
	h = (h ^ (h >> 27)) * 0x94D049BB133111EB
	return h ^ (h >> 31)
}

func positions(word string) []int {
	// k positions from one hash: h1 + i * h2 (double hashing).
	h := hash64(word)
	h1, h2 := h&0xFFFFFFFF, (h>>32)|1
	out := make([]int, hashCount)
	for i := range out {
		out[i] = int((h1 + uint64(i)*h2) % bitCount)
	}
	return out
}

func main() {
	bits := make([]int, bitCount)
	for _, word := range added {
		for _, p := range positions(word) {
			bits[p] = 1
		}
	}
	ones := 0
	for _, b := range bits {
		ones += b
	}
	fmt.Printf("%d bits, %d hash functions, %d words added, %d bits set\n",
		bitCount, hashCount, len(added), ones)
	for _, word := range slices.Concat(added, neverAdded) {
		ps := positions(word)
		answer := "maybe: a false positive"
		if slices.Contains(added, word) {
			answer = "maybe (it was added)"
		}
		if zero := slices.IndexFunc(ps, func(p int) bool { return bits[p] == 0 }); zero >= 0 {
			answer = fmt.Sprintf("no (bit %d is 0)", ps[zero])
		}
		shown := make([]string, len(ps))
		for i, p := range ps {
			shown[i] = fmt.Sprintf("%2d", p)
		}
		fmt.Printf("  %-7s bits %s   %s\n", word, strings.Join(shown, ", "), answer)
	}
}

In Go: uint64 arithmetic wraps around, and slices.IndexFunc returns -1 when every bit is 1, so the answer stays a maybe.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let bitCount = 48
let hashCount = 3
let added = "apple banana cherry grape lemon mango peach plum".split(separator: " ")
let neverAdded = "kiwi lime melon orange pear fig date guava papaya quince olive berry"
  .split(separator: " ")

func hash64(_ text: Substring) -> UInt64 {
  // FNV-1a, then a mixing step so that similar words land far apart.
  var h: UInt64 = 0xCBF2_9CE4_8422_2325
  for byte in text.utf8 {
    h = (h ^ UInt64(byte)) &* 0x100_0000_01B3
  }
  h = (h ^ (h >> 30)) &* 0xBF58_476D_1CE4_E5B9
  h = (h ^ (h >> 27)) &* 0x94D0_49BB_1331_11EB
  return h ^ (h >> 31)
}

func positions(_ word: Substring) -> [Int] {
  // k positions from one hash: h1 + i * h2 (double hashing).
  let h = hash64(word)
  let (h1, h2) = (h & 0xFFFF_FFFF, (h >> 32) | 1)
  return (0..<hashCount).map { Int((h1 + UInt64($0) * h2) % UInt64(bitCount)) }
}

func pad(_ text: String, _ width: Int, left: Bool = false) -> String {
  let fill = String(repeating: " ", count: max(0, width - text.count))
  return left ? fill + text : text + fill
}

var bits = [Int](repeating: 0, count: bitCount)
for word in added {
  for p in positions(word) { bits[p] = 1 }
}
let ones = bits.reduce(0, +)
print("\(bitCount) bits, \(hashCount) hash functions, \(added.count) words added, \(ones) bits set")
for word in added + neverAdded {
  let ps = positions(word)
  var answer = added.contains(word) ? "maybe (it was added)" : "maybe: a false positive"
  if let zero = ps.first(where: { bits[$0] == 0 }) {
    answer = "no (bit \(zero) is 0)"
  }
  let shown = ps.map { pad(String($0), 2, left: true) }.joined(separator: ", ")
  print("  \(pad(String(word), 7)) bits \(shown)   \(answer)")
}

In Swift: &* is the wrapping multiplication, where a plain * would stop the program on overflow. Without Foundation there is no String(format:), so pad lines up the columns.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

M64 = 0xFFFFFFFFFFFFFFFF
BITS = 48
HASHES = 3
ADDED = %w[apple banana cherry grape lemon mango peach plum].freeze
NEVER_ADDED = %w[kiwi lime melon orange pear fig date guava papaya quince olive berry].freeze

def hash64(text)
  # FNV-1a, then a mixing step so that similar words land far apart.
  h = 0xCBF29CE484222325
  text.each_byte { |byte| h = ((h ^ byte) * 0x100000001B3) & M64 }
  h = ((h ^ (h >> 30)) * 0xBF58476D1CE4E5B9) & M64
  h = ((h ^ (h >> 27)) * 0x94D049BB133111EB) & M64
  h ^ (h >> 31)
end

def positions(word)
  # k positions from one hash: h1 + i * h2 (double hashing).
  h = hash64(word)
  h1 = h & 0xFFFFFFFF
  h2 = (h >> 32) | 1
  Array.new(HASHES) { |i| (h1 + (i * h2)) % BITS }
end

bits = Array.new(BITS, 0)
ADDED.each { |word| positions(word).each { |p| bits[p] = 1 } }
puts "#{BITS} bits, #{HASHES} hash functions, #{ADDED.size} words added, #{bits.sum} bits set"
(ADDED + NEVER_ADDED).each do |word|
  ps = positions(word)
  zero = ps.find { |p| bits[p].zero? }
  answer = ADDED.include?(word) ? 'maybe (it was added)' : 'maybe: a false positive'
  answer = "no (bit #{zero} is 0)" if zero
  puts "  #{word.ljust(7)} bits #{ps.map { |p| p.to_s.rjust(2) }.join(', ')}   #{answer}"
end

In Ruby: Ruby's integers grow without limit, so every product is masked back to 64 bits; find returns nil when no bit is 0, and 0 itself is true in Ruby, so position 0 still counts as found.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

const val BITS = 48
const val HASHES = 3
val added = "apple banana cherry grape lemon mango peach plum".split(" ")
val neverAdded = "kiwi lime melon orange pear fig date guava papaya quince olive berry".split(" ")

fun hash64(text: String): ULong {
    // FNV-1a, then a mixing step so that similar words land far apart.
    var h = 0xCBF29CE484222325uL
    for (byte in text.encodeToByteArray()) {
        h = (h xor byte.toUByte().toULong()) * 0x100000001B3uL
    }
    h = (h xor (h shr 30)) * 0xBF58476D1CE4E5B9uL
    h = (h xor (h shr 27)) * 0x94D049BB133111EBuL
    return h xor (h shr 31)
}

fun positions(word: String): List<Int> {
    // k positions from one hash: h1 + i * h2 (double hashing).
    val h = hash64(word)
    val h1 = h and 0xFFFFFFFFuL
    val h2 = (h shr 32) or 1uL
    return List(HASHES) { i -> ((h1 + i.toULong() * h2) % BITS.toULong()).toInt() }
}

fun main() {
    val bits = IntArray(BITS)
    for (word in added) {
        for (p in positions(word)) bits[p] = 1
    }
    println("$BITS bits, $HASHES hash functions, ${added.size} words added, ${bits.sum()} bits set")
    for (word in added + neverAdded) {
        val ps = positions(word)
        val zero = ps.firstOrNull { bits[it] == 0 }
        var answer = if (word in added) "maybe (it was added)" else "maybe: a false positive"
        if (zero != null) answer = "no (bit $zero is 0)"
        val shown = ps.joinToString(", ") { it.toString().padStart(2) }
        println("  ${word.padEnd(7)} bits $shown   $answer")
    }
}

In Kotlin: ULong gives unsigned 64-bit arithmetic that wraps around, and its shr shifts in zeros; toUByte reads each byte of encodeToByteArray without its sign.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

import 'dart:convert';

const bitCount = 48;
const hashCount = 3;
final added = 'apple banana cherry grape lemon mango peach plum'.split(' ');
final neverAdded =
    'kiwi lime melon orange pear fig date guava papaya quince olive berry'
        .split(' ');

int hash64(String text) {
  // FNV-1a, then a mixing step so that similar words land far apart.
  var h = 0xCBF29CE484222325;
  for (final byte in utf8.encode(text)) {
    h = (h ^ byte) * 0x100000001B3;
  }
  h = (h ^ (h >>> 30)) * 0xBF58476D1CE4E5B9;
  h = (h ^ (h >>> 27)) * 0x94D049BB133111EB;
  return h ^ (h >>> 31);
}

List<int> positions(String word) {
  // k positions from one hash: h1 + i * h2 (double hashing).
  final h = hash64(word);
  final (h1, h2) = (h & 0xFFFFFFFF, (h >>> 32) | 1);
  return [for (var i = 0; i < hashCount; i++) (h1 + i * h2) % bitCount];
}

void main() {
  final bits = List.filled(bitCount, 0);
  for (final word in added) {
    for (final p in positions(word)) {
      bits[p] = 1;
    }
  }
  final ones = bits.reduce((a, b) => a + b);
  print(
    '$bitCount bits, $hashCount hash functions, ${added.length} words added, $ones bits set',
  );
  for (final word in [...added, ...neverAdded]) {
    final ps = positions(word);
    final zero = ps.where((p) => bits[p] == 0).firstOrNull;
    var answer = added.contains(word)
        ? 'maybe (it was added)'
        : 'maybe: a false positive';
    if (zero != null) answer = 'no (bit $zero is 0)';
    final shown = ps.map((p) => '$p'.padLeft(2)).join(', ');
    print('  ${word.padRight(7)} bits $shown   $answer');
  }
}

In Dart: Dart's int has 64 bits on the VM and in WebAssembly and its products wrap around; >>> is the shift that fills with zeros.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart