可以设计一个比.NET字典更一致的性能数据结构吗？

Question

.NET Dictionary<TKey,TValue>的内部结构和流程是一个高度优化的设计，西蒙库珀在这个出色的博客帖子中进行了讨论。

MSDN声明Add(TKey,TValue)是O(1) --除非字典的元素计数是容量的，这就需要首先执行动态调整大小的操作，从而在这些连接处进行Add() O(n)。

随着字典的增长，调整操作的次数越来越少，因此可以说，在大n上平均，Add()接近O(1)。

库珀在这个图中证明了这一点，即n/2添加操作的总运行时间是n的函数。

但是，Add()的平均最差性能是O(n)。

我的问题是:是否有可能设计一个比.NET字典更一致的性能数据结构？

具体来说，我希望添加、删除、检索操作的平均最差性能为O(1)。

注意，性能的一致性(“大O”)是唯一相关的设计标准。内存利用率和绝对性能(包括集群和缓存性能的程度)不是相关的设计标准。

选择一个比预期需求大得多的初始容量是一种选择，但这是一个初始化步骤，我正在寻找一个数据结构设计。

Answer 1

你是否只是试着创建一本大到足够大的字典？

泛型O(1)基本上是一个数组。通过索引访问。或者分层数组(4字节键，数组指向指向数组的数组，以节省空间)。

不管怎么说-不，对不起。

很多高性能的东西使用预先分配的数组。