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 /**
22 * This is a very fast, non-cryptographic hash suitable for general hash-based
23 * lookup. See http://code.google.com/p/smhasher/wiki/MurmurHash3 for details.
24 *
25 * <p>MurmurHash3 is the successor to MurmurHash2. It comes in 3 variants, and
26 * the 32-bit version targets low latency for hash table use.</p>
27 */
28 public class MurmurHash3 extends Hash {
29 private static MurmurHash3 _instance = new MurmurHash3();
30
31 public static Hash getInstance() {
32 return _instance;
33 }
34
35 /** Returns the MurmurHash3_x86_32 hash. */
36 @edu.umd.cs.findbugs.annotations.SuppressWarnings("SF")
37 @Override
38 public int hash(byte[] bytes, int offset, int length, int initval) {
39 final int c1 = 0xcc9e2d51;
40 final int c2 = 0x1b873593;
41
42 int h1 = initval;
43 int roundedEnd = offset + (length & 0xfffffffc); // round down to 4 byte block
44
45 for (int i = offset; i < roundedEnd; i += 4) {
46 // little endian load order
47 int k1 = (bytes[i] & 0xff) | ((bytes[i + 1] & 0xff) << 8) | ((bytes[i + 2] & 0xff) << 16)
48 | (bytes[i + 3] << 24);
49 k1 *= c1;
50 k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
51 k1 *= c2;
52
53 h1 ^= k1;
54 h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);
55 h1 = h1 * 5 + 0xe6546b64;
56 }
57
58 // tail
59 int k1 = 0;
60
61 switch (length & 0x03) {
62 case 3:
63 k1 = (bytes[roundedEnd + 2] & 0xff) << 16;
64 // FindBugs SF_SWITCH_FALLTHROUGH
65 case 2:
66 k1 |= (bytes[roundedEnd + 1] & 0xff) << 8;
67 // FindBugs SF_SWITCH_FALLTHROUGH
68 case 1:
69 k1 |= (bytes[roundedEnd] & 0xff);
70 k1 *= c1;
71 k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
72 k1 *= c2;
73 h1 ^= k1;
74 }
75
76 // finalization
77 h1 ^= length;
78
79 // fmix(h1);
80 h1 ^= h1 >>> 16;
81 h1 *= 0x85ebca6b;
82 h1 ^= h1 >>> 13;
83 h1 *= 0xc2b2ae35;
84 h1 ^= h1 >>> 16;
85
86 return h1;
87 }
88 }