BTW, in the original article I believe the "table based" hashing Dan alludes to is some kind of BuzHash and even mentions it probably being faster. I also just

BTW, in the original article I believe the "table based" hashing Dan alludes to is some kind of BuzHash and even mentions it probably being faster. I also just noticed that one of your intended applications is DNA sequences. For a tiny 2-bit AGTC alphabet, you could probably assign random 4..8 byte table codes for a basic size-4 table and then pre-compute the first several "powers" of that table in the same way as suggested in my big "IF" sibling comment here. To elaborate, every possible sextuplet becomes a table with 2 * 6=2^12=4096 * 8byte entries probably fitting in a 32 KiB CPU L1 cache. Of course, if you are hashing out and then also in 6 basepairs at a time to have 6X fewer loops, then you lose "single base pair granularity" of window sizes. I.e., every window has to be a multiple of 6 basepairs. But for DNA, there may be actual end-user applications where 3 bp (1 codon) is useful and 3X fewer loops is nothing to sneeze at. You could do the same thing with your current Rabin-Karp with an alphabet mapping table, of course. (A pair of simple arrays taking triplet numbers to/from codon numbers). Given the sensitivity of optimizations in both approaches to alphabet size, you may profitably improve your API to include alphabet size and possibly alphabet translation tables as parameters.