package com.dy.common.util; /** * MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年， * 现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年 * Appleby被Google雇佣，随后Google推出其变种的CityHash算法。 * * 官方网站：https://sites.google.com/site/murmurhash/ * * MurmurHash算法，自称超级快的hash算法，是FNV的4-5倍。官方数据如下： * * OneAtATime – 354.163715 mb/sec * FNV – 443.668038 mb/sec * SuperFastHash – 985.335173 mb/sec * lookup3 – 988.080652 mb/sec * MurmurHash 1.0 – 1363.293480 mb/sec * MurmurHash 2.0 – 2056.885653 mb/sec * * 但也有文章声称，只有当key的长度大于10字节的时候，MurmurHash的运算速 * 度才快于DJB。从计算速度上来看，MurmurHash只适用于已知长度的、长度比 * 较长的字符。 * * 哈希值分布非常均匀，即低碰撞率 * 比Crc16更为均匀 */ public final class MurmurHash { private byte[] toBytesWithoutEncoding(String str) { int len = str.length(); int pos = 0; byte[] buf = new byte[len << 1]; for (int i = 0; i < len; i++) { char c = str.charAt(i); buf[pos++] = (byte) (c & 0xFF); buf[pos++] = (byte) (c >> 8); } return buf; } /** * 刘润玉增加方法于2016-12-02 * @param data * @param length * @return */ public int hash16_plus(final byte[] data, int length) { int hash = hash32(data, length, 0x9747b28c); hash = hash % 65535 ; if(hash < 0){ hash = - hash ; } return hash ; } /** * 刘润玉增加方法于2016-12-02 * @param data * @return */ public int hash16_plus(final String data) { byte[] bytes = toBytesWithoutEncoding(data); int hash = hash32(bytes, bytes.length, 0x9747b28c); hash = hash % 65535 ; if(hash < 0){ hash = - hash ; } return hash ; } /** * Generates 32 bit hash from byte array with default seed value. * @param data byte array to hash * @param length length of the array to hash * @return 32 bit hash of the given array */ public int hash32(final byte[] data, int length) { return hash32(data, length, 0x9747b28c); } public int hash32(final String data) { byte[] bytes = toBytesWithoutEncoding(data); return hash32(bytes, bytes.length, 0x9747b28c); } /** * Generates 64 bit hash from byte array with default seed value. * @param data byte array to hash * @param length length of the array to hash * @return 64 bit hash of the given string */ public long hash64(final byte[] data, int length) { return hash64(data, length, 0xe17a1465); } public long hash64(final String data) { byte[] bytes = toBytesWithoutEncoding(data); return hash64(bytes, bytes.length); } /** * Generates 32 bit hash from byte array of the given length and seed. * @param data byte array to hash * @param length length of the array * @param seed initial seed value * @return 32 bit hash of the given array */ public int hash32(final byte[] data, int length, int seed) { // 'm' and 'r' are mixing constants generated offline. // They're not really 'magic', they just happen to work well. final int m = 0x5bd1e995; final int r = 24; // Initialize the hash to a random value int h = seed ^ length; int length4 = length / 4; for (int i = 0; i < length4; i++) { final int i4 = i * 4; int k = (data[i4 + 0] & 0xff) + ((data[i4 + 1] & 0xff) << 8) + ((data[i4 + 2] & 0xff) << 16) + ((data[i4 + 3] & 0xff) << 24); k *= m; k ^= k >>> r; k *= m; h *= m; h ^= k; } // Handle the last few bytes of the input array switch (length % 4) { case 3: h ^= (data[(length & ~3) + 2] & 0xff) << 16; case 2: h ^= (data[(length & ~3) + 1] & 0xff) << 8; case 1: h ^= (data[length & ~3] & 0xff); h *= m; } h ^= h >>> 13; h *= m; h ^= h >>> 15; return h; } /** * Generates 64 bit hash from byte array of the given length and seed. * @param data byte array to hash * @param length length of the array to hash * @param seed initial seed value * @return 64 bit hash of the given array */ public long hash64(final byte[] data, int length, int seed) { final long m = 0xc6a4a7935bd1e995L; final int r = 47; long h = (seed & 0xffffffffl) ^ (length * m); int length8 = length / 8; for (int i = 0; i < length8; i++) { final int i8 = i * 8; long k = ((long) data[i8 + 0] & 0xff) + (((long) data[i8 + 1] & 0xff) << 8) + (((long) data[i8 + 2] & 0xff) << 16) + (((long) data[i8 + 3] & 0xff) << 24) + (((long) data[i8 + 4] & 0xff) << 32) + (((long) data[i8 + 5] & 0xff) << 40) + (((long) data[i8 + 6] & 0xff) << 48) + (((long) data[i8 + 7] & 0xff) << 56); k *= m; k ^= k >>> r; k *= m; h ^= k; h *= m; } switch (length % 8) { case 7: h ^= (long) (data[(length & ~7) + 6] & 0xff) << 48; case 6: h ^= (long) (data[(length & ~7) + 5] & 0xff) << 40; case 5: h ^= (long) (data[(length & ~7) + 4] & 0xff) << 32; case 4: h ^= (long) (data[(length & ~7) + 3] & 0xff) << 24; case 3: h ^= (long) (data[(length & ~7) + 2] & 0xff) << 16; case 2: h ^= (long) (data[(length & ~7) + 1] & 0xff) << 8; case 1: h ^= (long) (data[length & ~7] & 0xff); h *= m; } ; h ^= h >>> r; h *= m; h ^= h >>> r; return h; } public static void main(String[] args) { test1() ; test2() ; } public static void test1() { String regionNum = "110000" ; String temp = "" ; String rtuAddr = "" ; int total0 = 0 ; int total1 = 0 ; int total2 = 0 ; int total3 = 0 ; int total4 = 0 ; int total5 = 0 ; int totalx = 0 ; int totaly = 0 ; MurmurHash mhash = new MurmurHash() ; Long start = System.currentTimeMillis() ; for(int i = 0 ; i < 10000; i++){ temp = "" + i ; while(temp.length() < 5){ temp = "0" + temp ; } rtuAddr = regionNum + temp ; int hash = mhash.hash16_plus(rtuAddr) ; if(hash < 0){ total0++ ; } if(hash >= 0 && hash < 1000){ total1++ ; } if(hash >= 1000 && hash < 2000){ total2++ ; } if(hash >= 2000 && hash < 3000){ total3++ ; } if(hash >= 3000 && hash < 4000){ total4++ ; } if(hash >= 4000 && hash < 5000){ total5++ ; } if(hash >= 64535 && hash < 65535){ totalx++ ; } if(hash > 65535){ totaly++ ; } //System.out.println(rtuAddr + "-" + crc); } Long end = System.currentTimeMillis() ; System.out.println("用时" + ":" + (end - start)); System.out.println("0以下" + ":" + total0); System.out.println("0-1000" + ":" + total1); System.out.println("1000-2000" + ":" + total2); System.out.println("2000-3000" + ":" + total3); System.out.println("3000-4000" + ":" + total4); System.out.println("5000-6000" + ":" + total5); System.out.println("64535-65535" + ":" + totalx); System.out.println("65535以上" + ":" + totaly); System.out.println("================="); } public static void test2() { String regionNum = "110000" ; String temp = "" ; String rtuAddr = "" ; int total1 = 0 ; int total2 = 0 ; int total3 = 0 ; int total4 = 0 ; int total5 = 0 ; MurmurHash mhash = new MurmurHash() ; Long start = System.currentTimeMillis() ; for(int i = 0 ; i < 10000; i++){ temp = "" ; temp = "" + i ; while(temp.length() < 5){ temp = "0" + temp ; } rtuAddr = regionNum + temp ; int hash = mhash.hash32(rtuAddr) ; if(hash > 0 && hash < 10000000){ total1++ ; } if(hash >= 10000000 && hash < 20000000){ total2++ ; } if(hash >= 20000000 && hash < 30000000){ total3++ ; } if(hash >= 30000000 && hash < 40000000){ total4++ ; } if(hash >= 40000000 && hash < 50000000){ total5++ ; } //System.out.println(rtuAddr + "-" + crc); } Long end = System.currentTimeMillis() ; System.out.println("用时" + ":" + (end - start)); System.out.println("0-10000000" + ":" + total1); System.out.println("10000000-20000000" + ":" + total2); System.out.println("20000000-30000000" + ":" + total3); System.out.println("30000000-40000000" + ":" + total4); System.out.println("50000000-60000000" + ":" + total5); System.out.println("================="); } }