JenkinsHash.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:11k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  * Copyright 2007 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. package org.apache.hadoop.util.hash;
  21. import java.io.FileInputStream;
  22. import java.io.IOException;
  23. /**
  24.  * Produces 32-bit hash for hash table lookup.
  25.  * 
  26.  * <pre>lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  27.  *
  28.  * You can use this free for any purpose.  It's in the public domain.
  29.  * It has no warranty.
  30.  * </pre>
  31.  * 
  32.  * @see <a href="http://burtleburtle.net/bob/c/lookup3.c">lookup3.c</a>
  33.  * @see <a href="http://www.ddj.com/184410284">Hash Functions (and how this
  34.  * function compares to others such as CRC, MD?, etc</a>
  35.  * @see <a href="http://burtleburtle.net/bob/hash/doobs.html">Has update on the
  36.  * Dr. Dobbs Article</a>
  37.  */
  38. public class JenkinsHash extends Hash {
  39.   private static long INT_MASK  = 0x00000000ffffffffL;
  40.   private static long BYTE_MASK = 0x00000000000000ffL;
  41.   
  42.   private static JenkinsHash _instance = new JenkinsHash();
  43.   
  44.   public static Hash getInstance() {
  45.     return _instance;
  46.   }
  47.   private static long rot(long val, int pos) {
  48.     return ((Integer.rotateLeft(
  49.         (int)(val & INT_MASK), pos)) & INT_MASK);
  50.   }
  51.   /**
  52.    * taken from  hashlittle() -- hash a variable-length key into a 32-bit value
  53.    * 
  54.    * @param key the key (the unaligned variable-length array of bytes)
  55.    * @param nbytes number of bytes to include in hash
  56.    * @param initval can be any integer value
  57.    * @return a 32-bit value.  Every bit of the key affects every bit of the
  58.    * return value.  Two keys differing by one or two bits will have totally
  59.    * different hash values.
  60.    * 
  61.    * <p>The best hash table sizes are powers of 2.  There is no need to do mod
  62.    * a prime (mod is sooo slow!).  If you need less than 32 bits, use a bitmask.
  63.    * For example, if you need only 10 bits, do
  64.    * <code>h = (h & hashmask(10));</code>
  65.    * In which case, the hash table should have hashsize(10) elements.
  66.    * 
  67.    * <p>If you are hashing n strings byte[][] k, do it like this:
  68.    * for (int i = 0, h = 0; i < n; ++i) h = hash( k[i], h);
  69.    * 
  70.    * <p>By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
  71.    * code any way you wish, private, educational, or commercial.  It's free.
  72.    * 
  73.    * <p>Use for hash table lookup, or anything where one collision in 2^^32 is
  74.    * acceptable.  Do NOT use for cryptographic purposes.
  75.   */
  76.   @SuppressWarnings("fallthrough")
  77.   public int hash(byte[] key, int nbytes, int initval) {
  78.     int length = nbytes;
  79.     long a, b, c;       // We use longs because we don't have unsigned ints
  80.     a = b = c = (0x00000000deadbeefL + length + initval) & INT_MASK;
  81.     int offset = 0;
  82.     for (; length > 12; offset += 12, length -= 12) {
  83.       a = (a + (key[offset + 0]    & BYTE_MASK)) & INT_MASK;
  84.       a = (a + (((key[offset + 1]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  85.       a = (a + (((key[offset + 2]  & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  86.       a = (a + (((key[offset + 3]  & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  87.       b = (b + (key[offset + 4]    & BYTE_MASK)) & INT_MASK;
  88.       b = (b + (((key[offset + 5]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  89.       b = (b + (((key[offset + 6]  & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  90.       b = (b + (((key[offset + 7]  & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  91.       c = (c + (key[offset + 8]    & BYTE_MASK)) & INT_MASK;
  92.       c = (c + (((key[offset + 9]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  93.       c = (c + (((key[offset + 10] & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  94.       c = (c + (((key[offset + 11] & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  95.       
  96.       /*
  97.        * mix -- mix 3 32-bit values reversibly.
  98.        * This is reversible, so any information in (a,b,c) before mix() is
  99.        * still in (a,b,c) after mix().
  100.        * 
  101.        * If four pairs of (a,b,c) inputs are run through mix(), or through
  102.        * mix() in reverse, there are at least 32 bits of the output that
  103.        * are sometimes the same for one pair and different for another pair.
  104.        * 
  105.        * This was tested for:
  106.        * - pairs that differed by one bit, by two bits, in any combination
  107.        *   of top bits of (a,b,c), or in any combination of bottom bits of
  108.        *   (a,b,c).
  109.        * - "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  110.        *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  111.        *    is commonly produced by subtraction) look like a single 1-bit
  112.        *    difference.
  113.        * - the base values were pseudorandom, all zero but one bit set, or
  114.        *   all zero plus a counter that starts at zero.
  115.        * 
  116.        * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
  117.        * satisfy this are
  118.        *     4  6  8 16 19  4
  119.        *     9 15  3 18 27 15
  120.        *    14  9  3  7 17  3
  121.        * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing for 
  122.        * "differ" defined as + with a one-bit base and a two-bit delta.  I
  123.        * used http://burtleburtle.net/bob/hash/avalanche.html to choose
  124.        * the operations, constants, and arrangements of the variables.
  125.        * 
  126.        * This does not achieve avalanche.  There are input bits of (a,b,c)
  127.        * that fail to affect some output bits of (a,b,c), especially of a.
  128.        * The most thoroughly mixed value is c, but it doesn't really even
  129.        * achieve avalanche in c.
  130.        * 
  131.        * This allows some parallelism.  Read-after-writes are good at doubling
  132.        * the number of bits affected, so the goal of mixing pulls in the
  133.        * opposite direction as the goal of parallelism.  I did what I could.
  134.        * Rotates seem to cost as much as shifts on every machine I could lay
  135.        * my hands on, and rotates are much kinder to the top and bottom bits,
  136.        * so I used rotates.
  137.        *
  138.        * #define mix(a,b,c) 
  139.        * { 
  140.        *   a -= c;  a ^= rot(c, 4);  c += b; 
  141.        *   b -= a;  b ^= rot(a, 6);  a += c; 
  142.        *   c -= b;  c ^= rot(b, 8);  b += a; 
  143.        *   a -= c;  a ^= rot(c,16);  c += b; 
  144.        *   b -= a;  b ^= rot(a,19);  a += c; 
  145.        *   c -= b;  c ^= rot(b, 4);  b += a; 
  146.        * }
  147.        * 
  148.        * mix(a,b,c);
  149.        */
  150.       a = (a - c) & INT_MASK;  a ^= rot(c, 4);  c = (c + b) & INT_MASK;
  151.       b = (b - a) & INT_MASK;  b ^= rot(a, 6);  a = (a + c) & INT_MASK;
  152.       c = (c - b) & INT_MASK;  c ^= rot(b, 8);  b = (b + a) & INT_MASK;
  153.       a = (a - c) & INT_MASK;  a ^= rot(c,16);  c = (c + b) & INT_MASK;
  154.       b = (b - a) & INT_MASK;  b ^= rot(a,19);  a = (a + c) & INT_MASK;
  155.       c = (c - b) & INT_MASK;  c ^= rot(b, 4);  b = (b + a) & INT_MASK;
  156.     }
  157.     //-------------------------------- last block: affect all 32 bits of (c)
  158.     switch (length) {                   // all the case statements fall through
  159.     case 12:
  160.       c = (c + (((key[offset + 11] & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  161.     case 11:
  162.       c = (c + (((key[offset + 10] & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  163.     case 10:
  164.       c = (c + (((key[offset + 9]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  165.     case  9:
  166.       c = (c + (key[offset + 8]    & BYTE_MASK)) & INT_MASK;
  167.     case  8:
  168.       b = (b + (((key[offset + 7]  & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  169.     case  7:
  170.       b = (b + (((key[offset + 6]  & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  171.     case  6:
  172.       b = (b + (((key[offset + 5]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  173.     case  5:
  174.       b = (b + (key[offset + 4]    & BYTE_MASK)) & INT_MASK;
  175.     case  4:
  176.       a = (a + (((key[offset + 3]  & BYTE_MASK) << 24) & INT_MASK)) & INT_MASK;
  177.     case  3:
  178.       a = (a + (((key[offset + 2]  & BYTE_MASK) << 16) & INT_MASK)) & INT_MASK;
  179.     case  2:
  180.       a = (a + (((key[offset + 1]  & BYTE_MASK) <<  8) & INT_MASK)) & INT_MASK;
  181.     case  1:
  182.       a = (a + (key[offset + 0]    & BYTE_MASK)) & INT_MASK;
  183.       break;
  184.     case  0:
  185.       return (int)(c & INT_MASK);
  186.     }
  187.     /*
  188.      * final -- final mixing of 3 32-bit values (a,b,c) into c
  189.      * 
  190.      * Pairs of (a,b,c) values differing in only a few bits will usually
  191.      * produce values of c that look totally different.  This was tested for
  192.      * - pairs that differed by one bit, by two bits, in any combination
  193.      *   of top bits of (a,b,c), or in any combination of bottom bits of
  194.      *   (a,b,c).
  195.      * 
  196.      * - "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  197.      *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  198.      *   is commonly produced by subtraction) look like a single 1-bit
  199.      *   difference.
  200.      * 
  201.      * - the base values were pseudorandom, all zero but one bit set, or
  202.      *   all zero plus a counter that starts at zero.
  203.      * 
  204.      * These constants passed:
  205.      *   14 11 25 16 4 14 24
  206.      *   12 14 25 16 4 14 24
  207.      * and these came close:
  208.      *    4  8 15 26 3 22 24
  209.      *   10  8 15 26 3 22 24
  210.      *   11  8 15 26 3 22 24
  211.      * 
  212.      * #define final(a,b,c) 
  213.      * { 
  214.      *   c ^= b; c -= rot(b,14); 
  215.      *   a ^= c; a -= rot(c,11); 
  216.      *   b ^= a; b -= rot(a,25); 
  217.      *   c ^= b; c -= rot(b,16); 
  218.      *   a ^= c; a -= rot(c,4);  
  219.      *   b ^= a; b -= rot(a,14); 
  220.      *   c ^= b; c -= rot(b,24); 
  221.      * }
  222.      * 
  223.      */
  224.     c ^= b; c = (c - rot(b,14)) & INT_MASK;
  225.     a ^= c; a = (a - rot(c,11)) & INT_MASK;
  226.     b ^= a; b = (b - rot(a,25)) & INT_MASK;
  227.     c ^= b; c = (c - rot(b,16)) & INT_MASK;
  228.     a ^= c; a = (a - rot(c,4))  & INT_MASK;
  229.     b ^= a; b = (b - rot(a,14)) & INT_MASK;
  230.     c ^= b; c = (c - rot(b,24)) & INT_MASK;
  231.     return (int)(c & INT_MASK);
  232.   }
  233.   
  234.   /**
  235.    * Compute the hash of the specified file
  236.    * @param args name of file to compute hash of.
  237.    * @throws IOException
  238.    */
  239.   public static void main(String[] args) throws IOException {
  240.     if (args.length != 1) {
  241.       System.err.println("Usage: JenkinsHash filename");
  242.       System.exit(-1);
  243.     }
  244.     FileInputStream in = new FileInputStream(args[0]);
  245.     byte[] bytes = new byte[512];
  246.     int value = 0;
  247.     JenkinsHash hash = new JenkinsHash();
  248.     for (int length = in.read(bytes); length > 0 ; length = in.read(bytes)) {
  249.       value = hash.hash(bytes, length, value);
  250.     }
  251.     System.out.println(Math.abs(value));
  252.   }
  253. }