正如Simon Cooper在这篇优秀的博客文章中所讨论的那样，.NET Dictionary<TKey,TValue>的内部结构和过程是一个高度优化的设计。
MSDN文档指出Add(TKey,TValue)是O（1）——除非Dictionary的元素计数已满，必须首先执行动态调整大小操作，从而在这些时刻使Add（）为O（n）。
随着Dictionary的增长，调整大小的操作越来越不频繁，因此可以说，在大n上求平均值，Add（）接近O（1）。
库珀在这张n/2加法运算的总运行时间图中证明了这一点。
然而，Add（）的平均最坏情况性能为O（n）。
我的问题是：是否有可能设计出比.NET Dictionary性能更一致的数据结构？
具体来说，我希望添加、删除、检索操作的平均最坏情况性能都为O（1）。
请注意，性能一致性（"大O"）是唯一相关的设计标准。内存利用率和绝对性能（包括集群程度和缓存性能）不是相关的设计标准。
选择比预期需求大得多的初始容量是一种选择，但这是一个初始化步骤，我正在寻找数据结构设计。
您是否只是尝试创建一个足够大的字典？
泛型O（1）基本上是一个数组。通过索引访问。或者层次数组（4字节键，数组指向aray，数组指向数组，非常接近数组，以节省空间）。
不管怎样——不，对不起。
很多高性能的东西都使用预分配的数组。