这是哪种数据结构？

Question

数据结构的名称(如果存在)具有以下操作的名称是什么？

• 您可以插入一个元素,并为您提供一个键.
• 您可以通过其键检索元素.

Answer 1

内存分配器

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

Answer 2

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

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

如果您不了解Lisp,请将符号视为变量; gensym创建一个新变量,并symbol-value返回由引用指定的变量的值.这些操作在编写很好的Lisp支持的宏(元编程)时特别有用.Modern Lisp实现具有"uninterned"符号,即不在任何表中的符号,这使得事物更清晰.这与您想到的数据结构无关(未加工的符号将是您的数据结构中不存在的内容).

符号表很容易在地图(字典)界面上实现(通常使用哈希表或平衡树实现).Gensym找到了一把新钥匙,创造并返回它.查找是通常的地图查找.如果您的所有密钥都是由gensym创建的,则密钥类型可以保持抽象.

Answer 3

我不确定它叫什么,但它是在版本控制系统中实现的.例如,Git存储具有以下数据类型:在其中存储blob并获取密钥,即SHA-1哈希.稍后,您可以使用该密钥检索blob.

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

我可以称之为"匿名价值商店".