001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import org.apache.yetus.audience.InterfaceAudience;
021import org.apache.yetus.audience.InterfaceStability;
022
023/**
024 * This is a very fast, non-cryptographic hash suitable for general hash-based lookup. See
025 * http://code.google.com/p/smhasher/wiki/MurmurHash3 for details.
026 * <p>
027 * MurmurHash3 is the successor to MurmurHash2. It comes in 3 variants, and the 32-bit version
028 * targets low latency for hash table use.
029 * </p>
030 */
031@InterfaceAudience.Private
032@InterfaceStability.Stable
033public class MurmurHash3 extends Hash {
034  private static MurmurHash3 _instance = new MurmurHash3();
035
036  public static Hash getInstance() {
037    return _instance;
038  }
039
040  /** Returns the MurmurHash3_x86_32 hash. */
041  @edu.umd.cs.findbugs.annotations.SuppressWarnings("SF")
042  @Override
043  public <T> int hash(HashKey<T> hashKey, int initval) {
044    final int c1 = 0xcc9e2d51;
045    final int c2 = 0x1b873593;
046    int length = hashKey.length();
047    int h1 = initval;
048    int roundedEnd = (length & 0xfffffffc); // round down to 4 byte block
049
050    for (int i = 0; i < roundedEnd; i += 4) {
051      int k1 = hashKey.getIntLE(i);
052      k1 *= c1;
053      k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
054      k1 *= c2;
055
056      h1 ^= k1;
057      h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);
058      h1 = h1 * 5 + 0xe6546b64;
059    }
060
061    // tail
062    int k1 = 0;
063
064    switch (length & 0x03) {
065      case 3:
066        k1 = (hashKey.get(roundedEnd + 2) & 0xff) << 16;
067        // FindBugs SF_SWITCH_FALLTHROUGH
068      case 2:
069        k1 |= (hashKey.get(roundedEnd + 1) & 0xff) << 8;
070        // FindBugs SF_SWITCH_FALLTHROUGH
071      case 1:
072        k1 |= (hashKey.get(roundedEnd) & 0xff);
073        k1 *= c1;
074        k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
075        k1 *= c2;
076        h1 ^= k1;
077      default:
078        // fall out
079    }
080
081    // finalization
082    h1 ^= length;
083
084    // fmix(h1);
085    h1 ^= h1 >>> 16;
086    h1 *= 0x85ebca6b;
087    h1 ^= h1 >>> 13;
088    h1 *= 0xc2b2ae35;
089    h1 ^= h1 >>> 16;
090
091    return h1;
092  }
093}