www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 15380] New: Clarify hash bits requirements


          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

Nov 26 2015