| New file | 
|  |  |  | 
|---|
|  |  |  | 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("================="); | 
|---|
|  |  |  | } | 
|---|
|  |  |  | } | 
|---|