Fast, Memory-Efficient Hash Table in Java: Borrowing the Best Ideas
3 days ago
- #java
- #hash-table
- #performance
- SwissTable is an open-addressing hash table design from Google, separating metadata (control bytes) from key/value storage to optimize performance.
- The design uses a split hash (h1 and h2) to minimize key comparisons, making lookups faster by first scanning compact control bytes.
- SwissTable achieves higher load factors (up to 87.5%) without performance degradation, improving memory efficiency.
- The design has been adopted in Rust and Go standard libraries, showcasing its generational impact.
- Java implementation leverages the Vector API for SIMD operations, enabling efficient control-byte scans.
- Key optimizations include control byte reuse, sentinel padding, h1/h2 split, tombstone handling, and efficient resizing.
- Benchmarks show SwissMap (Java implementation) competes with or outperforms other hash maps, especially at high load factors.
- The project, HashSmith, includes SwissMap and SwissSet variants, available for experimentation and benchmarking.