Hash算法在工作中的应用
Hash算法在工作中的应用
自由的眼 发表于11个月前
Hash算法在工作中的应用
  • 发表于 11个月前
  • 阅读 13
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: Hash

目前我的其中一个项目是车务通系统,属于物联网的车辆管理实现的一部分,监控车辆的GPS数据,并以此与司机互动相关信息。
由于在系统下管理的车辆比较多,将每次注册登录数据去数据库查询肯定是不现实的。所以,放在本地共享内存中成了一个比较好的缓冲,之所以没有考虑一些分布式的cache层,主要考量是机器成本(移动给的机器不多)。本地共享内存有一个好处是,没有多余的IO操作,数据不依赖进程而存在。
车务通项目的车辆数据,在程序启动后,判定共享内存是否存在,如果不存在则从数据库取得数据放在共享内存中。
当初最早的实现,是将所有车辆数据(主键是MSISDN),先从数据库中读取出来,然后进行排序。排序后存入共享内存中。
在查找车辆的时候,提供二分查找的方式命中。
但是这样的设计,在车辆频繁添加的时候,会很慢,为什么?每次都必须将新数据重新排序所有的数据,随着车辆的增加,这种排序的时间劣势也就显现出来了。
后来我改造了这个算法,所有的车辆数据入共享内存不需要排序,数据加载的时候,生成一个map图去映射相关的数据位置。这个map图也已一种形式,去存入共享内存中,将共享内存区分头和体部分。分别存储,但是在数据删除和添加的时候,需要维护两个内存的地方,在高并发的环境下,容易出现映射不对的问题。
这个也不是最优方案,但是比之前的好了很多。起码速度快了一些。但是我还是很不满意的。
说到这个问题,实际也说明了自己当初的一个弱点,过于依赖STL容器。
后来无意间,看到暴雪关于《暗黑2》的资源加载代码。
忽然产生了灵感,它的代码使用了Hash算法,生成资源包对应资源映射。
于是拿下来研究了一下,自己实现了一个Hash算法的数组封装。结果发现它的算法没有考虑到删除key的逻辑。
在我模拟的反复删除下,有BUG。
那么怎么办,那就自己去实现一下吧。
固然,所有的Hash算法最诱人的,就是o(1)命中。
这里简单的描述一下Hash算法,Hash其实没有什么神秘的,就是根据指定的key,生成一个与之匹配的数字ID,作为下标索引。从而当查询key的时候,你可以获得这个数据的下标,从而实现一次映射。
那么实时真的如此吗?
千万别被网上的文章忽悠了,Hash算法里面有一个陷阱。那就是Hash冲突。
什么是Hash冲突呢?
就拿大家都知道的MD5算法来说,它也是一个标准的Hash算法,它生成的是一个16字节的HashID数字。这是一个多大的数字呢?一个int是4个字节,也就是2的32次方。那么一个MD5的hashID就是2的256次方。
在这个数据范围量级下,它可以保证任意字符生成的数据ID是唯一的。
但是,实际使用中,我们没有这么大的内存。
有时候,对于有些数据,举个极端的例子,我们可能只需要2个hash数组的池。
那么,采用Hash算法,就会很容易产生碰撞了。也就是你算出来的数字,很可能会和别的字符算出来的数据HashID完全一致。
通常,处理Hash数组冲突的方法,是在一个数据下标下,如果发现已存在对应数据,那么就启动一个链表,记录下这个ID下所有冲突的对象。
当搜索的时候,发现这个HashID下有数据的话,就在下面的链表中去查找,直到找到匹配的key为止。
那么,这样的处理方式,实际依赖的是你冲突key的多少,比如,在一个固定的Hash数组中,一个key有10个冲突。那么,最不幸的情况下,你要付出o(10)次查找,才能定位一个唯一的数据。
这本身就打破了Hash o(1)命中的诱人神话,除非你的数组足够大。
在实际我的使用中,这里存在两个困难。
(1)我使用的是共享内存,我不可能在冲突的时候new一个内存节点去存储链表。如果把链表信息独立出来存储,就类似了以前的map头 + 数据体的模式,一样很慢,在固定内存下有很大隐患。
(2)我如何控制链表的深度?如果过深,就失去了hash命中优势。
针对这两方面,我开始做了一些测试和研究。
共享内存大小是固定的,我决定融合链表的优势,在发现hashID冲突的时候,自动将数据顺序存放在数据中以当前节点为开始,下一个空余的位置,并在之前的节点,记录冲突数据的下一个访问位置。
于是我定义了这么一个通用结构体
//hash表结构
struct _Hash_Table_Cell 
{
    char  m_cExists;                       //当前块是否已经使用,1已经使用,0没有被使用
    char* m_szKey;                         //当前的key值,没有则为空
    int   m_nKeySize;                      //当前key数据长度
    int   m_nNextKeyIndex;                 //链表信息,如果主键有冲突,记录下一个冲突主键的位置
    int   m_nProvKeyIndex;                 //链表信息,如果主键有冲突,记录上一个冲突主键的位置
    unsigned long m_uHashA;                //第二次的hashkey值
    unsigned long m_uHashB;                //第三次的hashkey值 
    char* m_szValue;                       //当前数据体指针
    int   m_nValueSize;                    //当前数据体长度
    
