Collections: Hash Maps (Map, LinearMap)

Bifurcan's hash map implementations are built on CHAMP (Compressed Hash-Array Mapped Prefix-tree) tries, a modern design that offers excellent performance across a range of operations.

Map (Immutable)

The immutable Map is a high-performance hash map that offers several key advantages:

  • Customizable Equality: You can provide custom hash and equality functions, allowing the map to work with objects that have non-standard equality semantics.
  • Canonical Structure: Equivalent maps are guaranteed to have an identical in-memory layout. This makes equality checks (.equals()) and set operations (merge, union, difference, intersection) significantly faster than in many other immutable map implementations.
  • Performance: It is highly competitive with other JVM immutable maps and often faster for batch operations.
import io.lacuna.bifurcan.Map;

Map<String, Integer> m1 = new Map<String, Integer>().put("a", 1).put("b", 2);
Map<String, Integer> m2 = new Map<String, Integer>().put("b", 3).put("c", 4);

// Union: values from m2 overwrite those in m1 for overlapping keys
Map<String, Integer> union = m1.union(m2); // {a=1, b=3, c=4}

// Intersection: keeps keys present in both maps, with values from m1
Map<String, Integer> intersection = m1.intersection(m2); // {b=2}

LinearMap (Mutable)

LinearMap is a mutable hash map based on Robin Hood hashing. It is designed for maximum performance in single-threaded contexts.

  • Contiguous Memory Layout: Entries are stored contiguously in memory. This makes iteration extremely fast—up to 20x faster than java.util.HashMap for large collections because it minimizes cache misses.
  • Fast Cloning: The contiguous layout also makes .clone() a very cheap operation.
  • Customizable Equality: Like the immutable Map, it supports custom hash and equality functions.

LinearMap is an excellent choice when you need a high-performance, mutable map, especially if you plan to iterate over its entries frequently.

import io.lacuna.bifurcan.LinearMap;

LinearMap<String, Integer> map = new LinearMap<>();
map.put("one", 1);
map.put("two", 2);

// Iteration is very fast
map.forEach(entry -> System.out.println(entry.key() + ": " + entry.value()));