我们服务器一直在用boost/sgl stl的hash table,但是从来没有考虑过其中的效率问题,虽然hash_map/unordered_map跑的可能真的比map快一些,可能应该不是你理解的那么快.其实他可以更快一些!!!
当我自己尝试着实现了一个hash table之后,我发现确实如此.这篇文章也是来说说,如何实现较快的一个.
通常的hash table都是用开链法,开放地址法来解决冲突.开链法是总容易实现的一个,而且因为效率稳定,被加入了C++11,取名unordered_map.不过效率实在不咋地.
开放地址法的hash table,我是从google-sparsehash里面注意到的,虽然数据结构,算法导论都会讲到.网上说速度很快,我就去看了一下API,其比普通的unordered_map多了一组API:
1. set_empty_key/set_deleted_key
在开链法中,所有的节点都是容器内的内容,可是开放地址法中不是的.所以需要额外的信息来维护节点的可用性信息.
当时我看到这两个API,大概就猜到内存是怎么实现的,闲来无事就是试着写了一个demo,在VC 2008下面跑的结果是,比unordered_map快一倍多;在Linux x64 gcc 4.4下面的结果是,比unordered_map快了将近1倍.
2. 高性能的hash table必须是开放地址法的
这么说,是有原因的.链表的特性就是容易删除,容易插入.可是hash table不需要这些特性,hash table只需要快.可以链表这东西,偏偏做不到快速定位,虽然你知道有下一个节点,但是你不知道下一个节点的准确位置,经常会造成缓存未命中,浪费大量时间.
3. bucket的容量
bucket的容量也是影响hash table性能的一个因素.无数的数据结构和算法书籍,都教导大家,通过质数取余数,可以获得比较好的下标分布.可是,无论是除法还是乘法,消耗都是相当高的.十几个或者几十个时钟周期,始终比不上一两个时钟周期快.所以,高性能的hash table必须要把bucket的容量设置成2^n.google-sparsehash里面初始容量是32.扩容的话,都是直接左移;算下标的话,都是(容量-1) & hash_value,简单的一个位运算搞定.
4. 正确实现find_position
我自己实现的hash table,是线性探测法的.所以find position也是比较简单,就是通过hash value和掩码,获取到其实下标,然后一个一个test.需要把buckets当作是环形的,否则buckets最末位的数据冲突就会不好搞.(我当时没有考虑这一点,直接给他扩容了.....)
5. 对象模型
不同的Key和Value模型,可以导致你对Hash Table的不同实现.简单的说,在C里面,你可以不用考虑Key和Value的生命周期(:D),但是C++里面,你不得不考虑Key,Value的生命周期问题.你不能做一个假设,key和value都是简单数据类型.一个int映射到一个对象,这种经常会用到的.
所以,erase一个key的时候,需要把key设置成deleted,然后还要把value重置一遍.如果没有重置,对象所引用的内存有可能就会被泄露.
这引发了我另外一个想法,就是通过模板,来特化Value的reset行为.因为不是所有的Value都是需要被重置的,只有那些复杂对象,才需要.
6. 可以考虑缓冲hash value
如果key都是简单数据,而非string或者复杂的数据类型,缓冲是没有任何意义的,因为hash value可以被快速的计算出来;但是当key是char*,或者一些复杂的数据类型,缓冲就会变的有意义.而且缓冲更有利于重排,容器扩容的时候速度会更快一些.
7. 考虑使用C的内存分配器
尽量不要使用C++的new/delete来分配内存.new,delete会有对象的构造,析构过程,这可能不是你所希望的.针对key和value数据类型的不同,你可能会有自己的特有的构造,析构过程.而且,C的内存分配器,同样可以被一些第三方库优化,比如tcmalloc/jemalloc等.
8. 选一个好的Hash函数(这是最重要的)
差不多就这些.后来自己写的那个demo,性能差不多和google-sparsehash一样...
参考:
1. 算法导论
2. 计算机程序设计艺术
3. google-sparsehash dense_hash_map的实现, http://code.google.com/p/google-sparsehash
/**********************************************************************
* 机械教条主义
*
* From: http://www.cnblogs.com/egmkang/
* Email: egmkang [at] 163.com
* QQ Group: 20240291(慎入,可能没人打理)
* Weibo: http://weibo.com/egmkang
*
**********************************************************************/
分享到:
相关推荐
c语言hash table的实现:经典代码段
这个小程序实现了哈希表的主要内容。有哈希函数、冲突避免,实现了插入和查找。主要是作为一个教学的例子存在。 本程序用Visual Studio 2005实现。
代码重点是hash_table,附加std::map与其做对比,实现的是一条sql语句:select c_nationkey, c_mktsegment, count(*), max(c_acctbal) from aaa_customer_1g group by c_nationkey, c_mktsegment order by c_...
一个简单的hash table实现类,实现了插入删除查询操作
现行哈希的C++实现代码,具体原理可以参考:Larson, Per-Ake (April 1988),"Dynamic Hash Tables",Communications of the ACM 31: 446–457, doi:10.1145/42404.42410.
哈希表 的C++ 代码实现
Java哈希表Java Hash Table的实践与实现
严蔚敏数据结构与算法 课本算法实现
散列表的每一个位置叫做槽,能够存放一个数据项,并以从0开始递增的整数命名。 初始条件下,散列表中是没有任何数据的,即每个槽都是空的,默认值为None 散列函数:某个数据项与存储它的槽之间的映射角做散列函数。 ...
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;你将看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;你...
因此,如果我们运行应用程序的多个实例,所有内容提供者实例都会形成一个 Chord 环,并根据 Chord 协议以分布式方式提供插入/查询请求。 实现了三个主要功能 ID空间分区/重新分区, 基于环的路由,以及 节点加入...
LRU算法的C++实现类。封装得不错,建议采用。
用C写的一个类似map的简单散列表,用于读取自定义的配置项,可以实现大量配置项的快速访问。
1. 基础知识 3 2. 环的原子管理算法 4 3. 路由算法 10 4. 组通信算法 15 5. 副本管理算法 17 6. 分布式哈希表的应用 21 1. 基
URL收集: 爬虫从一个或多个初始URL开始,递归或迭代地发现新的URL,构建一个URL队列。这些URL可以通过链接分析、站点地图、搜索引擎等方式获取。 请求网页: 爬虫使用HTTP或其他协议向目标URL发起请求,获取网页的...
性能很高的计算字符串或文件hash值的函数,比md5速度快得多,自己一直用着,重复的几率为很底,一般的应用足够, var I64BIT_TABLE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-'.split...
Linux 内核的实现,大量使用了数据结构,包括了数组、链表和散列表。其中用的最多的是双向循环链表。 Linux 内核使用的是自己定义的链表和散列表,简单而高效,使用方法也非常的别具一格。
The Joys of Hashing,Hash Table Programming with C,2019年新书,哈希编程的乐趣,基于C语言实现Hash表。
Each state machine takes as input commands from its log. In our hash table example
我将基于Chord的简单DHT设计为学术任务的一部分。 尽管设计基于Chord,但它是Chord的简化版本。 我们不需要实现手指表和基于手指的路由。我实现的三件事是:1)ID空间分区/重新分区,2)基于环的路由和3)节点联接...