You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-dev@hadoop.apache.org by "Jim Kellerman (JIRA)" <ji...@apache.org> on 2007/12/06 18:20:43 UTC
[jira] Commented: (HADOOP-2365) Result of HashFunction.hash()
contains all identical values
[ https://issues.apache.org/jira/browse/HADOOP-2365?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12549100 ]
Jim Kellerman commented on HADOOP-2365:
---------------------------------------
-1 on patch. This section of code should read:
{code}
int[] result = new int[nbHash];
for (int i = 0, initval = 0; i < nbHash; i++) {
initval = result[i] = Math.abs(JenkinsHash.hash(b, initval)) % maxValue;
}
return result;
{code}
However, thanks for finding my stupid mistake.
> Result of HashFunction.hash() contains all identical values
> -----------------------------------------------------------
>
> Key: HADOOP-2365
> URL: https://issues.apache.org/jira/browse/HADOOP-2365
> Project: Hadoop
> Issue Type: Bug
> Components: contrib/hbase
> Affects Versions: 0.16.0
> Reporter: Andrzej Bialecki
> Fix For: 0.16.0
>
> Attachments: hash-v1.patch
>
>
> There is a small bug in HashFunction:112 - initvalue should be changed between the loop iterations in order to spread the hash values over the whole allowed range. Instead the current code uses a fixed initvalue = 0, which gives all identical hash values in the result array. As a result, BloomFilter-s have extremely high rate of false positives.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Commented: (HADOOP-2365) Result of HashFunction.hash()
contains all identical values
Posted by Andrzej Bialecki <ab...@getopt.org>.
Jim Kellerman (JIRA) wrote:
> [ https://issues.apache.org/jira/browse/HADOOP-2365?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12549100 ]
>
> Jim Kellerman commented on HADOOP-2365:
> ---------------------------------------
>
> -1 on patch. This section of code should read:
>
> {code}
> int[] result = new int[nbHash];
> for (int i = 0, initval = 0; i < nbHash; i++) {
> initval = result[i] = Math.abs(JenkinsHash.hash(b, initval)) % maxValue;
> }
> return result;
> {code}
>
Yes, this works too - it shouldn't matter in this specific case.
Jenkins' hash has very good avalanche behavior, so even 1 bit difference
in the initvalue yields a completely different hash.
> However, thanks for finding my stupid mistake.
You're welcome. I'm using this class in a different Hadoop application,
where the problem became immediately apparent when I switched from my
home-grown BloomFilter implementation to this one.
--
Best regards,
Andrzej Bialecki <><
___. ___ ___ ___ _ _ __________________________________
[__ || __|__/|__||\/| Information Retrieval, Semantic Web
___|||__|| \| || | Embedded Unix, System Integration
http://www.sigram.com Contact: info at sigram dot com