今夜因“陌陌”而精彩，莫莫Hash在推荐系统的应用

本文来之不易，学习hash的起源是我在客户交流现场被问到hash冲突。其实这个是我的知识短板，但是因为我隐约记得有个murmurhash的东西，然后蒙混过去了。然后今天抓紧找各位大牛学习了hash在推荐系统中的作用，总结了这篇笔记。感觉自己还是太文盲了，另外也感谢客户老师以及公司内的大牛老师的指导。

0 1

推荐系统中数据如何转成稀疏数据

先来一句话概括下，Hash解决的是一个空间匹配的效率问题。理解这一句话首先要了解稠密数据和稀疏数据的区别，大家可以看看台湾某大学开源的libsvm数据格式，这个格式是目前稀疏数据的行业规范，稀疏数据的好处就是可以减少计算过程中的非0元的计算量。

ok，接下来用一个例子说明为什么在推荐领域要用Hash做特征编码。假设我们有一份推荐场景稠密数据，第一列是ID列，第二、三列是Feature列，最后一列是Label列。

ID	F1	F2	Label
A	7	6	0
B	5	9	1
C	2	2	0

这份数据转成稀疏格式（libsvm）后会是这样：

ID	KV	Label
A	2:7 1:6	0
B	1:5 2:9	1
C	0:2 0:2	0

F1和F2这两个特征列变成了K:V结构，以样本A为例，它的F1这个特征是7，在F1这三个特征中（7，5，2）排名第3，所以K值为2。它的F2这个特征是6，在F2三个特征中（6，9，2）排名第2，所以K为1。

0 2

Hash的作用

如果按照以上思路去把稠密数据转稀疏数据需要例如如下的这样的代码：

for(i=0; i<len(feature),i++ )

{ 

 #找到特征的排位确定k值

}

每一个样本的特征转换都需要遍历全部样本，如果样本数很大，效率非常差。因为这个稠密转稀疏无非是找到一个空值空间，把数据插入内存，这个时候就可以利用Hash的方式提升效率。

还以上文例子为例，我们可以把特征空间区分为两份，比如1~100的位置给到特征F1，1000~10000的位置给到特征F2。然后用一个HashFunction自动把数值映射到对应的位置上。

比如:

HashFunction(F1,7)=010

HashFunction(F2,9)=01000

这样就不需要遍历全部样本，大大提升了效率。

0 3

Hash冲突问题

在推荐领域，往往样本量非常大，每个特征的可能性也很多。比如某个特征表示的是平台的所有商品，那么如果用HashFunction的方法需要巨大的空间表示这个特征，这样才能避免相同的特征值落在相同的范围内，形成Hash冲突。但是巨大的空间意味着模型的宽度增加，对于计算效率也是有挑战。

变成一个博弈问题，Hash冲突风险越小，模型越大，人们希望风险小而且模型小。为了解决这个问题，业内有很多优质的Hash方法，比如MurmurHash、CityHash。

推荐MurmurHash，目前Redis数据库主键就是用的这个方案。因为这个Hash算法非常复杂，以我的智商应该很难理解，所以MurmurHash的详细原理，建议移步某乎。谢谢~