Hashing: static, extendible and linear

Python 3.14 · main.py

# Eight hash values into an extendible hash index with buckets of 2 keys.
from dataclasses import dataclass, field

CAPACITY = 2


@dataclass
class Bucket:
    name: str
    depth: int  # local depth: the last bits all its keys share
    keys: list[int] = field(default_factory=list)


class Index:
    def __init__(self) -> None:
        self.depth = 0  # global depth: the last bits that choose a slot
        self.slots = [Bucket("A", 0)]
        self.made = 1

    def insert(self, h: int) -> None:
        while True:
            bucket = self.slots[h & ((1 << self.depth) - 1)]
            if len(bucket.keys) < CAPACITY:
                bucket.keys.append(h)
                return
            if bucket.depth == self.depth:
                self.slots += self.slots  # slot i + 2^d points where slot i does
                self.depth += 1
            self.split(bucket)

    def split(self, bucket: Bucket) -> None:
        bit = 1 << bucket.depth
        bucket.depth += 1
        new = Bucket(
            "ABCDEFGH"[self.made], bucket.depth, [k for k in bucket.keys if k & bit]
        )
        self.made += 1
        bucket.keys = [k for k in bucket.keys if not k & bit]
        for i, b in enumerate(self.slots):
            if b is bucket and i & bit:
                self.slots[i] = new

    def show(self) -> None:
        for i, b in enumerate(self.slots):
            bits = format(i, f"0{self.depth}b") if self.depth else "-"
            print(f"  {bits} -> {b.name} (local depth {b.depth}): {b.keys}")


index = Index()
for h in [12, 5, 17, 6, 27, 9, 20, 15]:
    print(f"insert {h} = {h:05b}")
    index.insert(h)
    index.show()

In Python: self.slots += self.slots appends the list to itself, so each new slot refers to the same Bucket object as its twin.

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
const CAPACITY = 2;

class Bucket {
  constructor(name, depth, keys = []) {
    this.name = name;
    this.depth = depth; // local depth: the last bits all its keys share
    this.keys = keys;
  }
}

class Index {
  depth = 0; // global depth: the last bits that choose a slot
  slots = [new Bucket("A", 0)];
  made = 1;

  insert(h) {
    for (;;) {
      const bucket = this.slots[h & ((1 << this.depth) - 1)];
      if (bucket.keys.length < CAPACITY) {
        bucket.keys.push(h);
        return;
      }
      if (bucket.depth === this.depth) {
        this.slots = [...this.slots, ...this.slots]; // slot i + 2^d points where slot i does
        this.depth += 1;
      }
      this.split(bucket);
    }
  }

  split(bucket) {
    const bit = 1 << bucket.depth;
    bucket.depth += 1;
    const fresh = new Bucket(
      "ABCDEFGH"[this.made],
      bucket.depth,
      bucket.keys.filter((k) => k & bit),
    );
    this.made += 1;
    bucket.keys = bucket.keys.filter((k) => !(k & bit));
    this.slots = this.slots.map((b, i) => (b === bucket && i & bit ? fresh : b));
  }

  show() {
    this.slots.forEach((b, i) => {
      const bits = this.depth ? i.toString(2).padStart(this.depth, "0") : "-";
      console.log(`  ${bits} -> ${b.name} (local depth ${b.depth}): [${b.keys.join(", ")}]`);
    });
  }
}

const index = new Index();
for (const h of [12, 5, 17, 6, 27, 9, 20, 15]) {
  console.log(`insert ${h} = ${h.toString(2).padStart(5, "0")}`);
  index.insert(h);
  index.show();
}

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.util.ArrayList;
import java.util.List;

public class Main {
  // Eight hash values into an extendible hash index with buckets of 2 keys.
  static final int CAPACITY = 2;

  // depth is the local depth: the last bits all the bucket's keys share.
  record Bucket(char name, int depth, List<Integer> keys) {}

  static int depth = 0; // global depth: the last bits that choose a slot
  static List<Bucket> slots = new ArrayList<>(List.of(new Bucket('A', 0, new ArrayList<>())));
  static int made = 1;

  static String bits(int value, int width) {
    String b = Integer.toBinaryString(value);
    return "0".repeat(width - b.length()) + b;
  }

  static void insert(int h) {
    while (true) {
      Bucket bucket = slots.get(h & ((1 << depth) - 1));
      if (bucket.keys().size() < CAPACITY) {
        bucket.keys().add(h);
        return;
      }
      if (bucket.depth() == depth) {
        slots.addAll(List.copyOf(slots)); // slot i + 2^d points where slot i does
        depth++;
      }
      split(bucket);
    }
  }

  static void split(Bucket bucket) {
    int bit = 1 << bucket.depth();
    Bucket kept = new Bucket(bucket.name(), bucket.depth() + 1, new ArrayList<>());
    Bucket fresh = new Bucket((char) ('A' + made++), bucket.depth() + 1, new ArrayList<>());
    for (int k : bucket.keys()) {
      ((k & bit) != 0 ? fresh : kept).keys().add(k);
    }
    for (int i = 0; i < slots.size(); i++) {
      if (slots.get(i) == bucket) {
        slots.set(i, (i & bit) != 0 ? fresh : kept);
      }
    }
  }

  public static void main(String[] args) {
    for (int h : new int[] {12, 5, 17, 6, 27, 9, 20, 15}) {
      System.out.println("insert " + h + " = " + bits(h, 5));
      insert(h);
      for (int i = 0; i < slots.size(); i++) {
        Bucket b = slots.get(i);
        String slot = depth == 0 ? "-" : bits(i, depth);
        System.out.println(
            "  " + slot + " -> " + b.name() + " (local depth " + b.depth() + "): " + b.keys());
      }
    }
  }
}

In Java: A record cannot change, so a split builds two new buckets and points every slot of the old one at the right half.

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 <format>
#include <print>
#include <vector>

// Eight hash values into an extendible hash index with buckets of 2 keys.
constexpr std::size_t capacity = 2;

struct Bucket {
  char name;
  int depth; // local depth: the last bits all its keys share
  std::vector<int> keys;
};

std::vector<Bucket> buckets{{'A', 0, {}}};
std::vector<std::size_t> slots{0}; // each slot holds the position of its bucket
int depth = 0; // global depth: the last bits that choose a slot

void split(std::size_t b) {
  int bit = 1 << buckets[b].depth++;
  Bucket fresh{static_cast<char>('A' + buckets.size()), buckets[b].depth, {}};
  std::vector<int> kept;
  for (int k : buckets[b].keys)
    ((k & bit) ? fresh.keys : kept).push_back(k);
  buckets[b].keys = kept;
  for (std::size_t i = 0; i < slots.size(); ++i)
    if (slots[i] == b && (i & bit))
      slots[i] = buckets.size();
  buckets.push_back(fresh);
}

void insert(int h) {
  for (;;) {
    std::size_t b = slots[h & ((1 << depth) - 1)];
    if (buckets[b].keys.size() < capacity) {
      buckets[b].keys.push_back(h);
      return;
    }
    if (buckets[b].depth == depth) {
      // Slot i + 2^d points where slot i does.
      std::vector<std::size_t> copy = slots;
      slots.insert(slots.end(), copy.begin(), copy.end());
      ++depth;
    }
    split(b);
  }
}

int main() {
  for (int h : {12, 5, 17, 6, 27, 9, 20, 15}) {
    std::println("insert {} = {:05b}", h, h);
    insert(h);
    for (std::size_t i = 0; i < slots.size(); ++i) {
      const Bucket &b = buckets[slots[i]];
      auto bits = depth ? std::format("{:0{}b}", i, depth) : std::string("-");
      std::println("  {} -> {} (local depth {}): {}", bits, b.name, b.depth,
                   b.keys);
    }
  }
}

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
const int Capacity = 2;
int depth = 0; // global depth: the last bits that choose a slot
List<Bucket> slots = [new Bucket('A', 0)];
int made = 1;

foreach (int h in (int[])[12, 5, 17, 6, 27, 9, 20, 15])
{
    Console.WriteLine($"insert {h} = {Bits(h, 5)}");
    Insert(h);
    for (int i = 0; i < slots.Count; i++)
    {
        Bucket b = slots[i];
        string slot = depth == 0 ? "-" : Bits(i, depth);
        string keys = string.Join(", ", b.Keys);
        Console.WriteLine($"  {slot} -> {b.Name} (local depth {b.Depth}): [{keys}]");
    }
}

static string Bits(int value, int width) => Convert.ToString(value, 2).PadLeft(width, '0');

void Insert(int h)
{
    while (true)
    {
        Bucket bucket = slots[h & ((1 << depth) - 1)];
        if (bucket.Keys.Count < Capacity)
        {
            bucket.Keys.Add(h);
            return;
        }
        if (bucket.Depth == depth)
        {
            slots.AddRange([.. slots]); // slot i + 2^d points where slot i does
            depth++;
        }
        Split(bucket);
    }
}

void Split(Bucket bucket)
{
    int bit = 1 << bucket.Depth++;
    var fresh = new Bucket((char)('A' + made++), bucket.Depth);
    fresh.Keys.AddRange(bucket.Keys.Where(k => (k & bit) != 0));
    bucket.Keys.RemoveAll(k => (k & bit) != 0);
    for (int i = 0; i < slots.Count; i++)
    {
        if (slots[i] == bucket && (i & bit) != 0)
            slots[i] = fresh;
    }
}

class Bucket(char name, int depth)
{
    public char Name { get; } = name;

    // Local depth: the last bits all its keys share.
    public int Depth { get; set; } = depth;
    public List<int> Keys { get; } = [];
}

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 <stdio.h>

// Eight hash values into an extendible hash index with buckets of 2 keys.
enum { CAPACITY = 2 };
typedef struct {
  int depth; // local depth: the last bits all its keys share
  int keys[CAPACITY], n;
} Bucket;

static Bucket buckets[8];
static int made = 1, nslots = 1, slots[16];
static int depth = 0; // global depth: the last bits that choose a slot

static const char *bits(int value, int width) {
  static char out[8];
  for (int j = 0; j < width; j++)
    out[j] = (char)('0' + (value >> (width - 1 - j) & 1));
  out[width] = '\0';
  return out;
}

static void split(int b) {
  Bucket *old = &buckets[b], *fresh = &buckets[made];
  int bit = 1 << old->depth++, kept = 0;
  fresh->depth = old->depth;
  for (int i = 0; i < old->n; i++)
    if (old->keys[i] & bit)
      fresh->keys[fresh->n++] = old->keys[i];
    else
      old->keys[kept++] = old->keys[i];
  old->n = kept;
  for (int i = 0; i < nslots; i++)
    if (slots[i] == b && (i & bit))
      slots[i] = made;
  made++;
}

static void insert(int h) {
  for (;;) {
    int b = slots[h & ((1 << depth) - 1)];
    if (buckets[b].n < CAPACITY) {
      buckets[b].keys[buckets[b].n++] = h;
      return;
    }
    if (buckets[b].depth == depth) {
      for (int i = 0; i < nslots; i++) // slot i + 2^d points where slot i does
        slots[nslots + i] = slots[i];
      nslots *= 2;
      depth++;
    }
    split(b);
  }
}

int main(void) {
  static const int keys[] = {12, 5, 17, 6, 27, 9, 20, 15};
  for (int k = 0; k < 8; k++) {
    printf("insert %d = %s\n", keys[k], bits(keys[k], 5));
    insert(keys[k]);
    for (int i = 0; i < nslots; i++) {
      const Bucket *to = &buckets[slots[i]];
      printf("  %s -> %c (local depth %d): [", depth ? bits(i, depth) : "-",
             'A' + slots[i], to->depth);
      for (int j = 0; j < to->n; j++)
        printf(j ? ", %d" : "%d", to->keys[j]);
      printf("]\n");
    }
  }
}

In C: Buckets are named by their position, A for the first, and the directory holds those positions, so a split repoints slots by number.

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);

// Eight hash values into an extendible hash index with buckets of 2 keys.
const CAPACITY = 2;

final class Bucket
{
    /** @param list<int> $keys */
    public function __construct(
        public string $name,
        public int $depth, // local depth: the last bits all its keys share
        public array $keys = [],
    ) {}
}

final class HashIndex
{
    /** @param list<Bucket> $slots */
    public function __construct(
        public int $depth = 0, // global depth: the last bits that choose a slot
        public array $slots = [new Bucket('A', 0)],
        public int $made = 1,
    ) {}

    public function insert(int $h): void
    {
        while (true) {
            $bucket = $this->slots[$h & ((1 << $this->depth) - 1)];
            if (count($bucket->keys) < CAPACITY) {
                $bucket->keys[] = $h;
                return;
            }
            if ($bucket->depth === $this->depth) {
                // Slot i + 2^d points where slot i does.
                $this->slots = [...$this->slots, ...$this->slots];
                $this->depth++;
            }
            $this->split($bucket);
        }
    }

    private function split(Bucket $bucket): void
    {
        $bit = 1 << $bucket->depth++;
        $fresh = new Bucket('ABCDEFGH'[$this->made++], $bucket->depth);
        $moves = fn(int $k): bool => ($k & $bit) !== 0;
        $fresh->keys = array_values(array_filter($bucket->keys, $moves));
        $bucket->keys = array_values(array_filter($bucket->keys, fn(int $k): bool => !$moves($k)));
        foreach ($this->slots as $i => $b) {
            if ($b === $bucket && ($i & $bit) !== 0) {
                $this->slots[$i] = $fresh;
            }
        }
    }
}

$index = new HashIndex();
foreach ([12, 5, 17, 6, 27, 9, 20, 15] as $h) {
    echo 'insert ' . $h . ' = ' . sprintf('%05b', $h) . "\n";
    $index->insert($h);
    foreach ($index->slots as $i => $b) {
        $slot = $index->depth === 0 ? '-' : sprintf("%0{$index->depth}b", $i);
        $keys = implode(', ', $b->keys);
        echo "  {$slot} -> {$b->name} (local depth {$b->depth}): [{$keys}]\n";
    }
}

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

// Eight hash values into an extendible hash index with buckets of 2 keys.
const CAPACITY: usize = 2;

// Buckets are named A, B, C … in the order they are made.
#[derive(Default)]
struct Bucket {
    depth: u32, // local depth: the last bits all its keys share
    keys: Vec<u32>,
}

#[derive(Default)]
struct Index {
    depth: u32,        // global depth: the last bits that choose a slot
    slots: Vec<usize>, // the position of each slot's bucket in buckets
    buckets: Vec<Bucket>,
}

impl Index {
    fn insert(&mut self, h: u32) {
        loop {
            let b = self.slots[(h & ((1 << self.depth) - 1)) as usize];
            if self.buckets[b].keys.len() < CAPACITY {
                self.buckets[b].keys.push(h);
                return;
            }
            if self.buckets[b].depth == self.depth {
                self.slots.extend_from_within(..); // slot i + 2^d points where slot i does
                self.depth += 1;
            }
            self.split(b);
        }
    }

    fn split(&mut self, b: usize) {
        let bit = 1 << self.buckets[b].depth;
        self.buckets[b].depth += 1;
        let depth = self.buckets[b].depth;
        let (keys, kept) = self.buckets[b].keys.iter().partition(|&&k| k & bit != 0);
        self.buckets[b].keys = kept;
        let fresh = self.buckets.len();
        self.buckets.push(Bucket { depth, keys });
        for (i, slot) in self.slots.iter_mut().enumerate() {
            if *slot == b && i & bit as usize != 0 {
                *slot = fresh;
            }
        }
    }
}

