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