View Javadoc

1   /**
2    * Copyright 2010 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  
21  package org.apache.hadoop.hbase.util;
22  
23  /**
24   * This is a very fast, non-cryptographic hash suitable for general hash-based
25   * lookup.  See http://murmurhash.googlepages.com/ for more details.
26   *
27   * <p>The C version of MurmurHash 2.0 found at that site was ported
28   * to Java by Andrzej Bialecki (ab at getopt org).</p>
29   */
30  public class MurmurHash extends Hash {
31    private static MurmurHash _instance = new MurmurHash();
32  
33    public static Hash getInstance() {
34      return _instance;
35    }
36  
37    @Override
38    public int hash(byte[] data, int offset, int length, int seed) {
39      int m = 0x5bd1e995;
40      int r = 24;
41  
42      int h = seed ^ length;
43  
44      int len_4 = length >> 2;
45  
46      for (int i = 0; i < len_4; i++) {
47        int i_4 = (i << 2) + offset;
48        int k = data[i_4 + 3];
49        k = k << 8;
50        k = k | (data[i_4 + 2] & 0xff);
51        k = k << 8;
52        k = k | (data[i_4 + 1] & 0xff);
53        k = k << 8;
54        //noinspection PointlessArithmeticExpression
55        k = k | (data[i_4 + 0] & 0xff);
56        k *= m;
57        k ^= k >>> r;
58        k *= m;
59        h *= m;
60        h ^= k;
61      }
62  
63      // avoid calculating modulo
64      int len_m = len_4 << 2;
65      int left = length - len_m;
66      int i_m = len_m + offset;
67  
68      if (left != 0) {
69        if (left >= 3) {
70          h ^= data[i_m + 2] << 16;
71        }
72        if (left >= 2) {
73          h ^= data[i_m + 1] << 8;
74        }
75        if (left >= 1) {
76          h ^= data[i_m];
77        }
78  
79        h *= m;
80      }
81  
82      h ^= h >>> 13;
83      h *= m;
84      h ^= h >>> 15;
85  
86      return h;
87    }
88  }