1 /**
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19 package org.apache.hadoop.hbase.util;
20
21 import org.apache.hadoop.hbase.classification.InterfaceAudience;
22 import org.apache.hadoop.hbase.classification.InterfaceStability;
23
24 /**
25 * This is a very fast, non-cryptographic hash suitable for general hash-based
26 * lookup. See http://code.google.com/p/smhasher/wiki/MurmurHash3 for details.
27 *
28 * <p>MurmurHash3 is the successor to MurmurHash2. It comes in 3 variants, and
29 * the 32-bit version targets low latency for hash table use.</p>
30 */
31 @InterfaceAudience.Private
32 @InterfaceStability.Stable
33 public class MurmurHash3 extends Hash {
34 private static MurmurHash3 _instance = new MurmurHash3();
35
36 public static Hash getInstance() {
37 return _instance;
38 }
39
40 /** Returns the MurmurHash3_x86_32 hash. */
41 @edu.umd.cs.findbugs.annotations.SuppressWarnings("SF")
42 @Override
43 public int hash(byte[] bytes, int offset, int length, int initval) {
44 final int c1 = 0xcc9e2d51;
45 final int c2 = 0x1b873593;
46
47 int h1 = initval;
48 int roundedEnd = offset + (length & 0xfffffffc); // round down to 4 byte block
49
50 for (int i = offset; i < roundedEnd; i += 4) {
51 // little endian load order
52 int k1 = (bytes[i] & 0xff) | ((bytes[i + 1] & 0xff) << 8) | ((bytes[i + 2] & 0xff) << 16)
53 | (bytes[i + 3] << 24);
54 k1 *= c1;
55 k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
56 k1 *= c2;
57
58 h1 ^= k1;
59 h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);
60 h1 = h1 * 5 + 0xe6546b64;
61 }
62
63 // tail
64 int k1 = 0;
65
66 switch (length & 0x03) {
67 case 3:
68 k1 = (bytes[roundedEnd + 2] & 0xff) << 16;
69 // FindBugs SF_SWITCH_FALLTHROUGH
70 case 2:
71 k1 |= (bytes[roundedEnd + 1] & 0xff) << 8;
72 // FindBugs SF_SWITCH_FALLTHROUGH
73 case 1:
74 k1 |= (bytes[roundedEnd] & 0xff);
75 k1 *= c1;
76 k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
77 k1 *= c2;
78 h1 ^= k1;
79 }
80
81 // finalization
82 h1 ^= length;
83
84 // fmix(h1);
85 h1 ^= h1 >>> 16;
86 h1 *= 0x85ebca6b;
87 h1 ^= h1 >>> 13;
88 h1 *= 0xc2b2ae35;
89 h1 ^= h1 >>> 16;
90
91 return h1;
92 }
93 }