C++ unordered_map桶增长规律
无序容器unordered_map存储为一组桶,各元素通过hash函数映射到各个桶中。心血来潮,来看一下桶的增长规律。
1 #include <iostream> 2 #include <string> 3 #include <unordered_map> 4 using namespace std; 5 6 int main() 7 { 8 unordered_map<int , string> ump; 9 for(int i=0; i<190; i++) 10 { 11 ump.insert(pair<int, string>(i, "amy")); 12 cout << "插入 " << i << " - "; 13 cout << "桶数量" << ump.bucket_count() << " - "; 14 cout << "最大桶数量" << ump.bucket_count() << endl; 15 } 16 return 0; 17 }
我们从上面部分结果来看,每当桶不够用时,桶数会以大致 bucket[n] = 2*bucket[n-1] + 奇数 (1, 3, 5, 9 ...)来增长。与vector 成倍增长倒是不同。
3 = 2 * 0 + 3
7 = 2 * 3 + 1
17 = 2 * 7 + 3
37 = 2 * 17 + 3
79 = 2 * 37 + 5
167 = 2 * 79 + 9
337 = 2 * 167 + 5