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