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
20 package org.apache.hadoop.hbase.util;
21
22 import org.apache.hadoop.hbase.classification.InterfaceAudience;
23 import org.apache.hadoop.hbase.classification.InterfaceStability;
24
25 /**
26 * This is a very fast, non-cryptographic hash suitable for general hash-based
27 * lookup. See http://murmurhash.googlepages.com/ for more details.
28 *
29 * <p>The C version of MurmurHash 2.0 found at that site was ported
30 * to Java by Andrzej Bialecki (ab at getopt org).</p>
31 */
32 @InterfaceAudience.Private
33 @InterfaceStability.Stable
34 public class MurmurHash extends Hash {
35 private static MurmurHash _instance = new MurmurHash();
36
37 public static Hash getInstance() {
38 return _instance;
39 }
40
41 @Override
42 public int hash(byte[] data, int offset, int length, int seed) {
43 int m = 0x5bd1e995;
44 int r = 24;
45
46 int h = seed ^ length;
47
48 int len_4 = length >> 2;
49
50 for (int i = 0; i < len_4; i++) {
51 int i_4 = (i << 2) + offset;
52 int k = data[i_4 + 3];
53 k = k << 8;
54 k = k | (data[i_4 + 2] & 0xff);
55 k = k << 8;
56 k = k | (data[i_4 + 1] & 0xff);
57 k = k << 8;
58 //noinspection PointlessArithmeticExpression
59 k = k | (data[i_4 + 0] & 0xff);
60 k *= m;
61 k ^= k >>> r;
62 k *= m;
63 h *= m;
64 h ^= k;
65 }
66
67 // avoid calculating modulo
68 int len_m = len_4 << 2;
69 int left = length - len_m;
70 int i_m = len_m + offset;
71
72 if (left != 0) {
73 if (left >= 3) {
74 h ^= data[i_m + 2] << 16;
75 }
76 if (left >= 2) {
77 h ^= data[i_m + 1] << 8;
78 }
79 if (left >= 1) {
80 h ^= data[i_m];
81 }
82
83 h *= m;
84 }
85
86 h ^= h >>> 13;
87 h *= m;
88 h ^= h >>> 15;
89
90 return h;
91 }
92 }