- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我在 C++11 中使用 std::unordered_map。我在字符串键和复合数据类型之间做出决定(比如将两个 long 放在一个结构中以保存 UUID)。
当 hashmap 使用 std::string 键时与 hashmap 使用其他一些简单数据类型作为键时,是否有一种简单的方法来确定查找、插入、删除等的性能特征?
一旦我选择了一种数据类型:std::unordered_map 的搜索、删除和插入操作都是常数时间在 map 中的元素数量,但是如果我有一个很长的键 (例如,128 位),我开始怀疑这些操作在 key 大小方面的性能。
这是值得关注的事情,还是差异可以忽略不计?
最佳答案
我认为您误解了 std::unordered_map
的复杂性保证的插入、删除和查找操作。最坏情况O(size())
只有当你为 Key
实现了一个糟糕的散列函数时才会提到产生大量冲突的类型,但不同的键比较不相等。
说你有
struct terrible_hash
{
std::size_t operator()(int i) const
{ return 42; }
};
std::unordered_map<int, foo, terrible_hash> m;
在上面的映射中所有新键的插入都是O(m.size())
因为函数将被迫线性搜索每个元素,因为它们都散列为相同的值。
给定一个合适的哈希函数,这些操作应该是(摊销的)常数时间。
回到你的问题string
与 128 位数字 (UUID) 作为 key 类型;这取决于您的实现,但通常后者应该更快。我这样说是基于以下假设:
典型 hash<string>
特化将遍历整个字符串并对每个字节执行按位数学运算并将其与现有结果组合。例如,部分/简化的实现取自 VS2013:
size_t _Val = 14695981039346656037ULL;
for (size_t _Next = 0; _Next < _Count; ++_Next)
{
_Val ^= (size_t)_First[_Next];
_Val *= 1099511628211ULL;
}
return _Val;
使用您的 128 位 key 类型,您应该能够组合两个 64 位字以生成具有更少操作的散列。例如,您可以定义一个辅助函数模板,并使用它来组合来自 64 位单词的哈希值。
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
魔数(Magic Number)是从 boost::hash_combine
偷来的.再次查看 std::hash<uint64_t>
的 MSVC 实现,它们通过 unsigned char *
别名为 64 位整数并调用我上面粘贴的算法,但在这种情况下,迭代次数是已知的,编译器将能够更好地优化。
话虽如此,如果性能非常重要,您需要衡量两种键选择,然后再做出决定。
关于c++ - std::unordered_map:渐近 {search,insert,remove} 在键的大小和数据类型方面的表现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22002615/
我正在尝试编写一个相当多态的库。我遇到了一种更容易表现出来却很难说出来的情况。它看起来有点像这样: {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE
谁能解释一下这个表达式是如何工作的? type = type || 'any'; 这是否意味着如果类型未定义则使用“任意”? 最佳答案 如果 type 为“falsy”(即 false,或 undef
我有一个界面,在IAnimal.fs中, namespace Kingdom type IAnimal = abstract member Eat : Food -> unit 以及另一个成功
这个问题在这里已经有了答案: 关闭 10 年前。 Possible Duplicate: What is the difference between (type)value and type(va
在 C# 中,default(Nullable) 之间有区别吗? (或 default(long?) )和 default(long) ? Long只是一个例子,它可以是任何其他struct类型。 最
假设我有一个案例类: case class Foo(num: Int, str: String, bool: Boolean) 现在我还有一个简单的包装器: sealed trait Wrapper[
这个问题在这里已经有了答案: Create C# delegate type with ref parameter at runtime (1 个回答) 关闭 2 年前。 为了即时创建委托(dele
我正在尝试获取图像的 dct。一开始我遇到了错误 The function/feature is not implemented (Odd-size DCT's are not implemented
我正在尝试使用 AFNetworking 的 AFPropertyListRequestOperation,但是当我尝试下载它时,出现错误 预期的内容类型{( “应用程序/x-plist” )}, 得
我在下面收到错误。我知道这段代码的意思,但我不知道界面应该是什么样子: Element implicitly has an 'any' type because index expression is
我尝试将 SignalType 从 ReactiveCocoa 扩展为自定义 ErrorType,代码如下所示 enum MyError: ErrorType { // .. cases }
我无法在任何其他问题中找到答案。假设我有一个抽象父类(super class) Abstract0,它有两个子类 Concrete1 和 Concrete1。我希望能够在 Abstract0 中定义类
我想知道为什么这个索引没有用在 RANGE 类型中,而是用在 INDEX 中: 索引: CREATE INDEX myindex ON orders(order_date); 查询: EXPLAIN
我正在使用 RxJava,现在我尝试通过提供 lambda 来订阅可观察对象: observableProvider.stringForKey(CURRENT_DELETED_ID) .sub
我已经尝试了几乎所有解决问题的方法,其中包括。为 提供类型使用app.use(express.static('public'))还有更多,但我似乎无法为此找到解决方案。 index.js : imp
以下哪个 CSS 选择器更快? input[type="submit"] { /* styles */ } 或 [type="submit"] { /* styles */ } 只是好
我不知道这个设置有什么问题,我在 IDEA 中获得了所有注释(@Controller、@Repository、@Service),它在行号左侧显示 bean,然后转到该 bean。 这是错误: 14-
我听从了建议 registering java function as a callback in C function并且可以使用“简单”类型(例如整数和字符串)进行回调,例如: jstring j
有一些 java 类,加载到 Oracle 数据库(版本 11g)和 pl/sql 函数包装器: create or replace function getDataFromJava( in_uLis
我已经从 David Walsh 的 css 动画回调中获取代码并将其修改为 TypeScript。但是,我收到一个错误,我不知道为什么: interface IBrowserPrefix { [
我是一名优秀的程序员,十分优秀!