Index: hbase-common/src/main/java/org/apache/hadoop/hbase/util/MurmurHash3.java =================================================================== --- hbase-common/src/main/java/org/apache/hadoop/hbase/util/MurmurHash3.java (revision 0) +++ hbase-common/src/main/java/org/apache/hadoop/hbase/util/MurmurHash3.java (working copy) @@ -0,0 +1,87 @@ +/** + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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.apache.hadoop.hbase.util; + +/** + * This is a very fast, non-cryptographic hash suitable for general hash-based + * lookup. See http://code.google.com/p/smhasher/wiki/MurmurHash3 for details. + * + *
MurmurHash3 is the successor to MurmurHash2. It comes in 3 variants, and + * the 32-bit version targets low latency for hash table use.
+ */ +public class MurmurHash3 extends Hash { + private static MurmurHash3 _instance = new MurmurHash3(); + + public static Hash getInstance() { + return _instance; + } + + /** Returns the MurmurHash3_x86_32 hash. */ + @Override + public int hash(byte[] bytes, int offset, int length, int initval) { + final int c1 = 0xcc9e2d51; + final int c2 = 0x1b873593; + + int h1 = initval; + int roundedEnd = offset + (length & 0xfffffffc); // round down to 4 byte block + + for (int i = offset; i < roundedEnd; i += 4) { + // little endian load order + int k1 = (bytes[i] & 0xff) | ((bytes[i + 1] & 0xff) << 8) | ((bytes[i + 2] & 0xff) << 16) + | (bytes[i + 3] << 24); + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13); + h1 = h1 * 5 + 0xe6546b64; + } + + // tail + int k1 = 0; + + switch (length & 0x03) { + case 3: + k1 = (bytes[roundedEnd + 2] & 0xff) << 16; + // fallthrough + case 2: + k1 |= (bytes[roundedEnd + 1] & 0xff) << 8; + // fallthrough + case 1: + k1 |= (bytes[roundedEnd] & 0xff); + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + h1 ^= k1; + } + + // finalization + h1 ^= length; + + // fmix(h1); + h1 ^= h1 >>> 16; + h1 *= 0x85ebca6b; + h1 ^= h1 >>> 13; + h1 *= 0xc2b2ae35; + h1 ^= h1 >>> 16; + + return h1; + } +} Index: hbase-common/src/main/java/org/apache/hadoop/hbase/util/Hash.java =================================================================== --- hbase-common/src/main/java/org/apache/hadoop/hbase/util/Hash.java (revision 1525529) +++ hbase-common/src/main/java/org/apache/hadoop/hbase/util/Hash.java (working copy) @@ -35,11 +35,13 @@ public static final int JENKINS_HASH = 0; /** Constant to denote {@link MurmurHash}. */ public static final int MURMUR_HASH = 1; + /** Constant to denote {@link MurmurHash3}. */ + public static final int MURMUR_HASH3 = 2; /** * This utility method converts String representation of hash function name - * to a symbolic constant. Currently two function types are supported, - * "jenkins" and "murmur". + * to a symbolic constant. Currently three function types are supported, + * "jenkins", "murmur" and "murmur3". * @param name hash function name * @return one of the predefined constants */ @@ -48,6 +50,8 @@ return JENKINS_HASH; } else if ("murmur".equalsIgnoreCase(name)) { return MURMUR_HASH; + } else if ("murmur3".equalsIgnoreCase(name)) { + return MURMUR_HASH3; } else { return INVALID_HASH; } @@ -75,6 +79,8 @@ return JenkinsHash.getInstance(); case MURMUR_HASH: return MurmurHash.getInstance(); + case MURMUR_HASH3: + return MurmurHash3.getInstance(); default: return null; }