字典查找与数组查找；数组分配与字典分配
本文关键字：分配 数组 字典 查找 | 更新日期: 2023-09-27 18:28:41
你们中的任何人能告诉我字典结构查找方法的幕后是什么吗。我是说它是如何实现的？给定一个关键字，我们就可以在字典中找到它的值。
1） 我们知道，数组查找是O（1）运算。那么字典呢？
2） 如果我存储的键值对都是整数，如果有大量这样的数据和空间，我担心哪一个更可取？数组还是字典？例如，我可以分配一个固定大小的数组。但是键值对可能不会占据整个数组。它的大小可能是数组的一半。但数组分配应该是最大大小的，因为我不知道某个键是否会出现。让我澄清一下，让我们有键值对（10，1），（20，2），（30，3）。所以，如果我使用数组，那么我必须将其大小声明为[30][2]，尽管它只占用3个条目。所以，在这种情况下，字典会更好。并不是说30就可以是百万。所以其他条目会占用数组中的内存，对吗？
字典通常通过两种方式实现，一种是散列映射，另一种是二进制树。
1：如果字典是二叉树，那么搜索时间是二叉搜索，因此是O（logn）。
如果字典是一个散列映射，那么搜索时间是O（1）。（对于具有相同哈希的密钥，可能会增加到O（m））
2：你是对的，在这种稀疏数据集的情况下，字典会更好地利用空间。词典搜索的额外时间成本将相对较低。
使用bloom过滤器之类的东西可以进一步改进字典搜索（如果平均情况是哈希图中不存在的对象）。
术语dictionary非常通用，可以指代任何类型的数据结构。你也没有说这是一本有序的字典还是无序的。有各种以各种方式平衡的二进制搜索树，n元树、哈希表、skiplist等。
就阵列而言，平直阵列在人口稀少时确实会浪费空间。但是，您可以实现多级数组。前几个级别是目录，只有叶级别有小数组。
虚拟内存页表通常是这样实现的。
因此，像（十六进制）[0x23456]这样的数组索引可能会通过位掩码操作分解为[0x12][0x34][0x56]。选择顶部目录，它是指向中间目录的指针数组，中间目录有指向小表的指针数组。（当然，在现实中，代码必须遍历各个级别，并注意丢失的目录和表，而不是直接索引！这就是关键：不要实例化整个树。）
不久前，我以这种方式在正则表达式引擎中实现了Unicode字符集，针对不同的情况使用了几种不同深度的结构。
当然，这与您的常规new int[foo]C++数组无关！但是当然可以隐藏在一个看起来像数组的类后面。