在打算搭建memcache集群的时候，使用了crc3算法来对key进行hash，然而发现该算法性能比较低，于是寻找一个高性能，低碰撞的hash算，很高兴有前人已经为我们发明了这种算法——murmur。
MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年 Appleby被Google雇佣，随后Google推出其变种的CityHash算法。
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
//-----------------------------------------------------------------------------
// 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;
}
你可能还喜欢下面这些文章
记得第一次了解中文分词算法是在 Google 黑板报 上看到的，当初看到那个算法时我彻底被震撼住了，想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法，才知道这并不是中文分词算法研究的全部，前前后后还有很多故事可讲。在没有建立统计语言模型时，人们还在语言学的角度对自动分词进行研究，期间诞生了很多有意思的理论。中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？人来判断很容易，要交给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是
未来项目可能要上memcache集群，memcache集群的key分配完全在客户端完成，服务端不做任何处理，这里对key进行分配节点的最优方式就是使用一致性哈希。记得以前用mysql进行分库分表的时候，通常会用一个求余作为哈希函数，这样一些id就能对应相应的表了。不过使用mysql的时候，我们不需要考虑这些节点失效问题，以及节点增加或者减少的问题（在此之前应该做好足够的计划和准备），但是对于缓存，通常就比较宽松了，允许节点失效问题，但是普通的hash分配在节点失效之后，大部分的缓存位置都改变了，这显然个灾难，这个时候就要考虑一致性hash了，在增加或者删除节点，只有小部分的key会受影响。一致
特征工程是数据分析中最耗时间和精力的一部分工作，它不像算法和模型那样是确定的步骤，更多是工程上的经验和权衡。因此没有统一的方法。这里只是对一些常用的方法做一个总结。本文关注于特征选择部分。后面还有两篇会关注于特征表达和特征预处理。1. 特征的来源在做数据分析的时候，特征的来源一般有两块，一块是业务已经整理好各种特征数据，我们需要去找出适合我们问题需要的特征；另一块是我们从业务特征中自己去寻找高级数据特征。我们就针对这两部分来分别讨论。2. 选择合适的特征我们首先看当业务已经整理好各种特征数据时，我们如何去找出适合我们问题需要的特征，此时特征数可能成百上千，哪些才是我们需要的呢？第一
Excel宏使用的是vba，基本上就是运行在Excel里面的vb。所以学习vba和学习一门编程语言没有什么区别。所以我们最开始需要学的的就是一些基础语句。为了不让学习显得太枯燥，我们从一个hello world开始。首先需要打开Microsoft Excel，找到开发工具->宏，输入一个宏名称，点击创建创建了新的宏之后，就会出现一个编辑器界面Sub test()End Sub使用一个弹窗弹出hello worldSub test()MsgBox("hello world")End Sub到这里，一个简单的宏就创建完成了，虽然它现在什么也不能做，但是别着急，后面宏会为你做很多很多的事情，能
赞赏
微信赞赏
支付宝赞赏
