hogwarts sorting hat_huge squares
hogwarts sorting hat_huge squares
1. 概述 murmurhash是 Austin Appleby于2008年创立的一种 非加密hash算法，适用于基于hash进行查找的场景。murmurhash最新版本是MurMurHash3，支持 32位、64位及128位值的产生。 murmurhash标准使用c++实现，但是也有其他主流语言的支持版本，包括：perl、c#、ruby、python、java等。murmurhash在多个开源项目中得到应用，包括libstdc、libmemcached 、nginx、hadoop等。
CityHash是Google发布的字符串散列算法，和murmurhash一样，属于非加密型hash算法。CityHash算法的开发是受到了 MurmurHash的启发。其主要优点是大部分步骤包含了至少两步独立的数学运算。现代 CPU 通常能从这种代码获得最佳性能。 CityHash 也有其缺点：代码较同类流行算法复杂。 Google 希望为速度而不是为了简单而优化，因此没有照顾较短输入的特例。 Google 号称CityHash64 在速度方面至少能提高 30%(这个，肯定不是和murmurhash比咯)，并有望提高多达两倍。此外，这些算法的统计特性也很完备。 目前CityHash支持 64、128、256位
2.使用： 1）Murmurhash直接添加源码：
//----------------------------------------------------------------------------- // MurmurHash2, 64-bit versions, by Austin Appleby // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment // and endian-ness issues if used across multiple platforms. typedef unsigned long int uint64_t; // 64-bit hash for 64-bit platforms uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ) { const uint64_t m = 0xc6a4a7935bd1e995; const int r = 47; uint64_t h = seed ^ (len * m); const uint64_t * data = (const uint64_t *)key; const uint64_t * end = data + (len/8); while(data != end) { uint64_t k = *data++; k *= m; k ^= k >> r; k *= m; h ^= k; h *= m; } const unsigned char * data2 = (const unsigned char*)data; switch(len & 7) { case 7: h ^= uint64_t(data2[6]) << 48; case 6: h ^= uint64_t(data2[5]) << 40; case 5: h ^= uint64_t(data2[4]) << 32; case 4: h ^= uint64_t(data2[3]) << 24; case 3: h ^= uint64_t(data2[2]) << 16; case 2: h ^= uint64_t(data2[1]) << 8; case 1: h ^= uint64_t(data2[0]); h *= m; }; h ^= h >> r; h *= m; h ^= h >> r; return h; } // 64-bit hash for 32-bit platforms uint64_t MurmurHash64B ( const void * key, int len, unsigned int seed ) { const unsigned int m = 0x5bd1e995; const int r = 24; unsigned int h1 = seed ^ len; unsigned int h2 = 0; const unsigned int * data = (const unsigned int *)key; while(len >= 8) { unsigned int k1 = *data++; k1 *= m; k1 ^= k1 >> r; k1 *= m; h1 *= m; h1 ^= k1; len -= 4; unsigned int k2 = *data++; k2 *= m; k2 ^= k2 >> r; k2 *= m; h2 *= m; h2 ^= k2; len -= 4; } if(len >= 4) { unsigned int k1 = *data++; k1 *= m; k1 ^= k1 >> r; k1 *= m; h1 *= m; h1 ^= k1; len -= 4; } switch(len) { case 3: h2 ^= ((unsigned char*)data)[2] << 16; case 2: h2 ^= ((unsigned char*)data)[1] << 8; case 1: h2 ^= ((unsigned char*)data)[0]; h2 *= m; }; h1 ^= h2 >> 18; h1 *= m; h2 ^= h1 >> 22; h2 *= m; h1 ^= h2 >> 17; h1 *= m; h2 ^= h1 >> 19; h2 *= m; uint64_t h = h1; h = (h << 32) | h2; return h; }2）cityhash需要下载、配置、编译后才能使用
3.测试代码：
#include <iostream> #include <string> #include <time.h> #include "city.h" using namespace std; uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ); int main(int argc, char** argv) { char buf[1024]; time_t t1, t2; FILE* file = fopen(argv[1], "r"); int pattern = atoi(argv[2]); t1 = time(NULL); while(fgets(buf, 1024, file) != NULL) { if(1 == pattern) { MurmurHash64A(buf, strlen(buf), 16); } else { CityHash64WithSeed(buf, strlen(buf), 16); } } t2 = time(NULL); cout << (t2-t1) << endl; return 0; }生成随机字符串bash脚本：
#!/bin/sh #sh make_random_strings 16 10000 #make 10000 strings, the string length:16 for((j=0; j<$2; j++)) { str= for((i=0; i<$1; i++)) { one=`cat /dev/urandom |strings -n 1 | cut -c-1| head -1` str=${str}${one} } echo $str }测试长度16的字符串hash速度
测试数据： 735,529,084行 长度16的随机字符串 murmurhash平均耗时：94s cityhash平均耗时：86s 测试长度 32的字符串hash速度 测试数据： 262,017,242行 长度32的随机字符串 murmurhash平均耗时：33 cityhash平均耗时：33
测试长度 256的字符串hash速度 测试数据： 60,000,000行 长度256的随机字符串 murmurhash平均耗时：32 cityhash平均耗时：30 4.总结： 速度： cityhash和murmurhash相比，速度略快 使用复杂度：都非常简单 语言支持：murmurhash主流语言基本都支持；cityhash 2010才发布算法，2011年发布实现，目前只有c++的支持。 hash值位数：murmurhash支持32、64、128bit， cityhash支持64、128、256bit
reference： http://code.google.com/p/cityhash/ wiki：http://en.wikipedia.org/wiki/CityHash wiki：http://en.wikipedia.org/wiki/Murmurhash
转载于:https://my.oschina.net/zipu888/blog/549639
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/183754.html原文链接：https://javaforall.cn
腾讯云开发者
