View Javadoc

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.Public
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  }