C++中怎么正确使用hashmap

这篇“C++中怎么正确使用hashmap”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++中怎么正确使用hashmap”文章吧。首先回顾一下hash冲突的解决方案有哪些。open addressing是通过探测或者搜索数组的方法找到未使用的bucket来解决hash冲突的。 优点： *当hash冲突很小的时候，只需要访问对应的bucket就能获得对应的pair，不需要再查找额外的数据结构，性能较好。 缺点： * 对hash函数的要求比较高，否则当hash冲突很大的时，查找速度会很慢。或者叫closed addressing，当发生hash冲突时需要通过额外的数据结构来处理，比如链表或者红黑树。 优点： *hash冲突处理简单，比如采用链表来解决hash冲突的话，添加节点的时候直接在链表后面添加即可。 * 对hash函数要求会低一点，即便冲突稍微大一点，也能把查找速度控制得比较好。 缺点： * 由于需要额外的数据结构处理，性能在一般情况下不如Open addressing。STL采用的是Separate chaining的方案。使用链表挂在bucket上解决冲突，当链表超过一定长度时转换为红黑树。一般的开源库都会提供两种memory layout，一种叫flat，另一种叫node。flat实现是指存储pair的时候是直接存到对应的节点上。 优点： * 对比node少一次寻址，对cache更加友好，查找速度会更高。 缺点： * 对象不稳定，rehash的时候对象地址会修改，如果对象是个大结构的话rehash时的开销会比node要大。node实现是指在节点上只存储pair的地址。而pair则存储在另一块内存上。 优点： * 对象稳定，rehash的时候对象地址不修改，且rehash的效率不会被结构体影响。 缺点： * 查找多一次寻址，对cache不友好，查找速度会比flat要慢。STL用的是Node的实现。每个pair都是stable的。在hash冲突上，大部分的开源实现都选择了Open addressing这种方式，毕竟理论性能会更好，而flat和node则是两种实现都会提供。结合上面说的各种优缺点，我们可以简单得出一套通用的方案。首先考虑下面几个点：1. 是否可以一开始就可以确定好容量。2. key的copy开销是否很大。3. value的copy开销是否很大。4. value的地址不稳定是否会影响代码逻辑。可以简单归纳为以下四种情况：情况1:value可以是不稳定的，而且容量是已知的，可以一开始确定。 推荐：使用flat实现，通过一开始reserve两倍的size来减少rehash带来的开销。情况2:value可以是不稳定的，容量未知，key和value的copy开销很小。 推荐：使用flat实现。情况3:value可以是不稳定的，容量未知，key的copy开销很小但value的copy开销很大。 推荐：使用flat实现，value使用unique_ptr包裹起来。其他情况均使用node结构。上面提到的规则基本可以适用大部分情况，但也不是没有例外，比如笔者在用这套规则去测试robinhood的性能的时候发现行不通，robinhood在绝大部分情况下都是node的实现性能会更高，除非value是个十分简单的结构。通过分析发现，这主要是因为以下两个原因：1.robinhood在emplace的时候会有移动pair的操作，这使得如果pair的copy代价很高，性能会大打折扣。2.robinhood实现了自己的allocator来分配node的内存，使得调用malloc的次数大约为log(n)次，并且内存连续的情况会变多，对CPU Cache比一般的node实现要友好。具体我们可以看看源代码，首先是emplace的实现。这里robinhood有一个很神奇的操作，它在info里面存了一个distance，这个distance表示当前元素所在位置与初始位置的距离，简单举例，假设我插入了4个key，分别为a,b,c,d。sequence1：插入a，hash(a) == 0，此时index0是空的，直接插入。它的distance(0, 0) == 0。sequence2：插入b，hash(b) == 1，此时index1是空的，直接插入。它的distance(1, 1) == 0。sequence3：插入c，hash(c) == 1，此时index1存在，那么找到下一个位置2插入，它的distance(1, 2) == 1。sequence4：插入d，hash(d) == 1，此时index1和2都存在，找到位置3插入，它的distance(1, 3) == 2。至于它的移动操作是怎么来的呢，假设基于上面的流程此时再加一个插入元素e的操作，并且这时候hash(e) == 0，首先是index0，发现这个位置两者的distance是相同，所以跳过看下一个。而index1则满足条件（新的距离>当前b这个key的距离），所以会把e放到index1这个位置，并且找到下一个空白的位置index4，然后把c, d这两个元素后移，最终会变成下面这个图。分配内存这块就比较简单了。每次都分配比原来更多的内存，所以大概是分配log(n)次。所以如果是用的robinhood，笔者建议除非你的pair真的是非常简单的结构，否则都是用node实现会好一点。或者你可以交给robinhood自己判断，不显示指定使用flat还是node，robinhood的模板会自动免费云主机域名根据你的size去判断去使用哪个实现。这里附带上一个简单的benchmark测试robinhood和absl的性能，测试的key是uint32_t类型，value是个120size的结构。测试代码如下测试结果可以看到，在value copy rare的场景，absl的性能完全遵循上面提到的规则，而robinhood在这种情况下，emplace+construct+deconstruct是node更快，查找和遍历几乎和flat没区别。横向对比absl和robinhood两者的话，在查找和遍历上都是absl更快，emplace+construct+deconstruct在优化到极致的情况下两者差不多，robinhood并没有比absl快多少。当然，这只是简单测试，针对key类型不同的场景可能两者速度不太一样，具体就需要更加详细的benchmark了。笔者也尝试过极简类型的场景，结论也没有违背上面的规则，都是flat速度远大于node。建议：从两者里面选择的话，如果选型是用flat的话建议用absl，是node的话建议用robinhood。以上就是关于“C++中怎么正确使用hashmap”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注百云主机行业资讯频道。

相关推荐: C++中怎么使用字符串分割函数

这篇文章主要介绍“C++中怎么使用字符串分割函数”，在日常操作中，相信很多人在C++中怎么使用字符串分割函数问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++中怎么使用字符串分割函数”的疑惑有所帮助！接下来，请跟着小编一起来学…