hadoop-mapreduce-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Radim Kolar (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MAPREDUCE-4827) Increase hash quality of HashPartitioner
Date Thu, 29 Nov 2012 15:32:58 GMT

    [ https://issues.apache.org/jira/browse/MAPREDUCE-4827?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506535#comment-13506535
] 

Radim Kolar commented on MAPREDUCE-4827:
----------------------------------------

We can get another fast hash function from Knutt book if you are so paranoid.

Thus the hash function is:

h(k) = floor(m * (kA - floor(kA)))

In this case, the value of m is not critical and we typically choose a power of 2 so that
we can get the following efficient procedure on most digital computers:

    Choose m = 2p.
    Multiply the w bits of k by floor(A * 2w) to obtain a 2w bit product.
    Extract the p most significant bits of the lower half of this product.

    It seems that:

    A = (sqrt(5)-1)/2 = 0.6180339887

    is a good choice 


Knuth, "Sorting and Searching", v. 3 of "The Art of Computer Programming"
                
> Increase hash quality of HashPartitioner
> ----------------------------------------
>
>                 Key: MAPREDUCE-4827
>                 URL: https://issues.apache.org/jira/browse/MAPREDUCE-4827
>             Project: Hadoop Map/Reduce
>          Issue Type: Improvement
>            Reporter: Radim Kolar
>         Attachments: betterhash1.txt
>
>
> hash partitioner is using object.hashCode() for splitting keys into partitions. This
results in bad distributions because hashCode() quality is poor. 
> These hashCode() functions are sometimes written by hand (very poor quality) and sometimes
generated from by commons lang code (poor quality). Applying some transformation on top of
hashCode() provides better distribution.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message