c++ - Unordered_set 问题

Question

谁能解释一下无序集是如何工作的？我也不确定一套是如何工作的。我的主要问题是它的查找功能的效率如何。

例如，这个大 O 的总运行时间是多少？

    vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);


    theSecond.push_back(2);
    theSecond.push_back( -2147483648 );
    theSecond.push_back( 33 );


    //1) Place the contents into a unordered set that is O(m). 
    //2) O(n) look up so thats O(m + n). 
    //3) Add them to third structure so that's O(t)
    //4) All together it becomes O(m + n + t)
    unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end());

    for(int i = 0; i < theSecond.size(); i++) 
    {
        if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end()) 
        {
        theMatch.push_back( theSecond[i] );
        cout << theSecond[i];
        }
   }

Answer 1

unordered_set 和所有其他 unordered_ 数据结构都使用散列，如@Sean 所述。散列涉及用于插入的分摊常数时间，以及用于查找的接近常数的时间。哈希函数本质上是获取一些信息并从中生成一个数字。从某种意义上说，它是一种功能，即相同的输入必须产生相同的输出。但是，不同的输入可能会产生相同的输出，从而导致所谓的碰撞。对于“完美的散列函数”，即没有冲突的函数，查找将保证是恒定时间。实际上，输入数字来自您存储在结构中的元素(比如它的值，它是原始类型)并将其映射到数据结构中的某个位置。因此，对于给定的键，该函数会将您带到存储元素的位置，而无需任何遍历或搜索(为简单起见，此处忽略冲突)，因此时间恒定。这些结构有不同的实现(开放寻址、链接等)，请参阅 hash table , hash function .我还推荐 The Algorithm Design Manual 的第 3.7 节由斯基纳。现在，关于大 O 的复杂性，你是对的，你有 O(n) + O(n) + O(重叠的大小)。由于重叠不能大于 m 和 n 中的较小者，因此整体复杂度可以表示为 O(kN)，其中 N 是 m 和 n 中最大的。很快)。同样，这是“最佳情况”，没有冲突，并且具有完美的散列。

另一方面，

set 和 multi_set 使用二叉树，因此插入和查找通常为 O(logN)。哈希结构与二叉树的实际性能取决于 N，因此最好尝试这两种方法并在实际运行场景中对它们进行分析。