1 /** 2 * Copyright 2010 The Apache Software Foundation 3 * 4 * Licensed to the Apache Software Foundation (ASF) under one 5 * or more contributor license agreements. See the NOTICE file 6 * distributed with this work for additional information 7 * regarding copyright ownership. The ASF licenses this file 8 * to you under the Apache License, Version 2.0 (the 9 * "License"); you may not use this file except in compliance 10 * with the License. You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 21 package org.apache.hadoop.hbase.util; 22 23 /** 24 * This is a very fast, non-cryptographic hash suitable for general hash-based 25 * lookup. See http://murmurhash.googlepages.com/ for more details. 26 * 27 * <p>The C version of MurmurHash 2.0 found at that site was ported 28 * to Java by Andrzej Bialecki (ab at getopt org).</p> 29 */ 30 public class MurmurHash extends Hash { 31 private static MurmurHash _instance = new MurmurHash(); 32 33 public static Hash getInstance() { 34 return _instance; 35 } 36 37 @Override 38 public int hash(byte[] data, int offset, int length, int seed) { 39 int m = 0x5bd1e995; 40 int r = 24; 41 42 int h = seed ^ length; 43 44 int len_4 = length >> 2; 45 46 for (int i = 0; i < len_4; i++) { 47 int i_4 = (i << 2) + offset; 48 int k = data[i_4 + 3]; 49 k = k << 8; 50 k = k | (data[i_4 + 2] & 0xff); 51 k = k << 8; 52 k = k | (data[i_4 + 1] & 0xff); 53 k = k << 8; 54 //noinspection PointlessArithmeticExpression 55 k = k | (data[i_4 + 0] & 0xff); 56 k *= m; 57 k ^= k >>> r; 58 k *= m; 59 h *= m; 60 h ^= k; 61 } 62 63 // avoid calculating modulo 64 int len_m = len_4 << 2; 65 int left = length - len_m; 66 int i_m = len_m + offset; 67 68 if (left != 0) { 69 if (left >= 3) { 70 h ^= data[i_m + 2] << 16; 71 } 72 if (left >= 2) { 73 h ^= data[i_m + 1] << 8; 74 } 75 if (left >= 1) { 76 h ^= data[i_m]; 77 } 78 79 h *= m; 80 } 81 82 h ^= h >>> 13; 83 h *= m; 84 h ^= h >>> 15; 85 86 return h; 87 } 88 }