www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9522] New: AA implementation needs no prime number of buckets

http://d.puremagic.com/issues/show_bug.cgi?id=9522

           Summary: AA implementation needs no prime number of buckets
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: druntime
        AssignedTo: nobody puremagic.com
        ReportedBy: reachzach gmail.com


--- Comment #0 from Zach the Mystic <reachzach gmail.com> 2013-02-16 09:09:57
PST ---
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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 16 2013