Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?
Let f and r be two integers. They always keep the k-mer on the forward and reverse strand, respectively. At a new base c in a proper 2-bit encoding, we update the two integers as follows:

f = (f&lt;&lt;2|c) &amp; ((1ULL&lt;&lt;2*k) - 1)
r = r&gt;&gt;2 | (3ULL-c)&lt;&lt;2*(k-1)


With this updating rule, f keeps the forward strand k-mer ending at c and r is f's reverse complement. The hash of the k-mer can be min(f,r). If integer operations take constant time, computing the hashes of all k-mers of a sequence of length L takes O(L) time.

The above only works if k-mer fits a word, which means k&lt;=32 on x86. For long k-mers, you can overload bit operators in C++. In case of 32&lt;k&lt;=64, a simpler solution is to split into lower and higher bits:

c1 = c&amp;1, c2 = c&gt;&gt;1
f1 = (f1&lt;&lt;1|c1) &amp; ((1ULL&lt;&lt;k) - 1)
f2 = (f2&lt;&lt;1|c2) &amp; ((1ULL&lt;&lt;k) - 1)
r1 = r1&gt;&gt;1 | (1ULL-c1)&lt;&lt;(k-1)
r2 = r2&gt;&gt;1 | (1ULL-c2)&lt;&lt;(k-1)


This is twice as slow as the k&lt;=32 version. It is possible to implement these lines with SSE2 intrinsics, but that is overkilling.

When you want to hash a long k-mer into fewer bits, there are a few options:

xor:      f^r
min:      min(f,r)
min+hash: hash(min(f,r))


where hash() is a generic randomization hash function, which could be Murmur3, Wang's integer hash function, etc.

The following is a microbenchmark. Here, we squeeze all k-mers into a 32-bit hash table. collision_rate = 1 - #distinct_hash/#distinct_kmer. This is not the best metric, but it somehow measures the randomness, which is better than nothing.

====================================================
 Algorithm    data  max-k  k   %collision  CPU time
----------------------------------------------------
 xor          chr11  32    31     8.5%       0.9s
 xor+Wang     chr11  32    31     9.6%       1.3s
 min+Wang     chr11  32    31     1.4%       1.3s
 min+Wang     chr11  64    31     1.4%       1.9s
 min+murmur3  chr11  inf   31     1.4%       5.7s
 min+Wang     chr11  64    51     1.5%       2.1s
 min+murmur3  chr11  inf   51     1.5%       6.8s
 min+Wang     chr11  64    63     1.5%       2.1s
 min+murmur3  chr11  inf   63     1.5%       7.5s
 radix sort   chr11  -     -      -        5.6-7.3s
----------------------------------------------------
 min+Wang     hg38   64    63    26.2%        37s
 min+murmur3  hg38   inf   63    26.2%       192s
 radix sort   hg38   -     -      -         ~138s
====================================================


Observations:


Don't use XOR. In fact, XOR hashes all palindromes to 0xffff.... This is already worrying enough.
Unless you want to work with very long k-mers, don't use generic string hash functions like FNV and Murmur. Murmur is even slower than radix sorting all hashes.
For k&lt;=64, min+Wang is the best here. It is fast and simple to compute and has randomness nearly as good as murmur.