文档章节

Hash算法在工作中的应用

 自由的眼
发布于 2016/12/13 10:39
字数 2253
阅读 21
收藏 0
点赞 0
评论 0

目前我的其中一个项目是车务通系统,属于物联网的车辆管理实现的一部分,监控车辆的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
西城
技术主管
网站设计提纲

高性能(响应时间,并发数,TPS) 浏览器静态资源缓存 CDN缓存 反向代理服务器缓存 应用服务器本地缓存 分布式缓存服务器(Redis) 缓存数据预热 减少http请求(合并js,css,图片) http静态资...

fifadxj ⋅ 2016/08/05 ⋅ 0

闲聊 Hash 算法

最近读了一篇好文:【微信高并发资金交易系统设计方案——百亿红包背后的技术支撑】,其中关于高并发性能问题的解决方案中,有应用 hash 算法的思想。想起公众号后台里断断续续有读者提起算法...

MrPeak ⋅ 2017/02/27 ⋅ 0

一致性hash算法

问题一:一致性hash算法是由memcache服务器端实现还是客户端实现? 当然由客户端实现,一致性hash算法是实现应用程序如何把数据存储到不同的memcache服务器上,保证当memcache服务器在增加或...

洋承安 ⋅ 2013/12/21 ⋅ 0

哈希分布与一致性哈希算法简介

前言 在我们的日常web应用开发当中memcached可以算作是当今的标准开发配置了。相信memcache的基本原理大家也都了解过了,memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

Citrix Netscaler负载均衡算法

众所周知,作为新一代应用交付产品的Citrix Netscaler具有业内领先的数据控制、应用交付的能力,然而作为根本内容之一的ADC功能,如果不具备强大的、多元化的均衡算法是不可能适应如此众多的...

caojin_gene ⋅ 2017/05/16 ⋅ 0

[算法] 从 Memcached 分布式应用看一致性哈希散列函数的选择

一致性哈希算法来源于 P2P 网络的路由算法,目前主流的 P2P 软件就是利用我们所熟知的 DHT (Distributed Hash Table,分布式哈希表) 来定位整个分布式网络的信息,另外此算法在目前火热的云计...

长平狐 ⋅ 2012/11/19 ⋅ 0

安全存储密码:Hashing 还是加密?

对于网站来说, 再没有什么比用户信息泄露更让人尴尬的了。 尤其是当存有用户密码的文件如果被黑客获取, 对网站的安全和用户的信心来说都是巨大的打击。 如最近的Ebay泄密事件和小米的用户数...

oschina ⋅ 2014/06/20 ⋅ 15

到底什么是hash?它起什么作用?

从emule诞生到现在也已经有了两年左右时间了,随着emule的普及,喜欢他的人也越来越多,但是由于emule对技术相应有一个门槛,不像bt那么容易上手,所以很多朋友很长时间以来一直都有这样或那...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

让memcached分布式

转自:http://blog.csdn.net/cutesource/archive/2010/08/29/5848253.aspx memcached是应用最广的开源cache产品,它本身不提供分布式的解决方案,我猜想一方面它想尽量保持产品简单高效,另一...

flynewton ⋅ 2010/12/02 ⋅ 0

安全存储密码:Hashing还是加密?

对于网站来说, 再没有什么比用户信息泄露更让人尴尬的了。 尤其是当存有用户密码的文件如果被黑客获取, 对网站的安全和用户的信心来说都是巨大的打击。 如最近的Ebay泄密事件和小米的用户数...

安全牛 ⋅ 2014/06/20 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

磁盘管理—逻辑卷lvm

4.10-4.12 lvm 操作流程: 磁盘分区-->创建物理卷-->划分为卷组-->划分成逻辑卷-->格式化、挂载-->扩容。 磁盘分区 注: 创建分区时需要更改其文件类型为lvm(代码8e) 分区 3 已设置为 Linu...

弓正 ⋅ 12分钟前 ⋅ 0

Spring源码解析(六)——实例创建(上)

前言 经过前期所有的准备工作,Spring已经获取到需要创建实例的 beanName 和对应创建所需要信息 BeanDefinition,接下来就是实例创建的过程,由于该过程涉及到大量源码,所以将分为多个章节进...

MarvelCode ⋅ 32分钟前 ⋅ 0

a href="#"

<a href="#">是链接到本页,因为你有的时候需要有个链接的样式,但是又不希望他跳转,这样写,你可以把这个页面去试试

颖伙虫 ⋅ 39分钟前 ⋅ 0

js模拟栈和队列

栈和队列 栈:LIFO(先进后出)一种数据结构 队列:LILO(先进先出)一种数据结构 使用的js方法 1.push();可以接收任意数量的参数,把它们逐个推进队尾(数组末尾),并返回修改后的数组长度。 2....

LIAOJIN1 ⋅ 39分钟前 ⋅ 0

180619-Yaml文件语法及读写小结

Yaml文件小结 Yaml文件有自己独立的语法,常用作配置文件使用,相比较于xml和json而言,减少很多不必要的标签或者括号,阅读也更加清晰简单;本篇主要介绍下YAML文件的基本语法,以及如何在J...

小灰灰Blog ⋅ 47分钟前 ⋅ 0

IEC60870-5-104规约传送原因

1:周期循环2:背景扫描3:自发4:初始化5:请求6:激活7:激活确认8:停止激活9:停止激活确认10:激活结束11:远程命令引起的返送信息12:当地命令引起的返送信息13:文件传送20:响应总召...

始终初心 ⋅ 今天 ⋅ 0

【图文经典版】冒泡排序

1、可视化排序过程 对{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的可视化动态过程如下 2、代码实现    public void contextLoads() {// 冒泡排序int[] a = { 6, 5, 3, 1, 8, 7, 2, ...

pocher ⋅ 今天 ⋅ 0

ORA-12537 TNS-12560 TNS-00530 ora-609解决

oracle 11g不能连接,卡住,ORA-12537 TNS-12560 TNS-00530 TNS-12502 tns-12505 ora-609 Windows Error: 54: Unknown error 解决方案。 今天折腾了一下午,为了查这个问题。。找了N多方案,...

lanybass ⋅ 今天 ⋅ 0

IDEA反向映射Mybatis

1.首先在pom文件的plugins中添加maven对mybatis-generator插件的支持 ` <!-- mybatis逆向工程 --><plugin><groupId>org.mybatis.generator</groupId><artifactId>mybatis-generator-ma......

lichengyou20 ⋅ 今天 ⋅ 0

4.10/4.11/4.12 lvm讲解 4.13 磁盘故障小案例

准备磁盘分区 fdisk /dev/sdb n 创建三个新分区,分别1G t 改变分区类型为8e 准备物理卷 pvcreate /dev/sdb1 pvcreate /dev/sdb2 pvcreate /dev/sdb3 pvdisplay/pvs 列出当前的物理卷 pvremo...

Linux_老吴 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部