elastic

A Kotlin Multiplatform library of high-performance hash-table data structures.

The library pursues two deliberately separate goals:

1. A provable speed win — primitive-specialized, SwissTable-style open-addressing maps (leading with Long → V) that are faster and far more compact than the platform standard-library maps, by eliminating key and value boxing.
2. A research contribution — the first credible JVM/Kotlin clean-room implementation of Elastic Hashing and Funnel Hashing (Farach-Colton, Krapivin & Kuszmaul, arXiv:2501.02305, 2025), positioned not as a general-purpose fast map but as bounded-worst-case specialists for very high load factors (≈0.99).

The baseline this project commits to beating is the platform standard library (boxed java.util.HashMap; the Kotlin/Native HashMap) — not best-in-class native maps like abseil or Rust hashbrown, which are out of reach from common Kotlin. The win comes from boxing elimination and is gated on primitive keys.

Targets: JVM and Kotlin/Native (macosArm64, linuxX64, linuxArm64, mingwX64, iosArm64, iosSimulatorArm64). JS and Wasm are deferred.

Status

The roadmap ships the speed win first and frames the namesake structures honestly. See docs/project.md and the phased implementation plan for detail.

• Phase 0 — complete. Foundation, two-tier benchmark harness, and the (n, δ) sizing formulas from the paper, cross-checked against an external oracle.

• Phase 1 — complete. Two primitive-keyed maps shipped:

  • SwissLongMap<V> — a SwissTable/hashbrown-style Long → V map (no key boxing; object values).
  • LongLongMap — the fully primitive Long → Long specialization (neither key nor value boxed).

  Measured against HashMap<Long, Long>, LongLongMap retains ~4.7× less heap and is ~2× faster on random-access lookup at 1M entries (SwissLongMap: ~2.3× less heap).

• Phase 2 — complete. FunnelLongMap<V> — a clean-room funnel-hashing map (the first faithful JVM/KMP port), positioned as a bounded-worst-case specialist for very high load factors.

• Phase 3 — complete. ElasticLongMap<V> — the non-greedy namesake, with the paper's three-case insertion and an O(1)-amortized insertion probe bound asserted in CI.

• Phase 4 — complete. SingleWriterSwissLongMap<V> — the single-writer / multi-reader variant with lock-free, bounded-step readers; linearizable key-addressed operations, verified with Lincheck.

• Phase 5 — complete. The Swiss specialization matrix and interop views:

  • The 2×4 matrix — keys {Long, Int} × values {V, Long, Int, Double} — generated from templates by the codegen module: SwissIntMap<V>, LongIntMap, LongDoubleMap, IntIntMap, IntLongMap, IntDoubleMap join the Phase-1 pair, which is now generated from the same templates. A drift gate in check keeps the checked-in sources honest.
  • Opt-in boxed MutableMap views: asMutableMap() on the boxed-value maps (fail-fast iteration) and on SingleWriterSwissLongMap (weakly consistent snapshot iteration).

• Phase 6 — planned. Validation and release: the full benchmark matrix on pinned hardware, reproducibility metadata, and Maven Central publication.

Modules

• elastic — the Kotlin Multiplatform library; public API in io.spine.elastic.
• benchmarks — the portable benchmark harness (kotlinx-benchmark, JVM + Native).
• benchmarks-jvm — raw-JMH JVM benchmarks (multi-threaded read-scaling and mixed-load runs the portable harness cannot express).
• codegen — the template-substitution generator behind the specialization matrix; ./gradlew :elastic:generateSwissMaps regenerates the checked-in sources, and :elastic:verifyGeneratedSwissMaps (part of check) fails the build on drift.

Submodules

• config — shared repository configuration.