Timeline for Why does the collection library for Dart use a bit mask for hashing collections?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28 at 22:02 | comment | added | JimmyJames | @Basilevs You might be absolutely right and it would be interesting to see that analysis for this case. But my guess/hypothesis here is that when this was implemented, the developer implemented the algorithm as it was defined by Jenkins. The shifts amounts are magic numbers based on the assumption (AFAICT) of a 32-bit value. Retaining the overflow bits after a left shift is definitely a change. The fact that the re-masking is only done after left shifts is a clue to what the developer was thinking IMO. | |
| Feb 28 at 21:22 | comment | added | Basilevs | @JimmyJames truncation makes avalanche worse due to loss of entropy. A better solution would be to do everything in a convenient integer, then XOR high bits over lower bits of required width. | |
| Feb 28 at 20:32 | comment | added | JimmyJames | @Abion47 Perhaps not masking after each left shift would impair the avalanche effect of this algorithm (as explained in the wikipedia article.) The actual source article mentions funnels, which I understand to mean a propensity towards collisions. Jenkins writes that his analysis suggested that this algorithm did not have funnels. I'm guessing the person who write this for Dart was disinclined to introduce changes and potentially degrade the results. Without doing the requisite analysis, that's what I would probably do. | |
| Feb 28 at 20:23 | comment | added | JimmyJames | @Abion47 In an implementation using 32-bit ints is assumed, shifting would result in lost bits, right? If you are trying to create an implementation that works the same way as the 32-bit version using a 64-bit variable, you would need mask after every left shift which is what this does. I think it's likely that whoever wrote this was trying to replicate the Jenkins implementation as-is. That, of course, doesn't explain the 31-bit mask, however. | |
| Feb 28 at 20:11 | comment | added | Abion47 | The algorithm being designed for 32-bits makes the most sense, and the interoperability with other languages other answers mention sort does as well to an extent. The only remaining question is why apply the bit mask after every operation? Why not just apply the bit mask once at the end? Masking the bits increases the chance of a collision, so I'd have to imagine that doing it multiple (and, in this case, potentially many) times increases that chance significantly as data gets lost every time the mask is applied. | |
| Feb 28 at 17:32 | history | edited | JimmyJames | CC BY-SA 4.0 | added 425 characters in body |
| Feb 28 at 17:08 | vote | accept | Abion47 | ||
| Feb 28 at 16:23 | history | edited | JimmyJames | CC BY-SA 4.0 | added 214 characters in body |
| Feb 28 at 15:48 | history | answered | JimmyJames | CC BY-SA 4.0 |