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
– Thomas Mueller, Commented Dec 1, 2017 at 8:33
A good description is in the blog post A fast alternative to the modulo reduction — Thomas Mueller
– Thomas Mueller, Commented Dec 6, 2017 at 5:12

Birger · Accepted Answer · 2017-11-29 07:58:44Z

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, 2017 at 7:58

Birger

1,1417 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

xiaodai Over a year ago

seems quite slow when I applied to a large vector.

xiaodai · Accepted Answer · 2017-12-06 04:53:11Z

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 6, 2017 at 4:53

answered Dec 6, 2017 at 4:37

xiaodai

16.3k21 gold badges93 silver badges160 bronze badges

Collectives™ on Stack Overflow

R: Fast hashing of strings to integer modulo n?

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related