这是哪个数据结构?

数据结构的名称(如果存在的话)是什么?

  • 你可以插入一个元素,并给你一个键。
  • 您可以通过其键获取元素。

内存分配器

您分配(插入)一个元素,并给定一个键(指针,引用等),您可以通过指针引用检索元素(访问它)。

这是(非常接近)一个符号表,在Lisp的意义上(注意,“符号表”这个短语也可以指定相关但不同的数据结构)。 符号表是从称为符号的键到称为绑定(或槽或其他术语)的值的关联。

注册新密钥的操作称为gensym 。 Lisp符号总是有一个唯一的名字,这是一个string; gensym返回一个没有被任何符号使用的名称。 Lisp还支持按名称查找符号: intern返回给定名称的符号,如果不存在则创build符号; 一些实现提供intern-soft以避免在没有这个名称的情况下创build符号。 给定一个符号,您可以使用symbol-value检索关联symbol-value

如果你不了解Lisp,把符号看作variables; gensym创build一个新的variables, symbol-value返回由引用指定的variables的值。 编写macros(元编程)时,这些操作特别有用,Lisp支持的非常好。 现代Lisp实现具有“不间断”的符号,即不在任何表中的符号,这使得事情变得更加清晰。 这与您所考虑的数据结构无关(未插入符号将是不在您的数据结构中的东西)。

符号表很容易实现在地图(字典)接口的顶部(这可以通过散列表或平衡树来实现)。 Gensymfind一个新的钥匙,创build并返回它。 查找是通常的地图查找。 如果所有的密钥都是由gensym创build的,则密钥types可以保持抽象。

我不确定它叫什么,但它是在版本控制系统中实现的。 例如,Git商店有这样的数据types:你存储一个blob,并得到一个密钥,这是它的SHA-1哈希。 稍后,您可以使用该键检索您的blob。

我认为一些文件系统也可能以这种方式工作。

我可以称之为“匿名价值商店”。

听起来像一个哈希表/字典,虽然密钥是已知的,而不是给定的。

在“企业存储解决scheme”(或其他)的空间中,通常称为内容可寻址存储,假定密钥本身是从内容中导出(通过例如密码哈希),但是在大多数情况下只是一个实现细节。

我认为这是在Google存储上find的Big Table示例。 我们可以从关键容易获取元素。

听起来像一个可增长的arrays(std :: vector)。 在插入时,返回项目的数量作为ID,然后就完成了。 满足要求并提供简单的存储。

听起来像是符合Map和Hash的条件。

尽pipe要进一步确定元素,但必须对元素插入进行更具体的描述。

听起来像一本字典。 在哈希集中,元素表充当键,使用从元素集到自然数的哈希函数。 一个字典的工作方式是相似的,通过使用键集的哈希集合,并且表中的每个条目指向一个值。

我不知道任何一个插入一个元素,并得到一个关键,虽然…

它可能是一个哈希表的实现。

这可能适合几个结构的定义和function,但通常是指散列表或映射。