fn main() {
    let mut index = Index::default();
    index.slots.push(0);
    index.buckets.push(Bucket::default());
    for h in [12, 5, 17, 6, 27, 9, 20, 15] {
        println!("insert {h} = {h:05b}");
        index.insert(h);
        let d = index.depth as usize;
        for (i, &b) in index.slots.iter().enumerate() {
            let bits = match d {
                0 => "-".to_string(),
                _ => format!("{i:0d$b}"),
            };
            let (name, Bucket { depth, keys }) = (char::from(b'A' + b as u8), &index.buckets[b]);
            println!("  {bits} -> {name} (local depth {depth}): {keys:?}");
        }
    }
}

In Rust: The directory holds positions in buckets rather than references, because two slots share one bucket and Rust gives a value one owner.

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
const CAPACITY = 2;

class Bucket {
  name: string;
  depth: number; // local depth: the last bits all its keys share
  keys: number[];

  constructor(name: string, depth: number, keys: number[] = []) {
    this.name = name;
    this.depth = depth;
    this.keys = keys;
  }
}

class HashIndex {
  depth = 0; // global depth: the last bits that choose a slot
  slots: Bucket[] = [new Bucket("A", 0)];
  made = 1;

  insert(h: number): void {
    for (;;) {
      const bucket = this.slots[h & ((1 << this.depth) - 1)];
      if (bucket.keys.length < CAPACITY) {
        bucket.keys.push(h);
        return;
      }
      if (bucket.depth === this.depth) {
        this.slots = [...this.slots, ...this.slots]; // slot i + 2^d points where slot i does
        this.depth += 1;
      }
      this.split(bucket);
    }
  }

  split(bucket: Bucket): void {
    const bit = 1 << bucket.depth;
    bucket.depth += 1;
    const moved = bucket.keys.filter((k) => (k & bit) !== 0);
    const fresh = new Bucket("ABCDEFGH"[this.made], bucket.depth, moved);
    this.made += 1;
    bucket.keys = bucket.keys.filter((k) => (k & bit) === 0);
    this.slots = this.slots.map((b, i) => (b === bucket && (i & bit) !== 0 ? fresh : b));
  }

  show(): void {
    this.slots.forEach((b, i) => {
      const bits = this.depth ? i.toString(2).padStart(this.depth, "0") : "-";
      console.log(`  ${bits} -> ${b.name} (local depth ${b.depth}): [${b.keys.join(", ")}]`);
    });
  }
}

const index = new HashIndex();
for (const h of [12, 5, 17, 6, 27, 9, 20, 15]) {
  console.log(`insert ${h} = ${h.toString(2).padStart(5, "0")}`);
  index.insert(h);
  index.show();
}

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"
	"strings"
)

// Eight hash values into an extendible hash index with buckets of 2 keys.
const capacity = 2

type bucket struct {
	name  byte
	depth int // local depth: the last bits all its keys share
	keys  []int
}

var (
	depth = 0 // global depth: the last bits that choose a slot
	slots = []*bucket{{name: 'A'}}
	made  = 1
)

func insert(h int) {
	for {
		b := slots[h&(1<<depth-1)]
		if len(b.keys) < capacity {
			b.keys = append(b.keys, h)
			return
		}
		if b.depth == depth {
			slots = append(slots, slots...) // slot i + 2^d points where slot i does
			depth++
		}
		split(b)
	}
}

func split(b *bucket) {
	bit := 1 << b.depth
	b.depth++
	fresh := &bucket{name: byte('A' + made), depth: b.depth}
	made++
	var kept []int
	for _, k := range b.keys {
		if k&bit != 0 {
			fresh.keys = append(fresh.keys, k)
		} else {
			kept = append(kept, k)
		}
	}
	b.keys = kept
	for i, s := range slots {
		if s == b && i&bit != 0 {
			slots[i] = fresh
		}
	}
}

