HashSmith

HashSmith is a collection of high-performance hash table implementations for Java, designed to optimize speed and memory efficiency specifically for modern Java Virtual Machines (JVM). This project showcases innovative techniques such as SIMD-assisted probing in the SwissMap implementation and Robin Hood hashing in the RobinHoodMap. Both designs prioritize minimal memory overhead and predictable probe lengths, making them more efficient alternatives to the standard JDK HashMap.

Key Features

• SwissMap: Inspired by Google's SwissTable, this implementation employs SIMD probing for enhanced performance, tombstone reuse, and an optional scalar fallback.
• RobinHoodMap: Utilizes Robin Hood hashing combined with backward-shift deletion for efficient memory usage and performance.

Performance Benefits

HashSmith is particularly advantageous for workloads that require high-speed access and low memory consumption. Its implementations are built for JDK 21 and above, leveraging the incubating Vector API for SIMD acceleration. Users can expect improvements in both memory footprint and execution speed compared to traditional hash table implementations.

Code Examples

Here are quick examples demonstrating the usage of the two implementations:

import io.github.bluuewhale.hashsmith.SwissMap;
import io.github.bluuewhale.hashsmith.RobinHoodMap;

public class Demo {
    public static void main(String[] args) {
        // SwissMap
        var swiss = new SwissMap<String, Integer>();
        swiss.put("a", 1);
        swiss.put("b", 2);
        System.out.println(swiss.get("a")); // 1

        // RobinHoodMap
        var robin = new RobinHoodMap<String, Integer>();
        robin.put("x", 42);
        robin.put("y", 99);
        robin.remove("x");
        System.out.println(robin.get("y")); // 99
    }
}

Memory Efficiency

The memory footprint of HashSmith’s implementations, especially the SwissMap, demonstrates significant efficiency gains, with up to 43.7% reduction in retained heap compared to HashMap for small payloads. This efficiency is crucial for applications that manage large datasets with minimal system resource usage.

Benchmarking and Performance Testing

HashSmith facilitates benchmarking via the JMH framework to compare the performance metrics of HashMap, SwissMap, and RobinHoodMap. These benchmarks cover various operations such as retrieval, insertion, and iteration, ensuring users can make data-driven decisions depending on their application needs.

For more detailed documentation, refer to:

• SwissMap documentation: docs/SwissMap.md
• RobinHoodMap documentation: docs/RobinHoodMap.md

HashSmith stands out as an ideal choice for developers seeking to build efficient Java applications, offering advanced data structures that capitalize on modern computing capabilities.