O(N) 算法比 O(N logN) 算法慢
O(N) algorithm slower than O(N logN) algorithm
在数字数组中，每个数字出现偶数次，只有一个数字出现奇数次。我们需要找到那个数字（之前讨论过这个问题on Stack Overflow）。
这是一个用 3 种不同方法解决问题的解决方案 - 两种方法是 O(N)（hash_set 和 hash_map），而一种是 O(NlogN)（排序）。然而，对任意大输入的分析显示排序速度更快，并且随着输入的增加（相比之下）变得越来越快。
实现或复杂性分析有什么问题，为什么 O(NlogN) 方法更快？
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
class ScopedTimer {
public:
ScopedTimer(const string& name)
: name_(name), start_time_(high_resolution_clock::now()) {}
~ScopedTimer() {
cout << name_ << " took "
<< std::chrono::duration_cast<milliseconds>(
high_resolution_clock::now() - start_time_).count()
<< " milliseconds" << endl;
}
private:
const string name_;
const high_resolution_clock::time_point start_time_;
};
int find_using_hash(const vector<int>& input_data) {
unordered_set<int> numbers(input_data.size());
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_hashmap(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_sort_and_count(const vector<int>& input_data) {
vector<int> local_copy(input_data);
std::sort(local_copy.begin(), local_copy.end());
int prev_value = local_copy.front();
int counter = 0;
for(const auto& value : local_copy) {
if(prev_value == value) {
++counter;
continue;
}
if(counter % 2 == 1) {
return prev_value;
}
prev_value = value;
counter = 1;
}
return counter == 1 ? prev_value : -1;
}
void execute_and_time(const string& method_name, std::function<int()> method) {
ScopedTimer timer(method_name);
cout << method_name << " returns " << method() << endl;
}
int main()
{
vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});
for(const auto& input_size : input_size_vec) {
// Prepare input data
std::vector<int> input_data;
const int magic_number = 123454321;
for(int i=0;i<input_size;++i) {
input_data.push_back(i);
input_data.push_back(i);
}
input_data.push_back(magic_number);
std::random_shuffle(input_data.begin(), input_data.end());
cout << "For input_size " << input_size << ":" << endl;
execute_and_time("hash-set:",std::bind(find_using_hash, input_data));
execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data));
execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data));
cout << "--------------------------" << endl;
}
return 0;
}
分析结果：
sh$ g++ -O3 -std=c++11 -o main *.cc
sh$ ./main
For input_size 262144:
hash-set: returns 123454321
hash-set: took 107 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 37 milliseconds
hash-map: returns 123454321
hash-map: took 109 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 173 milliseconds
hash-map: returns 123454321
hash-map: took 731 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 3250 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 745 milliseconds
hash-map: returns 123454321
hash-map: took 3631 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 14528 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 3238 milliseconds
hash-map: returns 123454321
hash-map: took 16483 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 350305 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 60396 milliseconds
hash-map: returns 123454321
hash-map: took 427841 milliseconds
--------------------------
加法
@Matt 建议的 xor 快速解决方案当然没有竞争力——在最坏的情况下不到 1 秒的示例：
int find_using_xor(const vector<int>& input_data) {
int output = 0;
for(const int& value : input_data) {
output = output^value;
}
return output;
}
For input_size 268435456:
xor: returns 123454321
xor: took 264 milliseconds
但问题仍然存在——尽管理论上算法复杂性具有优势，但为什么哈希与实践中的排序相比效率如此低？
让我们从查看排序解决方案的数字开始。在下面的table中，第一列是尺寸比例。它是通过计算给定测试的 NlogN 并除以第一个测试的 NlogN 来计算的。第二列是给定测试与第一次测试的时间比。
NlogN size ratio time ratio
4*20/18 = 4.4 173 / 37 = 4.7
16*22/18 = 19.6 745 / 37 = 20.1
64*24/18 = 85.3 3238 / 37 = 87.5
1024*28/18 = 1590 60396 / 37 = 1630
可以看到两个比值非常吻合，说明排序例程确实是O(NlogN).
那么为什么哈希例程没有按预期执行。很简单，从哈希 table 中提取一个项目是 O(1) 的想法纯属幻想。实际提取时间取决于散列函数的质量，以及散列中的 bin 数 table。实际提取时间范围从 O(1) 到 O(N)，其中最坏的情况发生在散列中的所有条目 table 最终进入同一个垃圾箱。所以使用散列 table，你应该期望你的性能介于 O(N) 和 O(N^2) 之间这似乎符合您的数据，如下所示
O(N) O(NlogN) O(N^2) time
4 4.4 16 6
16 20 256 30
64 85 4096 136
1024 1590 10^6 3274
请注意，时间比率处于范围的低端，表明哈希函数运行良好。
此分析与user3386199 in his 所做的分析基本相同。不管他的回答如何，我都会进行这种分析——但他确实先到了。
我 运行 我机器上的程序（HP Z420 运行 一个 Ubuntu 14.04 LTE 衍生产品），并为 1<<26 添加了输出，所以我有一个不同的一组数字，但比率看起来与原始 post 中数据的比率非常相似。我得到的原始时间是（文件on-vs-logn.raw.data）：
For input_size 262144:
hash-set: returns 123454321
hash-set: took 45 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
hash-map: returns 123454321
hash-map: took 61 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 372 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 154 milliseconds
hash-map: returns 123454321
hash-map: took 390 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 1921 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 680 milliseconds
hash-map: returns 123454321
hash-map: took 1834 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 8356 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2970 milliseconds
hash-map: returns 123454321
hash-map: took 9045 milliseconds
--------------------------
For input_size 67108864:
hash-set: returns 123454321
hash-set: took 37582 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 12842 milliseconds
hash-map: returns 123454321
hash-map: took 46480 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 172329 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 53856 milliseconds
hash-map: returns 123454321
hash-map: took 211191 milliseconds
--------------------------
real 11m32.852s
user 11m24.687s
sys 0m8.035s
我创建了一个脚本 awk.analysis.sh 来分析数据：
#!/bin/sh
awk '
BEGIN { printf("%9s %8s %8s %8s %8s %8s %8s %9s %9s %9s %9s\n",
"Size", "Sort Cnt", "R:Sort-C", "Hash Set", "R:Hash-S", "Hash Map",
"R:Hash-M", "O(N)", "O(NlogN)", "O(N^3/2)", "O(N^2)")
}
/input_size/ { if (old_size == 0) old_size = ; size = }
/hash-set: took/ { if (o_hash_set == 0) o_hash_set = ; t_hash_set = }
/sort-and-count: took/ { if (o_sort_cnt == 0) o_sort_cnt = ; t_sort_cnt = }
/hash-map: took/ { if (o_hash_map == 0) o_hash_map = ; t_hash_map = }
/^----/ {
o_n = size / old_size
o_nlogn = (size * log(size)) / (old_size * log(old_size))
o_n2 = (size * size) / (old_size * old_size)
o_n32 = (size * sqrt(size)) / (old_size * sqrt(old_size))
r_sort_cnt = t_sort_cnt / o_sort_cnt
r_hash_map = t_hash_map / o_hash_map
r_hash_set = t_hash_set / o_hash_set
printf("%9d %8d %8.2f %8d %8.2f %8d %8.2f %9.0f %9.2f %9.2f %9.0f\n",
size, t_sort_cnt, r_sort_cnt, t_hash_set, r_hash_set,
t_hash_map, r_hash_map, o_n, o_nlogn, o_n32, o_n2)
}' < on-vs-logn.raw.data
程序的输出很宽，但给出：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 34 1.00 45 1.00 61 1.00 1 1.00 1.00 1
1048576 154 4.53 372 8.27 390 6.39 4 4.44 8.00 16
4194304 680 20.00 1921 42.69 1834 30.07 16 19.56 64.00 256
16777216 2970 87.35 8356 185.69 9045 148.28 64 85.33 512.00 4096
67108864 12842 377.71 37582 835.16 46480 761.97 256 369.78 4096.00 65536
268435456 53856 1584.00 172329 3829.53 211191 3462.15 1024 1592.89 32768.00 1048576
很明显，在这个平台上，hash set和hash map算法不是O(N)，也没有O(N.logN)好，但是比O( N3/2) 更不用说 O(N2) 了。另一方面，排序算法确实非常接近 O(N.logN)。
您只能将其归因于散列集和散列映射代码中的理论缺陷，或者散列 table 的大小不足，因此他们使用的是次优散列 table 大小。值得研究存在哪些机制来预先确定哈希集和哈希映射的大小，以查看使用它是否会影响性能。 （另请参阅下面的额外信息。）
并且，仅作记录，这是原始数据分析脚本的输出：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 37 1.00 107 1.00 109 1.00 1 1.00 1.00 1
1048576 173 4.68 641 5.99 731 6.71 4 4.44 8.00 16
4194304 745 20.14 3250 30.37 3631 33.31 16 19.56 64.00 256
16777216 3238 87.51 14528 135.78 16483 151.22 64 85.33 512.00 4096
268435456 60396 1632.32 350305 3273.88 427841 3925.15 1024 1592.89 32768.00 1048576
进一步测试表明修改散列函数如下所示：
int find_using_hash(const vector<int>& input_data) {
unordered_set<int> numbers;
numbers.reserve(input_data.size());
和：
int find_using_hashmap(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
counter_map.reserve(input_data.size());
产生这样的分析：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 34 1.00 42 1.00 80 1.00 1 1.00 1.00 1
1048576 155 4.56 398 9.48 321 4.01 4 4.44 8.00 16
4194304 685 20.15 1936 46.10 1177 14.71 16 19.56 64.00 256
16777216 2996 88.12 8539 203.31 5985 74.81 64 85.33 512.00 4096
67108864 12564 369.53 37612 895.52 28808 360.10 256 369.78 4096.00 65536
268435456 53291 1567.38 172808 4114.48 124593 1557.41 1024 1592.89 32768.00 1048576
显然，为散列映射保留 space 是有益的。
散列集代码比较不同；它在大约一半的时间（总体）添加一个项目，'adds' 然后在另一半的时间删除一个项目。这比哈希映射代码必须做的工作更多，因此速度较慢。这也意味着保留的 space 比实际需要的要大，并且可能会导致保留的 space 性能下降。
这真的取决于 hash_map/hash_set 实施。通过将 libstdc++ 的 unordered_{map,set} 替换为 Google 的 dense_hash_{map,set}，它比 sort 快得多。 dense_hash_xxx 的缺点是它们要求有两个永远不会被使用的键值。有关详细信息，请参阅他们的文档。
要记住的另一件事是：hash_{map,set} 通常会占用大量动态内存 allocation/deallocation，因此最好使用更好的替代 libc 的默认值 malloc/free，例如Google 的 tcmalloc 或 Facebook 的 jemalloc.
hidden $ g++ -O3 -std=c++11 xx.cpp /usr/lib/libtcmalloc_minimal.so.4
hidden $ ./a.out
For input_size 262144:
unordered-set: returns 123454321
unordered-set: took 35 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 18 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
unordered-map: returns 123454321
unordered-map: took 36 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 13 milliseconds
--------------------------
For input_size 1048576:
unordered-set: returns 123454321
unordered-set: took 251 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 77 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 153 milliseconds
unordered-map: returns 123454321
unordered-map: took 220 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 60 milliseconds
--------------------------
For input_size 4194304:
unordered-set: returns 123454321
unordered-set: took 1453 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 357 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 596 milliseconds
unordered-map: returns 123454321
unordered-map: took 1461 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 296 milliseconds
--------------------------
For input_size 16777216:
unordered-set: returns 123454321
unordered-set: took 6664 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 1751 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2513 milliseconds
unordered-map: returns 123454321
unordered-map: took 7299 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 1364 milliseconds
--------------------------
tcmalloc: large alloc 1073741824 bytes == 0x5f392000 @
tcmalloc: large alloc 2147483648 bytes == 0x9f392000 @
tcmalloc: large alloc 4294967296 bytes == 0x11f392000 @
For input_size 268435456:
tcmalloc: large alloc 4586348544 bytes == 0x21fb92000 @
unordered-set: returns 123454321
unordered-set: took 136271 milliseconds
tcmalloc: large alloc 8589934592 bytes == 0x331974000 @
tcmalloc: large alloc 2147483648 bytes == 0x21fb92000 @
dense-hash-set: returns 123454321
dense-hash-set: took 34641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 47606 milliseconds
tcmalloc: large alloc 2443452416 bytes == 0x21fb92000 @
unordered-map: returns 123454321
unordered-map: took 176066 milliseconds
tcmalloc: large alloc 4294967296 bytes == 0x331974000 @
dense-hash-map: returns 123454321
dense-hash-map: took 26460 milliseconds
--------------------------
代码：
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <google/dense_hash_map>
#include <google/dense_hash_set>
using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using google::dense_hash_map;
using google::dense_hash_set;
class ScopedTimer {
public:
ScopedTimer(const string& name)
: name_(name), start_time_(high_resolution_clock::now()) {}
~ScopedTimer() {
cout << name_ << " took "
<< std::chrono::duration_cast<milliseconds>(
high_resolution_clock::now() - start_time_).count()
<< " milliseconds" << endl;
}
private:
const string name_;
const high_resolution_clock::time_point start_time_;
};
int find_using_unordered_set(const vector<int>& input_data) {
unordered_set<int> numbers(input_data.size());
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_unordered_map(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_dense_hash_set(const vector<int>& input_data) {
dense_hash_set<int> numbers(input_data.size());
numbers.set_deleted_key(-1);
numbers.set_empty_key(-2);
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_dense_hash_map(const vector<int>& input_data) {
dense_hash_map<int,int> counter_map;
counter_map.set_deleted_key(-1);
counter_map.set_empty_key(-2);
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_sort_and_count(const vector<int>& input_data) {
vector<int> local_copy(input_data);
std::sort(local_copy.begin(), local_copy.end());
int prev_value = local_copy.front();
int counter = 0;
for(const auto& value : local_copy) {
if(prev_value == value) {
++counter;
continue;
}
if(counter % 2 == 1) {
return prev_value;
}
prev_value = value;
counter = 1;
}
return counter == 1 ? prev_value : -1;
}
void execute_and_time(const string& method_name, std::function<int()> method) {
ScopedTimer timer(method_name);
cout << method_name << " returns " << method() << endl;
}
int main()
{
vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});
for(const auto& input_size : input_size_vec) {
// Prepare input data
std::vector<int> input_data;
const int magic_number = 123454321;
for(int i=0;i<input_size;++i) {
input_data.push_back(i);
input_data.push_back(i);
}
input_data.push_back(magic_number);
std::random_shuffle(input_data.begin(), input_data.end());
cout << "For input_size " << input_size << ":" << endl;
execute_and_time("unordered-set:",std::bind(find_using_unordered_set, std::cref(input_data)));
execute_and_time("dense-hash-set:",std::bind(find_using_dense_hash_set, std::cref(input_data)));
execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, std::cref(input_data)));
execute_and_time("unordered-map:",std::bind(find_using_unordered_map, std::cref(input_data)));
execute_and_time("dense-hash-map:",std::bind(find_using_dense_hash_map, std::cref(input_data)));
cout << "--------------------------" << endl;
}
return 0;
}
我 运行 通过具有不同输入大小的 valgrind 的程序，我得到了这些循环计数结果：
with 1<<16 values:
find_using_hash: 27 560 872
find_using_sort: 17 089 994
sort/hash: 62.0%
with 1<<17 values:
find_using_hash: 55 105 370
find_using_sort: 35 325 606
sort/hash: 64.1%
with 1<<18 values:
find_using_hash: 110 235 327
find_using_sort: 75 695 062
sort/hash: 68.6%
with 1<<19 values:
find_using_hash: 220 248 209
find_using_sort: 157 934 801
sort/hash: 71.7%
with 1<<20 values:
find_using_hash: 440 551 113
find_using_sort: 326 027 778
sort/hash: 74.0%
with 1<<21 values:
find_using_hash: 881 086 601
find_using_sort: 680 868 836
sort/hash: 77.2%
with 1<<22 values:
find_using_hash: 1 762 482 400
find_using_sort: 1 420 801 591
sort/hash: 80.6%
with 1<<23 values:
find_using_hash: 3 525 860 455
find_using_sort: 2 956 962 786
sort/hash: 83.8%
这表明排序时间正在慢慢超过哈希时间，至少在理论上是这样。使用我的特定 compiler/library (gcc 4.8.2/libsddc++) 和优化 (-O2)，排序和散列方法在大约 2^28 个值时速度相同，这是您的极限试。我怀疑在使用那么多内存时，其他系统因素也在发挥作用，这使得很难在实际挂起时间中进行评估。
O(N) 似乎比 O(N logN) 慢这一事实让我抓狂，所以我决定深入研究这个问题。
我在 Windows 中使用 Visual Studio 进行了此分析，但我敢打赌在 Linux 中使用 g++ 结果会非常相似。
首先，我使用 Very Sleepy 找到了 find_using_hash() 中 for 循环中执行最多的代码片段。这是我看到的：
如您所见，排名靠前的条目都与列表相关（RtlAllocateHeap 是从列表代码中调用的）。显然，问题是对于 unordered_set 中的每次插入，并且由于桶是作为列表实现的，因此会为节点分配一个节点，这 sky-rockets 算法的持续时间，而不是排序不做任何分配。
为了确定这是问题所在，我写了一个非常简单的散列实现 table，没有分配，结果更合理：
就是这样，log N 乘以 N 的系数在你最大的例子中（即 1<<28）是 28，仍然小于 "constant" 的数量分配所需的工作量。
这里已经有很多很好的答案，但这是一种特殊的问题，自然会产生许多有效答案。
我写信是为了从数学角度提供答案（如果没有 LaTeX 很难做到），因为重要的是要纠正未解决的误解，即用哈希解决给定问题代表的问题是 "theoretically" O(n)，但不知何故 "practically" 比 O(n) 差。这样的事情在数学上是不可能的！
For those wishing to pursue the topic in more depth, I recommend this
book which I saved for and bought as a very poor high school
student, and which stoked my interest in applied mathematics for many
years to come, essentially changing the outcome of my life:
http://www.amazon.com/Analysis-Algorithms-Monographs-Computer-Science/dp/0387976876
要理解为什么问题不是 "theoretically" O(n)，有必要注意潜在的假设也是错误的：散列是 "theoretically" 一个 O(1) 数据结构.
事实恰恰相反。纯粹形式的哈希只是 "practically" 一个 O(1) 数据结构，但理论上仍然是一个 O(n) 数据结构。 （注：在混合形式下，它们可以达到理论上的O(log n)性能。）
因此，在最好的情况下，解决方案仍然是一个 O(n log n) 问题，因为 n 接近无穷大。
You may start to respond, but everyone knows that hashes are O(1)!
那么现在让我解释一下这个说法 是 正确的，但在实践而非理论意义上，。
对于任何应用（不管n，只要提前知道n——他们在数学证明中称之为"fixed"而不是"arbitrary"） ，您可以设计哈希 table 以匹配应用程序，并在该环境的约束下获得 O(1) 性能。每个纯哈希结构都旨在在数据集大小的 先验 范围内表现良好，并假设密钥相对于哈希函数是独立的。
但是当你让 n 接近无穷大时，按照 Big-O 符号定义的要求，桶开始填充（这必须根据鸽巢原理发生），并且任何纯哈希结构分解为 O(n) 算法（这里的 Big-O 符号忽略了取决于有多少桶的常数因子）。
Whoa! There's a lot in that sentence.
所以在这一点上，比起方程式，适当的类比会更有帮助：
通过想象一个包含 26 个抽屉的文件柜，每个抽屉对应字母表中的一个字母，可以获得对散列 tables 的非常准确的数学理解。每个文件都存储在与文件名中的第一个字母对应的抽屉中。
"hash function"是一个O(1)操作，看第一个
字母.
存储是一项O(1)操作：将文件放入抽屉
为了那封信。
和只要每个抽屉里的文件不超过一个,
检索是一个 O(1) 操作：打开那个字母的抽屉。
在这些设计约束下，此哈希结构是 O(1)。
现在假设您超出了此 "filing cabinet" 散列结构的设计限制，并且已经存储了数百个文件。存储现在根据需要在每个抽屉中找到一个空的 space 执行尽可能多的操作，并且检索需要与每个抽屉中的项目数量一样多的操作。
与将所有文件扔到一个巨大的堆中相比，总体平均性能大约提高了 1/26 倍的时间。但请记住，在数学上，不能说 O(n/26)，因为根据定义 O(n) 表示法不考虑影响性能的常数因素，而只考虑作为 n 函数的算法复杂度。所以当超出设计约束时，数据结构为O(n).
在数字数组中，每个数字出现偶数次，只有一个数字出现奇数次。我们需要找到那个数字（之前讨论过这个问题on Stack Overflow）。
这是一个用 3 种不同方法解决问题的解决方案 - 两种方法是 O(N)（hash_set 和 hash_map），而一种是 O(NlogN)（排序）。然而，对任意大输入的分析显示排序速度更快，并且随着输入的增加（相比之下）变得越来越快。
实现或复杂性分析有什么问题，为什么 O(NlogN) 方法更快？
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
class ScopedTimer {
public:
ScopedTimer(const string& name)
: name_(name), start_time_(high_resolution_clock::now()) {}
~ScopedTimer() {
cout << name_ << " took "
<< std::chrono::duration_cast<milliseconds>(
high_resolution_clock::now() - start_time_).count()
<< " milliseconds" << endl;
}
private:
const string name_;
const high_resolution_clock::time_point start_time_;
};
int find_using_hash(const vector<int>& input_data) {
unordered_set<int> numbers(input_data.size());
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_hashmap(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_sort_and_count(const vector<int>& input_data) {
vector<int> local_copy(input_data);
std::sort(local_copy.begin(), local_copy.end());
int prev_value = local_copy.front();
int counter = 0;
for(const auto& value : local_copy) {
if(prev_value == value) {
++counter;
continue;
}
if(counter % 2 == 1) {
return prev_value;
}
prev_value = value;
counter = 1;
}
return counter == 1 ? prev_value : -1;
}
void execute_and_time(const string& method_name, std::function<int()> method) {
ScopedTimer timer(method_name);
cout << method_name << " returns " << method() << endl;
}
int main()
{
vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});
for(const auto& input_size : input_size_vec) {
// Prepare input data
std::vector<int> input_data;
const int magic_number = 123454321;
for(int i=0;i<input_size;++i) {
input_data.push_back(i);
input_data.push_back(i);
}
input_data.push_back(magic_number);
std::random_shuffle(input_data.begin(), input_data.end());
cout << "For input_size " << input_size << ":" << endl;
execute_and_time("hash-set:",std::bind(find_using_hash, input_data));
execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data));
execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data));
cout << "--------------------------" << endl;
}
return 0;
}
分析结果：
sh$ g++ -O3 -std=c++11 -o main *.cc
sh$ ./main
For input_size 262144:
hash-set: returns 123454321
hash-set: took 107 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 37 milliseconds
hash-map: returns 123454321
hash-map: took 109 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 173 milliseconds
hash-map: returns 123454321
hash-map: took 731 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 3250 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 745 milliseconds
hash-map: returns 123454321
hash-map: took 3631 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 14528 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 3238 milliseconds
hash-map: returns 123454321
hash-map: took 16483 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 350305 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 60396 milliseconds
hash-map: returns 123454321
hash-map: took 427841 milliseconds
--------------------------
加法
@Matt 建议的 xor 快速解决方案当然没有竞争力——在最坏的情况下不到 1 秒的示例：
int find_using_xor(const vector<int>& input_data) {
int output = 0;
for(const int& value : input_data) {
output = output^value;
}
return output;
}
For input_size 268435456:
xor: returns 123454321
xor: took 264 milliseconds
但问题仍然存在——尽管理论上算法复杂性具有优势，但为什么哈希与实践中的排序相比效率如此低？
让我们从查看排序解决方案的数字开始。在下面的table中，第一列是尺寸比例。它是通过计算给定测试的 NlogN 并除以第一个测试的 NlogN 来计算的。第二列是给定测试与第一次测试的时间比。
NlogN size ratio time ratio
4*20/18 = 4.4 173 / 37 = 4.7
16*22/18 = 19.6 745 / 37 = 20.1
64*24/18 = 85.3 3238 / 37 = 87.5
1024*28/18 = 1590 60396 / 37 = 1630
可以看到两个比值非常吻合，说明排序例程确实是O(NlogN).
那么为什么哈希例程没有按预期执行。很简单，从哈希 table 中提取一个项目是 O(1) 的想法纯属幻想。实际提取时间取决于散列函数的质量，以及散列中的 bin 数 table。实际提取时间范围从 O(1) 到 O(N)，其中最坏的情况发生在散列中的所有条目 table 最终进入同一个垃圾箱。所以使用散列 table，你应该期望你的性能介于 O(N) 和 O(N^2) 之间这似乎符合您的数据，如下所示
O(N) O(NlogN) O(N^2) time
4 4.4 16 6
16 20 256 30
64 85 4096 136
1024 1590 10^6 3274
请注意，时间比率处于范围的低端，表明哈希函数运行良好。
此分析与user3386199 in his
我 运行 我机器上的程序（HP Z420 运行 一个 Ubuntu 14.04 LTE 衍生产品），并为 1<<26 添加了输出，所以我有一个不同的一组数字，但比率看起来与原始 post 中数据的比率非常相似。我得到的原始时间是（文件on-vs-logn.raw.data）：
For input_size 262144:
hash-set: returns 123454321
hash-set: took 45 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
hash-map: returns 123454321
hash-map: took 61 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 372 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 154 milliseconds
hash-map: returns 123454321
hash-map: took 390 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 1921 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 680 milliseconds
hash-map: returns 123454321
hash-map: took 1834 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 8356 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2970 milliseconds
hash-map: returns 123454321
hash-map: took 9045 milliseconds
--------------------------
For input_size 67108864:
hash-set: returns 123454321
hash-set: took 37582 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 12842 milliseconds
hash-map: returns 123454321
hash-map: took 46480 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 172329 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 53856 milliseconds
hash-map: returns 123454321
hash-map: took 211191 milliseconds
--------------------------
real 11m32.852s
user 11m24.687s
sys 0m8.035s
我创建了一个脚本 awk.analysis.sh 来分析数据：
#!/bin/sh
awk '
BEGIN { printf("%9s %8s %8s %8s %8s %8s %8s %9s %9s %9s %9s\n",
"Size", "Sort Cnt", "R:Sort-C", "Hash Set", "R:Hash-S", "Hash Map",
"R:Hash-M", "O(N)", "O(NlogN)", "O(N^3/2)", "O(N^2)")
}
/input_size/ { if (old_size == 0) old_size = ; size = }
/hash-set: took/ { if (o_hash_set == 0) o_hash_set = ; t_hash_set = }
/sort-and-count: took/ { if (o_sort_cnt == 0) o_sort_cnt = ; t_sort_cnt = }
/hash-map: took/ { if (o_hash_map == 0) o_hash_map = ; t_hash_map = }
/^----/ {
o_n = size / old_size
o_nlogn = (size * log(size)) / (old_size * log(old_size))
o_n2 = (size * size) / (old_size * old_size)
o_n32 = (size * sqrt(size)) / (old_size * sqrt(old_size))
r_sort_cnt = t_sort_cnt / o_sort_cnt
r_hash_map = t_hash_map / o_hash_map
r_hash_set = t_hash_set / o_hash_set
printf("%9d %8d %8.2f %8d %8.2f %8d %8.2f %9.0f %9.2f %9.2f %9.0f\n",
size, t_sort_cnt, r_sort_cnt, t_hash_set, r_hash_set,
t_hash_map, r_hash_map, o_n, o_nlogn, o_n32, o_n2)
}' < on-vs-logn.raw.data
程序的输出很宽，但给出：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 34 1.00 45 1.00 61 1.00 1 1.00 1.00 1
1048576 154 4.53 372 8.27 390 6.39 4 4.44 8.00 16
4194304 680 20.00 1921 42.69 1834 30.07 16 19.56 64.00 256
16777216 2970 87.35 8356 185.69 9045 148.28 64 85.33 512.00 4096
67108864 12842 377.71 37582 835.16 46480 761.97 256 369.78 4096.00 65536
268435456 53856 1584.00 172329 3829.53 211191 3462.15 1024 1592.89 32768.00 1048576
很明显，在这个平台上，hash set和hash map算法不是O(N)，也没有O(N.logN)好，但是比O( N3/2) 更不用说 O(N2) 了。另一方面，排序算法确实非常接近 O(N.logN)。
您只能将其归因于散列集和散列映射代码中的理论缺陷，或者散列 table 的大小不足，因此他们使用的是次优散列 table 大小。值得研究存在哪些机制来预先确定哈希集和哈希映射的大小，以查看使用它是否会影响性能。 （另请参阅下面的额外信息。）
并且，仅作记录，这是原始数据分析脚本的输出：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 37 1.00 107 1.00 109 1.00 1 1.00 1.00 1
1048576 173 4.68 641 5.99 731 6.71 4 4.44 8.00 16
4194304 745 20.14 3250 30.37 3631 33.31 16 19.56 64.00 256
16777216 3238 87.51 14528 135.78 16483 151.22 64 85.33 512.00 4096
268435456 60396 1632.32 350305 3273.88 427841 3925.15 1024 1592.89 32768.00 1048576
进一步测试表明修改散列函数如下所示：
int find_using_hash(const vector<int>& input_data) {
unordered_set<int> numbers;
numbers.reserve(input_data.size());
和：
int find_using_hashmap(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
counter_map.reserve(input_data.size());
产生这样的分析：
Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2)
262144 34 1.00 42 1.00 80 1.00 1 1.00 1.00 1
1048576 155 4.56 398 9.48 321 4.01 4 4.44 8.00 16
4194304 685 20.15 1936 46.10 1177 14.71 16 19.56 64.00 256
16777216 2996 88.12 8539 203.31 5985 74.81 64 85.33 512.00 4096
67108864 12564 369.53 37612 895.52 28808 360.10 256 369.78 4096.00 65536
268435456 53291 1567.38 172808 4114.48 124593 1557.41 1024 1592.89 32768.00 1048576
显然，为散列映射保留 space 是有益的。
散列集代码比较不同；它在大约一半的时间（总体）添加一个项目，'adds' 然后在另一半的时间删除一个项目。这比哈希映射代码必须做的工作更多，因此速度较慢。这也意味着保留的 space 比实际需要的要大，并且可能会导致保留的 space 性能下降。
这真的取决于 hash_map/hash_set 实施。通过将 libstdc++ 的 unordered_{map,set} 替换为 Google 的 dense_hash_{map,set}，它比 sort 快得多。 dense_hash_xxx 的缺点是它们要求有两个永远不会被使用的键值。有关详细信息，请参阅他们的文档。
要记住的另一件事是：hash_{map,set} 通常会占用大量动态内存 allocation/deallocation，因此最好使用更好的替代 libc 的默认值 malloc/free，例如Google 的 tcmalloc 或 Facebook 的 jemalloc.
hidden $ g++ -O3 -std=c++11 xx.cpp /usr/lib/libtcmalloc_minimal.so.4
hidden $ ./a.out
For input_size 262144:
unordered-set: returns 123454321
unordered-set: took 35 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 18 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
unordered-map: returns 123454321
unordered-map: took 36 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 13 milliseconds
--------------------------
For input_size 1048576:
unordered-set: returns 123454321
unordered-set: took 251 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 77 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 153 milliseconds
unordered-map: returns 123454321
unordered-map: took 220 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 60 milliseconds
--------------------------
For input_size 4194304:
unordered-set: returns 123454321
unordered-set: took 1453 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 357 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 596 milliseconds
unordered-map: returns 123454321
unordered-map: took 1461 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 296 milliseconds
--------------------------
For input_size 16777216:
unordered-set: returns 123454321
unordered-set: took 6664 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 1751 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2513 milliseconds
unordered-map: returns 123454321
unordered-map: took 7299 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 1364 milliseconds
--------------------------
tcmalloc: large alloc 1073741824 bytes == 0x5f392000 @
tcmalloc: large alloc 2147483648 bytes == 0x9f392000 @
tcmalloc: large alloc 4294967296 bytes == 0x11f392000 @
For input_size 268435456:
tcmalloc: large alloc 4586348544 bytes == 0x21fb92000 @
unordered-set: returns 123454321
unordered-set: took 136271 milliseconds
tcmalloc: large alloc 8589934592 bytes == 0x331974000 @
tcmalloc: large alloc 2147483648 bytes == 0x21fb92000 @
dense-hash-set: returns 123454321
dense-hash-set: took 34641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 47606 milliseconds
tcmalloc: large alloc 2443452416 bytes == 0x21fb92000 @
unordered-map: returns 123454321
unordered-map: took 176066 milliseconds
tcmalloc: large alloc 4294967296 bytes == 0x331974000 @
dense-hash-map: returns 123454321
dense-hash-map: took 26460 milliseconds
--------------------------
代码：
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <google/dense_hash_map>
#include <google/dense_hash_set>
using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using google::dense_hash_map;
using google::dense_hash_set;
class ScopedTimer {
public:
ScopedTimer(const string& name)
: name_(name), start_time_(high_resolution_clock::now()) {}
~ScopedTimer() {
cout << name_ << " took "
<< std::chrono::duration_cast<milliseconds>(
high_resolution_clock::now() - start_time_).count()
<< " milliseconds" << endl;
}
private:
const string name_;
const high_resolution_clock::time_point start_time_;
};
int find_using_unordered_set(const vector<int>& input_data) {
unordered_set<int> numbers(input_data.size());
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_unordered_map(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_dense_hash_set(const vector<int>& input_data) {
dense_hash_set<int> numbers(input_data.size());
numbers.set_deleted_key(-1);
numbers.set_empty_key(-2);
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_dense_hash_map(const vector<int>& input_data) {
dense_hash_map<int,int> counter_map;
counter_map.set_deleted_key(-1);
counter_map.set_empty_key(-2);
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_sort_and_count(const vector<int>& input_data) {
vector<int> local_copy(input_data);
std::sort(local_copy.begin(), local_copy.end());
int prev_value = local_copy.front();
int counter = 0;
for(const auto& value : local_copy) {
if(prev_value == value) {
++counter;
continue;
}
if(counter % 2 == 1) {
return prev_value;
}
prev_value = value;
counter = 1;
}
return counter == 1 ? prev_value : -1;
}
void execute_and_time(const string& method_name, std::function<int()> method) {
ScopedTimer timer(method_name);
cout << method_name << " returns " << method() << endl;
}
int main()
{
vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});
for(const auto& input_size : input_size_vec) {
// Prepare input data
std::vector<int> input_data;
const int magic_number = 123454321;
for(int i=0;i<input_size;++i) {
input_data.push_back(i);
input_data.push_back(i);
}
input_data.push_back(magic_number);
std::random_shuffle(input_data.begin(), input_data.end());
cout << "For input_size " << input_size << ":" << endl;
execute_and_time("unordered-set:",std::bind(find_using_unordered_set, std::cref(input_data)));
execute_and_time("dense-hash-set:",std::bind(find_using_dense_hash_set, std::cref(input_data)));
execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, std::cref(input_data)));
execute_and_time("unordered-map:",std::bind(find_using_unordered_map, std::cref(input_data)));
execute_and_time("dense-hash-map:",std::bind(find_using_dense_hash_map, std::cref(input_data)));
cout << "--------------------------" << endl;
}
return 0;
}
我 运行 通过具有不同输入大小的 valgrind 的程序，我得到了这些循环计数结果：
with 1<<16 values:
find_using_hash: 27 560 872
find_using_sort: 17 089 994
sort/hash: 62.0%
with 1<<17 values:
find_using_hash: 55 105 370
find_using_sort: 35 325 606
sort/hash: 64.1%
with 1<<18 values:
find_using_hash: 110 235 327
find_using_sort: 75 695 062
sort/hash: 68.6%
with 1<<19 values:
find_using_hash: 220 248 209
find_using_sort: 157 934 801
sort/hash: 71.7%
with 1<<20 values:
find_using_hash: 440 551 113
find_using_sort: 326 027 778
sort/hash: 74.0%
with 1<<21 values:
find_using_hash: 881 086 601
find_using_sort: 680 868 836
sort/hash: 77.2%
with 1<<22 values:
find_using_hash: 1 762 482 400
find_using_sort: 1 420 801 591
sort/hash: 80.6%
with 1<<23 values:
find_using_hash: 3 525 860 455
find_using_sort: 2 956 962 786
sort/hash: 83.8%
这表明排序时间正在慢慢超过哈希时间，至少在理论上是这样。使用我的特定 compiler/library (gcc 4.8.2/libsddc++) 和优化 (-O2)，排序和散列方法在大约 2^28 个值时速度相同，这是您的极限试。我怀疑在使用那么多内存时，其他系统因素也在发挥作用，这使得很难在实际挂起时间中进行评估。
O(N) 似乎比 O(N logN) 慢这一事实让我抓狂，所以我决定深入研究这个问题。
我在 Windows 中使用 Visual Studio 进行了此分析，但我敢打赌在 Linux 中使用 g++ 结果会非常相似。
首先，我使用 Very Sleepy 找到了 find_using_hash() 中 for 循环中执行最多的代码片段。这是我看到的：
如您所见，排名靠前的条目都与列表相关（RtlAllocateHeap 是从列表代码中调用的）。显然，问题是对于 unordered_set 中的每次插入，并且由于桶是作为列表实现的，因此会为节点分配一个节点，这 sky-rockets 算法的持续时间，而不是排序不做任何分配。
为了确定这是问题所在，我写了一个非常简单的散列实现 table，没有分配，结果更合理：
就是这样，log N 乘以 N 的系数在你最大的例子中（即 1<<28）是 28，仍然小于 "constant" 的数量分配所需的工作量。
这里已经有很多很好的答案，但这是一种特殊的问题，自然会产生许多有效答案。
我写信是为了从数学角度提供答案（如果没有 LaTeX 很难做到），因为重要的是要纠正未解决的误解，即用哈希解决给定问题代表的问题是 "theoretically" O(n)，但不知何故 "practically" 比 O(n) 差。这样的事情在数学上是不可能的！
For those wishing to pursue the topic in more depth, I recommend this book which I saved for and bought as a very poor high school student, and which stoked my interest in applied mathematics for many years to come, essentially changing the outcome of my life: http://www.amazon.com/Analysis-Algorithms-Monographs-Computer-Science/dp/0387976876
要理解为什么问题不是 "theoretically" O(n)，有必要注意潜在的假设也是错误的：散列是 "theoretically" 一个 O(1) 数据结构.
事实恰恰相反。纯粹形式的哈希只是 "practically" 一个 O(1) 数据结构，但理论上仍然是一个 O(n) 数据结构。 （注：在混合形式下，它们可以达到理论上的O(log n)性能。）
因此，在最好的情况下，解决方案仍然是一个 O(n log n) 问题，因为 n 接近无穷大。
You may start to respond, but everyone knows that hashes are O(1)!
那么现在让我解释一下这个说法 是 正确的，但在实践而非理论意义上，。
对于任何应用（不管n，只要提前知道n——他们在数学证明中称之为"fixed"而不是"arbitrary"） ，您可以设计哈希 table 以匹配应用程序，并在该环境的约束下获得 O(1) 性能。每个纯哈希结构都旨在在数据集大小的 先验 范围内表现良好，并假设密钥相对于哈希函数是独立的。
但是当你让 n 接近无穷大时，按照 Big-O 符号定义的要求，桶开始填充（这必须根据鸽巢原理发生），并且任何纯哈希结构分解为 O(n) 算法（这里的 Big-O 符号忽略了取决于有多少桶的常数因子）。
Whoa! There's a lot in that sentence.
所以在这一点上，比起方程式，适当的类比会更有帮助：
通过想象一个包含 26 个抽屉的文件柜，每个抽屉对应字母表中的一个字母，可以获得对散列 tables 的非常准确的数学理解。每个文件都存储在与文件名中的第一个字母对应的抽屉中。
"hash function"是一个
O(1)操作，看第一个 字母.存储是一项
O(1)操作：将文件放入抽屉 为了那封信。和只要每个抽屉里的文件不超过一个, 检索是一个
O(1)操作：打开那个字母的抽屉。
在这些设计约束下，此哈希结构是 O(1)。
现在假设您超出了此 "filing cabinet" 散列结构的设计限制，并且已经存储了数百个文件。存储现在根据需要在每个抽屉中找到一个空的 space 执行尽可能多的操作，并且检索需要与每个抽屉中的项目数量一样多的操作。
与将所有文件扔到一个巨大的堆中相比，总体平均性能大约提高了 1/26 倍的时间。但请记住，在数学上，不能说 O(n/26)，因为根据定义 O(n) 表示法不考虑影响性能的常数因素，而只考虑作为 n 函数的算法复杂度。所以当超出设计约束时，数据结构为O(n).