func main() {
	for _, h := range []int{12, 5, 17, 6, 27, 9, 20, 15} {
		fmt.Printf("insert %d = %05b\n", h, h)
		insert(h)
		for i, b := range slots {
			bits := "-"
			if depth > 0 {
				bits = fmt.Sprintf("%0*b", depth, i)
			}
			keys := strings.ReplaceAll(fmt.Sprint(b.keys), " ", ", ")
			fmt.Printf("  %s -> %c (local depth %d): %s\n", bits, b.name, b.depth, keys)
		}
	}
}

In Go: append(slots, slots...) doubles the slice of pointers, so both slots of each pair point to the same bucket.

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
let capacity = 2

struct Bucket {
  let name: Character
  var depth: Int  // local depth: the last bits all its keys share
  var keys: [Int] = []
}

var depth = 0  // global depth: the last bits that choose a slot
var buckets = [Bucket(name: "A", depth: 0)]
var slots = [0]  // each slot holds the position of its bucket

func bits(_ value: Int, width: Int) -> String {
  let digits = String(value, radix: 2)
  return String(repeating: "0", count: width - digits.count) + digits
}

func insert(_ h: Int) {
  while true {
    let b = slots[h & ((1 << depth) - 1)]
    if buckets[b].keys.count < capacity {
      buckets[b].keys.append(h)
      return
    }
    if buckets[b].depth == depth {
      slots += slots  // slot i + 2^d points where slot i does
      depth += 1
    }
    split(b)
  }
}

func split(_ b: Int) {
  let bit = 1 << buckets[b].depth
  buckets[b].depth += 1
  let letters = Array("ABCDEFGH")
  var fresh = Bucket(name: letters[buckets.count], depth: buckets[b].depth)
  fresh.keys = buckets[b].keys.filter { $0 & bit != 0 }
  buckets[b].keys = buckets[b].keys.filter { $0 & bit == 0 }
  for i in slots.indices where slots[i] == b && i & bit != 0 {
    slots[i] = buckets.count
  }
  buckets.append(fresh)
}

for h in [12, 5, 17, 6, 27, 9, 20, 15] {
  print("insert \(h) = \(bits(h, width: 5))")
  insert(h)
  for (i, b) in slots.enumerated() {
    let slot = depth == 0 ? "-" : bits(i, width: depth)
    let keys = buckets[b].keys.map(String.init).joined(separator: ", ")
    print("  \(slot) -> \(buckets[b].name) (local depth \(buckets[b].depth)): [\(keys)]")
  }
}

In Swift: Bucket is a struct, a value, so the directory holds positions in buckets and a split changes the bucket in place by its position.

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

# Eight hash values into an extendible hash index with buckets of 2 keys.
CAPACITY = 2

# depth is the local depth: the last bits all the bucket's keys share.
Bucket = Struct.new(:name, :depth, :keys)

# The directory of an extendible hash index.
class HashIndex
  def initialize
    @depth = 0 # global depth: the last bits that choose a slot
    @slots = [Bucket.new('A', 0, [])]
    @made = 1
  end

  def insert(value)
    bucket = slot_of(value)
    while bucket.keys.size >= CAPACITY
      double if bucket.depth == @depth
      split(bucket)
      bucket = slot_of(value)
    end
    bucket.keys << value
  end

  def show
    @slots.each_with_index do |bucket, i|
      slot = @depth.zero? ? '-' : format("%0#{@depth}b", i)
      puts "  #{slot} -> #{bucket.name} (local depth #{bucket.depth}): #{bucket.keys}"
    end
  end

  private

  def slot_of(value)
    @slots[value & ((1 << @depth) - 1)]
  end

  def double
    @slots += @slots # slot i + 2^d points where slot i does
    @depth += 1
  end

  def split(bucket)
    bit = 1 << bucket.depth
    bucket.depth += 1
    moved, bucket.keys = bucket.keys.partition { |key| key.anybits?(bit) }
    fresh = Bucket.new('ABCDEFGH'[@made], bucket.depth, moved)
    @made += 1
    repoint(bucket, fresh, bit)
  end

  def repoint(bucket, fresh, bit)
    @slots.each_index { |i| @slots[i] = fresh if @slots[i].equal?(bucket) && i.anybits?(bit) }
  end
