Bug 9522 – [AA] AA implementation needs no prime number of buckets
Status
RESOLVED
Resolution
FIXED
Severity
enhancement
Priority
P2
Component
druntime
Product
D
Version
D2
Platform
All
OS
All
Creation time
2013-02-16T09:09:57Z
Last change time
2018-11-23T11:07:41Z
Assigned to
No Owner
Creator
Zach the Mystic
Comments
Comment #0 by reachzach — 2013-02-16T09:09:57Z
Hash function expert Bob Jenkins' says specifically that a 'decent' hash function can distribute its keys to a power of 2 just as easily as to a prime number. He approves of the SuperFastHash algorithm used in druntime. There is therefore no need for the AA implementation to use a prime number of buckets for its tables. See:
http://burtleburtle.net/bob/hash/hashfaq.html
For his take on the current hash function used (which he approves of), see the sections "Paul Tsieh's Hash" and "My Hash" near the bottom of this article:
http://burtleburtle.net/bob/hash/doobs.html
This is the current AA implementation. See line 50 for unnecessary prime number listings:
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
Comment #1 by stanislav.blinov — 2018-11-23T11:07:41Z