我们服务器一直在用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）的实现方式与具体细节。本篇文章将从以下几个方面展开讨论： 1. **哈希表的基本概念** 2. **哈希函数的设计** 3. **哈希表的创建与管理** 4. **...
* Collision 是 Hash Table 中的一种情况，即不同的关键字被映射到同一个索引处。 * Collision 解决方法有链地址法、开放寻址法等。 四、Hash Table 的实现 * Hash Table 的实现可以通过数组和链表等数据结构来...
- 在这个C语言实现中，哈希函数可能是一个简单的模运算，例如`hash(key) = key % size`，其中`size`是哈希表的大小。 3. **冲突解决：链地址法**： - 链地址法是为每个数组元素创建一个链表，当新键映射到已有的...
标题中的"u_hash_table.rar_Table For Two"暗示我们关注的是一个特定的哈希表实现，可能是为处理两个相关对象设计的。描述中的"compare should return 0 for two equal keys"是指哈希表在比较键（key）时，如果两个...
在“fpga-hash-table-master”这个项目中，我们可以预期找到以下内容： 1. **设计文档**：可能包含关于如何在FPGA上实现哈希表的详细设计文档，包括架构描述、性能预期和优化策略。 2. **源代码**：可能包括用...
代码重点是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_...
总的来说，"All hash ids_hash_Table_"是一个利用哈希表技术创建的作弊表，其核心在于高效的数据存取，这在游戏开发中具有重要意义，尤其是在需要快速响应用户输入或处理大量数据时。理解哈希表的工作原理和优化策略...
在GLib中，可以使用`g_hash_table_new()`函数创建一个新的哈希表，该函数需要两个参数：一个哈希函数和一个比较函数。哈希函数负责计算键的哈希值，比较函数则用于判断两个键是否相等。 3. **插入与查找** 使用`g...
哈希表（Hash Table）是一种数据结构，它通过计算一个称为哈希函数的特定值，将数据快速存储和检索。在VC（Visual C++）编程环境中，创建哈希表是提高程序性能的重要手段，尤其在处理大量数据时，能够实现近乎常数...
1. **Insert_Hash** 函数：该函数接收一个员工资料数组和数组的大小作为参数，其功能是将这些员工信息按照员工的ID映射到哈希表中。你需要根据员工的ID调用哈希函数（HashFun）来计算出在哈希表中的位置，并将员工...
在本例"test_hash_table.rar"中，我们将深入探讨如何构建和使用一个简单的哈希表，并通过Dev-C++编译器进行实践。 哈希表的基本思想是利用哈希函数解决键值对（key-value pair）的存储问题。哈希函数将键转换为数组...
在Java编程语言中，哈希表（Hash Table）是一种常用的数据结构，它的实现通常通过`Hashtable`类。这个数据结构提供了快速的插入、删除和查找操作，其平均时间复杂度为O(1)。`Hashtable`是Java集合框架的一部分，位于...
在纽约大学的数据结构课程中，学生们被分配了一个名为"tree-hash-table-homework"的作业，这个作业重点探讨了两种重要的数据结构：树（特别是红黑树）和哈希表。下面将详细解释这两个概念及其相关知识。 首先，让...
hash 表是我们经常使用的一种存储数据的结构，它查找性能不会因为数据的增长而下降。
在数组实现中，每个元素是一个键值对，键是字符串或数字，值是数据。在链表实现中，每个元素是一个链表节点，链表节点包含键和值。 散列表的应用 散列表有很多应用，例如： * 缓存系统：散列表可以用来实现缓存...
`uthash`是一个开源的C宏库，专门用于简化哈希表的实现，它提供了高效且易于使用的接口，使程序员能够快速构建自己的哈希表结构。 哈希表的关键组成部分包括哈希函数、冲突解决策略和存储结构。哈希函数负责将键...
哈希表是一种在计算机科学中广泛使用的数据结构，它的核心思想是通过散列函数将键（Key）映射到一个固定大小的数组中，从而实现快速查找、插入和删除操作。在C++中，实现哈希表可以帮助我们优化对大量数据的处理效率...
标题中的"a-similar-map-simple-hash-table.rar_Table"指的是一个使用C语言实现的类似于地图的数据结构，这个数据结构是一个简单的哈希表。哈希表是一种高效的数据存储方式，它通过哈希函数将键（key）映射到数组的...
分布式哈希表（DHT，Distributed Hash Table）是一种用于分布式环境的数据存储技术，它将数据分布在网络中的多个节点上，以实现高效、可扩展的数据管理和检索。DHT的设计目标是提供一种全局一致性的哈希函数，使得...
在编程领域，哈希表（Hash Table）是一种高效的数据结构，它通过计算字符串的哈希值来实现快速的查找、插入和删除操作。哈希表通常由数组和哈希函数组成，其中哈希函数将键（Key）映射到数组的特定位置。在这个场景...