001/**
002 *
003 * Licensed to the Apache Software Foundation (ASF) under one
004 * or more contributor license agreements.  See the NOTICE file
005 * distributed with this work for additional information
006 * regarding copyright ownership.  The ASF licenses this file
007 * to you under the Apache License, Version 2.0 (the
008 * "License"); you may not use this file except in compliance
009 * with the License.  You may obtain a copy of the License at
010 *
011 *     http://www.apache.org/licenses/LICENSE-2.0
012 *
013 * Unless required by applicable law or agreed to in writing, software
014 * distributed under the License is distributed on an "AS IS" BASIS,
015 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016 * See the License for the specific language governing permissions and
017 * limitations under the License.
018 */
019package org.apache.hadoop.hbase.util;
020
021import org.apache.yetus.audience.InterfaceAudience;
022import org.apache.yetus.audience.InterfaceStability;
023
024/**
025 * This is a very fast, non-cryptographic hash suitable for general hash-based
026 * lookup.  See http://code.google.com/p/smhasher/wiki/MurmurHash3 for details.
027 *
028 * <p>MurmurHash3 is the successor to MurmurHash2. It comes in 3 variants, and
029 * the 32-bit version targets low latency for hash table use.</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 =
053          (hashKey.get(i) & 0xff) | ((hashKey.get(i + 1) & 0xff) << 8)
054              | ((hashKey.get(i + 2) & 0xff) << 16)
055              | (hashKey.get(i + 3) << 24);
056      k1 *= c1;
057      k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
058      k1 *= c2;
059
060      h1 ^= k1;
061      h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);
062      h1 = h1 * 5 + 0xe6546b64;
063    }
064
065    // tail
066    int k1 = 0;
067
068    switch (length & 0x03) {
069    case 3:
070      k1 = (hashKey.get(roundedEnd + 2) & 0xff) << 16;
071      // FindBugs SF_SWITCH_FALLTHROUGH
072    case 2:
073      k1 |= (hashKey.get(roundedEnd + 1) & 0xff) << 8;
074      // FindBugs SF_SWITCH_FALLTHROUGH
075    case 1:
076      k1 |= (hashKey.get(roundedEnd) & 0xff);
077      k1 *= c1;
078      k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);
079      k1 *= c2;
080      h1 ^= k1;
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}