62

我遇到了一个很好的问题，它是相似的，但完全不一样，因为它谈到了 Java，它具有不同的哈希表实现，凭借同步的访问器 /mutators： HashMap 和 Hashtable 之间有什么区别爪哇？

set那么和的 C++ 实现有什么区别unordered_set呢？这个问题当然可以扩展到其他 C++ 容器的mapvsunordered_map等等。

这是我的初步评估：

set：虽然标准没有明确要求将其实现为树，但时间复杂性约束要求其查找/插入操作，这意味着它将始终以树的形式实现。通常作为 RB 树（如 GCC 4.8 中所见），它是高度平衡的。由于它们是高度平衡的，因此它们具有可预测的时间复杂度find()

优点：紧凑（与其他 DS 相比）

缺点：访问时间复杂度为 O(lg n)

unordered_set：虽然标准没有明确要求将其实现为树，但时间复杂性约束要求其查找/插入操作，这意味着它将始终作为哈希表实现。

优点：

  1. 更快（承诺为搜索摊销 O(1)）
  2. 与 tree-DS 相比，易于将基本原语转换为线程安全

缺点：

  1. 查找不保证是 O(1)。理论上最坏的情况是 O(n)。
  2. 不像树那么紧凑（出于实际目的，负载因子永远不会是 1）。

注意：哈希表的 O(1) 来自没有冲突的假设。即使负载因子为 0.5，每第二个变量插入都会导致碰撞。可以观察到，哈希表的负载因子与访问其中元素所需的操作数成反比。我们减少了更多#operations，更稀疏的哈希表。当存储的元素的大小与指针相当时，开销就相当大了。

我是否错过了应该知道的用于性能分析的 map/set 之间的任何区别？

4

4 回答 4

29

我认为您通常已经回答了自己的问题，但是，这是：

不像树那么紧凑。（出于实际目的，负载因子永远不会是 1）

不一定是真的。一个类型的树的每个节点（我们假设它是一棵红黑树）T使用的空间至少等于2 * pointer_size + sizeof(T) + sizeof(bool). 这可能3 * pointer size取决于树是否包含parent每个树节点的指针。

load factor < 1将此与哈希映射进行比较：由于您所说的事实，每个哈希映射都会浪费数组空间。但是，假设哈希映射使用单链表进行链接（实际上，没有真正的理由不这样做），插入的每个元素只取sizeof(T) + pointer size.

请注意，此分析忽略了可能来自对齐使用的额外空间的任何开销。

对于任何尺寸较小的元素T（因此，任何基本类型），指针的大小和其他开销占主导地位。在> 0.5（例如）的负载因子下，std::unordered_set可能确实比等效的std::set.

另一个重要的缺失点是std::set，根据给定的比较函数，遍历 a 可以保证产生从最小到最大的排序，而遍历 anstd::unordered_set将以“随机”顺序返回值。

于 2013-04-18T07:28:44.627 回答
11

另一个区别（尽管与性能无关）是set插入不会使迭代器无效，而unordered_set如果它触发了重新散列，则插入可以。在实践中，这是一个非常小的问题，因为对实际元素的引用仍然有效。

于 2013-04-19T18:35:05.447 回答
2

Yuushi 已经很好地解决了空间效率和其他问题；我将评论问题的其他几个部分......

哈希表的 O(1) 来自没有冲突的假设。

这不是真的。O(1) 的意思并不是第一次查找尝试总是会成功，而是平均而言，需要的尝试次数是恒定的，而不是随着值数量的增加而增加。例如，使用unordered_setor ... _map，max_load_factor构造时默认为 1.0，如果负载因子通过良好的散列函数接近该值，则散列到任何一个桶的平均元素数将在 2 左右，无论有多少值在表中。

即使负载因子为 0.5，每第二个变量插入都会导致碰撞。

没错，但它并没有你想象的那么可怕：在 1.0 的负载因子下，平均链长度为 2 还不错。

可以观察到，哈希表的负载因子与访问其中元素所需的操作数成反比。我们减少了更多#operations，更稀疏的哈希表。

肯定存在相关性（不是相反的）。

于 2018-02-13T08:16:14.880 回答
1

在某些情况下set更方便。

例如使用vector作为键：

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3

之所以vector<int>会在set因为vectoroverride operator<。

但是如果你使用unordered_set<vector<int>>你必须创建一个散列函数vector<int>，因为向量没有散列函数，所以你必须定义一个像：

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

你可以看到在某些情况下unordered_set更复杂。

主要引用自： https ://stackoverflow.com/a/29855973/6329006

之间的更多区别unordered_set，set请参见：https ://stackoverflow.com/a/52203931/6329006

于 2018-09-06T12:25:59.460 回答