k ache-hash: A dynamic, concurrent, and cache-efficient hash table for streaming k -mer operations

Hash tables are fundamental to computational genomics, where keys are often k -mers-fixed-length substrings that exhibit a "streaming" property: consecutive k -mers share k-1 nucleotides and are processed in order. Existing static data structures exploit this locality but cannot support dynamic updates, while state-of-the-art concurrent hash tables support dynamic operations but ignore k -mer locality.

We introduce k ache-hash , the first dynamic, concurrent, and resizable hash table that exploits k -mer locality. k ache-hash builds on Iceberg hashing-a multi-level design achieving stability and low associativity-but replaces generic hashing with minimizer-based hashing, ensuring that consecutive k -mers map to the same buckets. This keeps frequently accessed buckets cache-resident during streaming operations. On the human genome, k ache-hash achieves 1.58-2.62× higher insertion throughput than IcebergHT and up to 6.1× higher query throughput, while incurring 7.39× fewer cache misses. k ache-hash scales near-linearly to 16 threads and supports dynamic resizing without sacrificing locality. Our theoretical analysis proves that streaming k -mer operations achieve 𝒪(1/r) amortized cache misses per operation, where r is the minimizer run length, explaining the substantial performance gains over general-purpose hash tables.

k ache-hash is implemented in C++20 and is available at https://github.com/jamshed/kache-hash .

p.pandey@northeastern.edu.

Supplementary material are available for this manuscript.