C++ unordered_map 的 begin() 方法最坏时间复杂度是 O(n) 吗

[feng32]

如果很不巧，哈希表前面一半正好是空的，有没有可能需要迭代很多次才能找到一个元素？

[minami]

cplusplus reference 显示是常数复杂度，应该是类内部有记录

[yuikns]

Suppose you wanna to define a special hash function (unordered_map::hasher) and always return exactly the same result. Yes

https://marknelson.us/posts/2011/09/03/hash-functions-for-c-unordered-containers.html

[yulon]

如果你需要遍历哈希表，最好加个 vector 或 list，顺便还能记录插入顺序，至于哈希表里存列表的迭代器还是列表里存哈希表的迭代器就随你选择了。

[feng32]

@yulon 然后哈希表快速删除中间一项后，重建整个 vector ？

哈希表的插入、查找、删除是 O(1) 这个我没有疑问，看起来唯一有问题的是 begin()
同时我也不希望引入一些其它的会造成 O(n) 操作的机制

[yulon]

@feng32 vector 或 [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] [list] ……

看你自己是 [重遍历] 还是 [重增删]

讲个话真累。

[feng32]

还是上面的例子，哈希表中删除一项，因为哈希表本身是无序的，不知道它在链表里的前一项和后一项是什么，结果需要搜索整条链表

当然如果哈希表节点里包含一个到链表节点的指针，就不用搜索了；遍历的时候可以选择从链表头开始遍历，这又要求链表节点有包含哈希表节点的指针；结果是链表和哈希表元素形成了双向的一一对应的关系

@yulon 这是你的解法吗

[yulon]

@feng32 你这个人是不是看不懂「或」「还是」？

unordered_map<key, value>+list<unordered_map::iterator> 或 unordered_map<key, list::iterator>+list<value> 都随你选择，到底怎么样才会理解成 unordered_map<key, list::iterator>+list<unordered_map::iterator>？？？

你要双向都能找到对方的节点就自己造一个「哈希表」和「 list 」然后共用一种「节点」类型，所以我全程都是用数据结构的名字而不是标准库里的 std::xxxx，懂了么？

[qianlv7]

@yulon unordered_map<key, value>+list<unordered_map::iterator> 不行把, rehash unordered_map::iterator 变了, 不过重建也是 O(n), 增加了常数.

[yulon]

@qianlv7 所以我一开始没写 unordered_map，那个看不懂我写了带 unordered_map 的声明，这个看了 unordered_map 又不懂迭代器可能会非法，哈希表实现那么多，自己实现个迭代器 /节点不会变非法的哈希表很难吗，再蠢点直接把 value 存个指针行不行，这时候是不是要说指针你会忘记释放，那么智能指针请，是不是还要说分配内存有性能问题还会造成碎片，因为你们不会实现哈希表啊还有什么办法，虽然说起来像套娃一样，但我知道我不补充肯定还有人钻，我真的是要疯了，还有什么需求一次性说干净，如果真的喜欢钻牛角尖，直接口吐芬芳好了。

[seasona]

应该是常数级别的，libstdc++里面是用_Hashtable，我大致看了一下源代码，应该是用一个类似于 std::forward_list 中 before_begin 的结构__before_begin，里面会存储_Hash_node_base _M_node，这个就是 begin()返回的节点。

On insert we compute the element's hash code and use it to find the bucket index. If the element must be inserted in an empty bucket we add it at the beginning of the singly linked list and make the bucket point to _M_before_begin. The bucket that used to point to _M_before_begin, if any, is updated to point to its new before begin node.

https://gcc.gnu.org/onlinedocs/gcc-4.8.5/libstdc++/api/a00974_source.html#l00174

[nightwitch]

标准规定了常数级别。

[123444a]

是个非空桶链表，o （ 1 ），大一的入学课程教的