end

index = HashIndex.new
[12, 5, 17, 6, 27, 9, 20, 15].each do |value|
  puts "insert #{value} = #{format('%05b', value)}"
  index.insert(value)
  index.show
end

In Ruby: RuboCop keeps methods small, so split hands the slot update and its message to repoint and report.

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
const val CAPACITY = 2

// depth is the local depth: the last bits all the bucket's keys share.
class Bucket(
    val name: Char,
    var depth: Int,
    var keys: List<Int> = emptyList(),
)

var depth = 0 // global depth: the last bits that choose a slot
val slots = mutableListOf(Bucket('A', 0))
var made = 1

fun insert(h: Int) {
    while (true) {
        val bucket = slots[h and ((1 shl depth) - 1)]
        if (bucket.keys.size < CAPACITY) {
            bucket.keys += h
            return
        }
        if (bucket.depth == depth) {
            slots += slots.toList() // slot i + 2^d points where slot i does
            depth++
        }
        split(bucket)
    }
}

fun split(bucket: Bucket) {
    val bit = 1 shl bucket.depth
    bucket.depth++
    val (moved, kept) = bucket.keys.partition { it and bit != 0 }
    val fresh = Bucket('A' + made++, bucket.depth, moved)
    bucket.keys = kept
    for (i in slots.indices) {
        if (slots[i] === bucket && i and bit != 0) slots[i] = fresh
    }
}

fun main() {
    for (h in listOf(12, 5, 17, 6, 27, 9, 20, 15)) {
        println("insert $h = ${h.toString(2).padStart(5, '0')}")
        insert(h)
        slots.forEachIndexed { i, b ->
            val slot = if (depth == 0) "-" else i.toString(2).padStart(depth, '0')
            println("  $slot -> ${b.name} (local depth ${b.depth}): ${b.keys}")
        }
    }
}

In Kotlin: keys is a read-only List that a split replaces, so bucket.keys += h builds a new list with the key added.

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

// Eight hash values into an extendible hash index with buckets of 2 keys.
const capacity = 2;

// depth is the local depth: the last bits all the bucket's keys share.
class Bucket {
  Bucket(this.name, this.depth, [List<int>? keys]) : keys = keys ?? [];
  final String name;
  int depth;
  List<int> keys;
}

var depth = 0; // global depth: the last bits that choose a slot
var slots = [Bucket('A', 0)];
var made = 1;

void insert(int h) {
  while (true) {
    final bucket = slots[h & ((1 << depth) - 1)];
    if (bucket.keys.length < capacity) {
      bucket.keys.add(h);
      return;
    }
    if (bucket.depth == depth) {
      slots = [...slots, ...slots]; // slot i + 2^d points where slot i does
      depth++;
    }
    split(bucket);
  }
}

void split(Bucket bucket) {
  final bit = 1 << bucket.depth++;
  final moved = bucket.keys.where((k) => k & bit != 0).toList();
  final fresh = Bucket('ABCDEFGH'[made++], bucket.depth, moved);
  bucket.keys = bucket.keys.where((k) => k & bit == 0).toList();
  for (var i = 0; i < slots.length; i++) {
    if (identical(slots[i], bucket) && i & bit != 0) slots[i] = fresh;
  }
}

void main() {
  for (final h in [12, 5, 17, 6, 27, 9, 20, 15]) {
    print('insert $h = ${h.toRadixString(2).padLeft(5, '0')}');
    insert(h);
    for (final (i, b) in slots.indexed) {
      final slot = depth == 0 ? '-' : i.toRadixString(2).padLeft(depth, '0');
      print('  $slot -> ${b.name} (local depth ${b.depth}): ${b.keys}');
    }
  }
}

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