| commit | 3175e91efa4d4cb1847044f9ea4a8ef57fd6f39c | [log] [tgz] |
|---|---|---|
| author | Andrea Canciani <ranma42@gmail.com> | Mon Nov 14 09:24:47 2011 |
| committer | Kristian Høgsberg <krh@bitplanet.net> | Tue Nov 15 15:15:48 2011 |
| tree | 48bbb695557597835abb9c861b85e347af65a2bb | |
| parent | e742dcc9ed4b22eb5191f7e8d2b7cd8011ed5893 [diff] |
hash: Improve double hashing Instead of artificially introducing collisions in the step value by replacing 0 with 1 (which causes the value 1 to have twice the frequency of any other value), the step value can simply be computed as an uniformly distributed value in the range [1, rehash], extremes included. This is safe because any step value smaller than the hash modulus is co-prime with it, hence induces an orbit which includes every integer in [0, size - 1].