hbase-common/src/main/java/org/apache/hadoop/hbase/util/MurmurHash.java

   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.yetus.audience.InterfaceAudience;
  23 import org.apache.yetus.audience.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 <T> int hash(HashKey<T> hashKey, int seed) {
  43     int m = 0x5bd1e995;
  44     int r = 24;
  45     int length = hashKey.length();
  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);
  52       int k = hashKey.get(i_4 + 3);
  53       k = k << 8;
  54       k = k | (hashKey.get(i_4 + 2) & 0xff);
  55       k = k << 8;
  56       k = k | (hashKey.get(i_4 + 1) & 0xff);
  57       k = k << 8;
  58       // noinspection PointlessArithmeticExpression
  59       k = k | (hashKey.get(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;
  71
  72     if (left != 0) {
  73       if (left >= 3) {
  74         h ^= hashKey.get(i_m + 2) << 16;
  75       }
  76       if (left >= 2) {
  77         h ^= hashKey.get(i_m + 1) << 8;
  78       }
  79       if (left >= 1) {
  80         h ^= hashKey.get(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 }