ral*_*aul 10 c++ hash unordered-map hashmap c++11
我还没有读过C++标准,但这就是我觉得c ++的unordered_map假设可行的方式.
我很惊讶我找不到有关unordered_map如何处理内存的信息.是否存在unordered_map分配的特定初始内存大小.如果我们说我们分配了50个内存并且我们最终插入5000整数会怎么样？
这将是很多碰撞,所以我认为应该有一种像重新散列和重新调整大小的算法,以在达到一定程度的碰撞阈值后减少碰撞次数.由于它们是作为成员函数显式提供给类的,因此我假设它们也在内部使用.有这样的机制吗？
对于每个put请求,散列对象并将其映射到此内存中的空间
不幸的是,这并不完全正确.您指的是开放式寻址或封闭式散列数据结构,而不是如何unordered_map指定.
每个unordered_map实现都将链表存储到存储桶数组中的外部节点.这意味着插入项目将始终至少分配一次(新节点),如果不是两次(调整存储桶数组的大小,则调整新节点).
不,这对于实现最常见用途的哈希映射来说并不是最有效的方法.不幸的是,规范中的一个小"疏忽" unordered_map但需要这种行为.所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效.因为插入可能导致桶阵列增长(重新分配),所以通常不可能让迭代器直接指向桶阵列并满足稳定性保证.
unordered_map如果您要将昂贵的复制项目存储为您的密钥或值,那么这是一种更好的数据结构.这是有道理的,因为它的一般设计是从Boost的移动前语义设计中解脱出来的.
Chandler Carruth(谷歌)在他的CppCon '14演讲"效率与算法,性能与数据结构"中提到了这个问题.
| 归档时间： |
|
| 查看次数： |
4956 次 |
| 最近记录： |