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      // little endian load order
052      int k1 = (hashKey.get(i) & 0xff) | ((hashKey.get(i + 1) & 0xff) << 8)
053        | ((hashKey.get(i + 2) & 0xff) << 16) | (hashKey.get(i + 3) << 24);
054      k1 *= c1;
055      k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
056      k1 *= c2;
057
058      h1 ^= k1;
059      h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);
060      h1 = h1 * 5 + 0xe6546b64;
061    }
062
063    // tail
064    int k1 = 0;
065
066    switch (length & 0x03) {
067      case 3:
068        k1 = (hashKey.get(roundedEnd + 2) & 0xff) << 16;
069        // FindBugs SF_SWITCH_FALLTHROUGH
070      case 2:
071        k1 |= (hashKey.get(roundedEnd + 1) & 0xff) << 8;
072        // FindBugs SF_SWITCH_FALLTHROUGH
073      case 1:
074        k1 |= (hashKey.get(roundedEnd) & 0xff);
075        k1 *= c1;
076        k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
077        k1 *= c2;
078        h1 ^= k1;
079      default:
080        // fall out
081    }
082
083    // finalization
084    h1 ^= length;
085
086    // fmix(h1);
087    h1 ^= h1 >>> 16;
088    h1 *= 0x85ebca6b;
089    h1 ^= h1 >>> 13;
090    h1 *= 0xc2b2ae35;
091    h1 ^= h1 >>> 16;
092
093    return h1;
094  }
095}