c# - 字典查找与数组查找；数组分配与字典分配

Question

谁能告诉我字典结构查找方法的幕后是什么.我的意思是它是如何实现的？给定一个键，我们在字典中找到值。

1)我们知道and数组查找是O(1)的操作。那么字典呢？

2)如果我存储的键值对都是整数，如果有大量这样的数据和空间，我会担心哪一个更可取？数组还是字典？例如，我可以分配一个固定大小的数组。但是键值对可能不会占据整个数组。它的大小可能是数组的一半。但是数组分配应该是最大的，因为我不知道某个键是否会出现。让我澄清一下，让我们有键值对 (10,1)、(20,2)、(30,3)。因此，如果我使用数组，那么我必须将其大小声明为 [30][2]，尽管它只占用 3 个条目。所以，在这种情况下，字典会更好。不是说 30 可以是百万。那么其他条目将占用数组中的内存吗？

Answer 1

字典通常以两种方式实现， HashMap 或二叉树。

1:如果字典是二叉树，那么查找时间就是二分查找，因此是O(log n)。

如果字典是一个hash map，那么查找时间就是O(1)。 (对于具有相同散列的键，可能会增加到 O(m))

2:你是对的，在这种稀疏数据集的情况下，字典可以更好地利用空间。字典搜索的额外时间成本将相对较低。

使用布隆过滤器之类的东西可以进一步改进字典搜索(如果平均情况是散列映射中不存在的对象)。