    _Hash_Table_Cell()
    {
        Init();
    }
    
    void Init()
    {
        m_cExists       = 0;
        m_nKeySize      = 0;
        m_nValueSize    = 0;
        m_uHashA        = 0;
        m_uHashB        = 0;
        m_nNextKeyIndex = -1;
        m_nProvKeyIndex = -1;
        m_szKey         = NULL;
        m_szValue       = NULL;        
    }
    
    void Set_Key(char* pKey, int nKeySize)
    {
        m_szKey         = pKey;
        m_nKeySize      = nKeySize;
    }
    
    void Set_Value(char* pValue, int nValueSize)
    {
        m_szValue       = pValue;
        m_nValueSize    = nValueSize;
    }
    
    void Clear()
    {
        m_cExists       = 0;
        m_uHashA        = 0;
        m_uHashB        = 0;
        m_nNextKeyIndex = -1;
        m_nProvKeyIndex = -1;        
        if(NULL != m_szKey)    
        {
            memset(m_szKey, 0, m_nKeySize);        
        }
        if(NULL != m_szValue)
        {
            memset(m_szValue, 0, m_nValueSize);
        }
    }  
};
m_nNextKeyIndex和m_nProvKeyIndex就是记录冲突数据的下一个数组下标和前一个数组下标(实现的双向链表功能)。
第二个问题实际是一个散列的问题。
我们需要将任意key值数据计算hashID计算尽量正太分布。
这里,普通的算法是直接将key(是一个字符串),按照第一个字节到最后一个字节与或。但是在大多情况下,这样的映射往往是很难足够分散的。因为你无法控制key值的摄入。
于是我在设计的时候,增加了一个符合完全正太分布的Hash数值下标,然后,在取得key值导出成对应下标的时候,再次在这个已有的hash散列中再次映射。尽量保证数据分布的属性。我姑且称这个完全的Hash散列为"秘钥"。
那么看看,秘钥是怎么生成的呢?
//生成秘钥
void CHashTable::prepareCryptTable()

  unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
  for(index1 = 0; index1 < 0x100; index1++)
  { 
    for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
    { 
      unsigned long temp1, temp2;
      seed = (seed * 125 + 3) % 0x2AAAAB;
      temp1 = (seed & 0xFFFF) << 0x10;
      seed = (seed * 125 + 3) % 0x2AAAAB;
      temp2 = (seed & 0xFFFF);
      m_cryptTable[index2] = (temp1 | temp2); 
    } 
  } 
}
这段代码,是我从暴雪的源代码里面截取出来的。一个标准的正太分布数组。

因为我的实际项目中,有部分是C的,有部分是C++的。
于是,我写了两个版本。
经过测试,100万条手机号为key的数据中,key冲突深为4。实际查询中,94%都是o(1)命中。最差的也是4次就能命中。
共享内存不需要数据头体的区分,完全以数据体就可以了。
进程加载共享内存也不必在遍历共享内存生成相关映射关系。
数据的插入也不需要在排序。直接入根据key生成去hash数组就行了。删除也是一样。
查询命中效率几乎达到了o(1)。
代码也简洁了。
效果很不错。

最后
在这里,我把源代码放上来让大家随意的玩耍,可以任意数组大小,可以支持共享内存和内存两种方式。
https://github.com/freeeyes/HashTablePool

我做了一次比较,100万次随机查询 C的查询速度是C++的35%左右。总体来说速度很快,代码也得到了很大简化。
最后祝大家玩的开心,如果有问题可以反馈给我。

共有 人打赏支持
粉丝 0
博文 9
码字总数 16565
作品 1
×
自由的眼
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: