Mega Code Archive
FowlerNollVo hash algorhythm
<![CDATA[
/*
* Copyright 2008-2010 the T2 Project ant the Others.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
//package org.t2framework.commons.util;
/**
* Fowler/Noll/Vo hash algorhythm.
*
* This one is originally from http://www.isthe.com/chongo/tech/comp/fnv, and is
* taken from project voldemort.
*
* The basic theory is:
*
* <pre>
* hash = basis
* for each octet_of_data to be hashed
* hash = hash * FNV_prime
* hash = hash xor octet_of_data
* return hash
* </pre>
*
* @see http://www.isthe.com/chongo/tech/comp/fnv
* @see http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
*
*/
public class FnvHashFunction extends AbstractHashFunction {
private static final long FNV_BASIS = 0x811c9dc5;
// for 32bit
private static final long FNV_PRIME = (1 << 24) + 0x193;
public int hash(byte[] bytes, int length, int initval) {
long hash = FNV_BASIS;
for (int i = 0; i < bytes.length; i++) {
hash ^= 0xFF & bytes[i];
hash *= FNV_PRIME;
}
return (int) hash;
}
}
abstract class AbstractHashFunction implements HashFunction {
public int hash(byte[] bytes, int initval) {
return hash(bytes, bytes.length, initval);
}
public int hash(byte[] bytes) {
return hash(bytes, bytes.length, -1);
}
}
interface HashFunction {
int hash(byte[] bytes);
int hash(byte[] bytes, int initval);
int hash(byte[] bytes, int length, int initval);
}
---------------
package org.t2framework.commons.util;
import junit.framework.TestCase;
public class FnvHashFunctionTest extends TestCase {
public void test1() throws Exception {
FnvHashFunction fnv = new FnvHashFunction();
int numIterations = 1000000;
int numBuckets = 5;
int[] buckets = new int[numBuckets];
long start = System.currentTimeMillis();
for (int i = 0; i < numIterations; i++) {
int val = fnv.hash(Integer.toString(i).getBytes());
buckets[Math.abs(val) % numBuckets] += 1;
}
System.out.println(System.currentTimeMillis() - start);
double expected = numIterations / (double) numBuckets;
for (int i = 0; i < numBuckets; i++) {
System.out.println(i + " " + buckets[i] + " "
+ (buckets[i] / expected));
}
}
public void test2() throws Exception {
MurmurHashFunction mur = new MurmurHashFunction();
int numIterations = 1000000;
int numBuckets = 5;
int[] buckets = new int[numBuckets];
long start = System.currentTimeMillis();
for (int i = 0; i < numIterations; i++) {
int val = mur.hash(Integer.toString(i).getBytes());
buckets[Math.abs(val) % numBuckets] += 1;
}
System.out.println(System.currentTimeMillis() - start);
double expected = numIterations / (double) numBuckets;
for (int i = 0; i < numBuckets; i++) {
System.out.println(i + " " + buckets[i] + " "
+ (buckets[i] / expected));
}
}
public void test3() throws Exception {
JenkinsHashFunction jenkins = new JenkinsHashFunction();
int numIterations = 1000000;
int numBuckets = 5;
int[] buckets = new int[numBuckets];
long start = System.currentTimeMillis();
for (int i = 0; i < numIterations; i++) {
int val = jenkins.hash(Integer.toString(i).getBytes());
buckets[Math.abs(val) % numBuckets] += 1;
}
System.out.println(System.currentTimeMillis() - start);
double expected = numIterations / (double) numBuckets;
for (int i = 0; i < numBuckets; i++) {
System.out.println(i + " " + buckets[i] + " "
+ (buckets[i] / expected));
}
}
}
]]>