R: Fast hashing of strings to integer modulo n?

Question

I have a vector of strings and I would like to hash each element individually to integers modulo n.

In this SO post it suggests an approach using digest and strotoi. But when I try it I get NA as the returned value

library(digest)
strtoi(digest("cc", algo = "xxhash32"), 16L)

So the above approach will not work as it can not even produce an integer let alone modulo of one.

What's the best way to hash a large vector of strings to integers modulo n for some n? Efficient solutions are more than welcome as the vector is large.

For speed, you could also consider replacing the modulo reduction with multiply and shift. — Thomas Mueller, Dec 01 '17 at 08:33
A good description is in the blog post [A fast alternative to the modulo reduction](https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/) — Thomas Mueller, Dec 06 '17 at 05:12

score 2 · Answer 1 · answered Nov 29 '17 at 07:58

2

R uses 32-bit integers for integer vectors, so the range of representable integers is restricted to about +/-2*10^9. strtoi returns NA because the number is too big.

The mpfr-function from the Rmpfr package should work for you:

mpfr(x = digest("cc`enter code here`", algo = "xxhash32"), base = 16)
[1] 4192999065

answered Nov 29 '17 at 07:58

Birger

1,111
7
17

seems quite slow when I applied to a large vector. – xiaodai Dec 06 '17 at 04:36

xiaodai · Accepted Answer · 2017-12-06T04:53:11.317

1

I made a Rcpp implementation using code from this SO post and the resultant code is quite fast even for large-ish string vectors.

To use it

if(!require(disk.frame)) devtools::install_github("xiaodaigh/disk.frame")
modn = 17
disk.frame::hashstr2i(c("string1","string2"), modn)

edited Dec 06 '17 at 04:53

answered Dec 06 '17 at 04:37

xiaodai

14,889
18
76
140

R: Fast hashing of strings to integer modulo n?

2 Answers2