The definitive guide to “modulo bias” and how to avoid it (2020)

Re:The definitive guide to “modulo bias” and how to avoid it... by xxpor on Thursday September 15, 2022 @12:24PM (#32854352)

Everything here is focused on cryptography, but there's other common issues that can fall into this trap too. For example, naive implementations of a hash function for a basic array + linked list hash table. If you generate a hash, and then modulo that to pick a hash bucket, you could end up with a biased distribution across the buckets, and customers complaining your performance varies wildly based on the input value.

Just more things to think about :)

[ Parent | on HN ]

Re:The definitive guide to “modulo bias” and how to avoid it... by kelnos on Thursday September 15, 2022 @03:06PM (#32856993)

Isn't that why most tutorials on writing hash tables that use this bucketing method recommend using table sizes that are powers of two? I guess most tutorials don't exactly explain why, though, so someone who doesn't understand could decide to not use a power of two without understanding why that's bad.

[ Parent | on HN ]

Re:The definitive guide to “modulo bias” and how to avoid it... by xxpor on Thursday September 15, 2022 @04:46PM (#32858216)

There's another reason why (mathematically related) to use a power of 2 as well: it makes the modulo a simple and fast mask, instead of a slow division.

[ Parent | on HN ]