谁能告诉我字典结构的后台查找方法是什么
。我是说它是如何实现的?给定一个键,我们可以在字典中找到该值。
1)我们知道,数组查找是O(1)运算。那字典呢?
2)如果我存储的都是两个都是整数的键值对,那么如果有大量这样的数据,那么我担心的是空间,那会更好吗?数组还是字典?
例如,我可以分配一个固定大小的数组。但是键值对可能不会占据整个数组。它的大小可能是数组的一半。但是数组分配应为最大大小,因为我不知道某个键是否会出现。
让我澄清一下,让我们有键值对(10,1),(20,2),(30,3)。因此,如果我使用数组,那么尽管它仅占用3个条目,但我必须将其大小声明为[30] [2]。因此,在这种情况下,字典会更好。不是30可以是百万。那么其他条目将占用数组中的内存,对吗?
最佳答案
字典通常以两种方式实现:哈希映射或二叉树。
1:如果字典是二叉树,则搜索时间是二叉搜索,因此为O(log n)。
如果字典是哈希图,则搜索时间为O(1)。 (对于具有相同散列的键,可能会增加到O(m))
2:是的,在这种稀疏数据集的情况下,字典将更好地利用空间。词典搜索的额外时间成本将相对较低。
可以使用Bloom Bloom过滤器(如果平均情况是哈希图中不存在该对象)进一步改善字典的搜索。