Mailing-List: contact mapreduce-issues-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mapreduce-issues@hadoop.apache.org
Date: Thu, 29 Nov 2012 15:32:58 +0000 (UTC)
From: "Radim Kolar (JIRA)" <jira@apache.org>
To: mapreduce-issues@hadoop.apache.org
Message-ID: <2081049878.40363.1354203178893.JavaMail.jiratomcat@arcas>
In-Reply-To: <1712870313.33514.1354122181532.JavaMail.jiratomcat@arcas>
Subject: [jira] [Commented] (MAPREDUCE-4827) Increase hash quality of
 HashPartitioner
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ 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