• via Digitalmars-d-bugs (29/29) Nov 26 2015 https://issues.dlang.org/show_bug.cgi?id=15380

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=15380

          Issue ID: 15380
           Summary: Clarify hash bits requirements
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P1
         Component: dlang.org
          Assignee: nobody puremagic.com
          Reporter: verylonglogin.reg gmail.com

Currently the only documented requirement for a hash function is to return
equal hashes for equal objects [1]. But it's common that hash function also
should meet the following requirement for performance:

  All hash bits must equally represent the object.

This requirement allows hash tables and other algorithms to cut any `k` bits.
It really is a common situation: currently Druntime's associative arrays only
use lowest bits of hash (by getting a modulo with hash table size which is a
power of 2 [2]) for bucket index calculation and nothing prevents it from using
highest bits instead because of e.g. some refactoring.

As a result even if an object is fully represented by an integer varying in a
small range this integer can't be used as a hash as it has only few changing
bits which may be cut by a hash table and this MUST be documented.

[1] http://dlang.org/hash-map.html
[2]
https://github.com/D-Programming-Language/druntime/blob/893cc056bb717bea58c77bf960c4a006a1af079b/src/rt/aaA.d#L115

--