命名一个以可预测的顺序存储键的字典结构？

Note:尽管我的特定背景是 Objective-C，但我的问题实际上超越了编程语言的选择。另外，我将其标记为“主观”，因为否则肯定有人会抱怨，但我个人认为这几乎完全是客观的。另外，我知道这个相关的SO问题 https://stackoverflow.com/questions/376090/nsdictionary-with-ordered-keys/，但由于这是一个更大的问题，我认为最好将其作为一个单独的问题。请不要在没有充分阅读和理解问题的情况下批评该问题。谢谢！

我们大多数人都熟悉字典抽象数据类型 http://www.itl.nist.gov/div897/sqg/dads/HTML/dictionary.html存储键值关联，我们是否将其称为映射、字典、关联数组、哈希等，具体取决于我们选择的语言。字典的简单定义可以概括为三个属性：

1. 值通过键访问（与通过索引访问不同，如数组）。
2. 每个键都与一个值相关联。
3. 每个密钥必须是唯一的。

任何其他属性都可以说是为了特定目的的便利或专业化。例如，某些语言（尤其是 PHP 和 Python 等脚本语言）模糊了字典和数组之间的界限，并且确实提供了字典的排序。尽管这很有用，但此类添加并不是字典的基本特征。从纯粹的意义上来说，字典的实际实现细节是无关紧要的。

对于我的问题，最重要的观察是未定义键的枚举顺序— 字典可以按照它认为最方便的任何顺序提供键，并且由客户根据需要组织它们。

I've 创建自定义词典 http://dysart.cs.byu.edu/CHDataStructures/interface_c_h_lockable_dictionary.html强加特定的键顺序，包括自然排序（基于对象比较）和插入顺序。很明显，可以将前者命名为一些变体排序字典（我实际上已经实现了），但后者的问题更大。我见过链接哈希映射 http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html and 链接地图 http://commons.apache.org/collections/api-3.1/org/apache/commons/collections/map/LinkedMap.html（爪哇），有序字典 http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx（。网），有序字典 http://codeendeavor.com/gsdocs/net/guttershark/util/collections/OrderedDictionary.html（闪光），有序字典 http://www.python.org/dev/peps/pep-0372/（Python），以及有序字典 http://cocoawithlove.com/2008/12/ordereddictionary-subclassing-cocoa.html（目标-C）。其中一些更成熟，一些更具概念验证性。

链接哈希映射根据 Java 集合传统中的实现来命名——“链接”是因为它使用双向链表来跟踪插入顺序，而“散列”是因为它是 HashMap 的子类。除了用户不需要担心这一点之外，类名甚至没有真正表明它的作用。使用ordered似乎是现有代码之间的共识，但是关于这个主题的网络搜索也揭示了“有序”和“排序”之间可以理解的混淆，我也有同样的感觉。 .NET 实现甚至对明显的用词不当进行了注释，并建议应该将其改为“IndexedDictionary”，因为您可以在排序中的特定点检索和插入对象。

我正在设计一个框架和 API，并且希望尽可能智能地命名该类。从我的角度来看，indexed可能会起作用（取决于人们如何解释它，并基于字典的广告功能），ordered不精确并且很容易造成混乱，并且linked“已经出局了”（向 Monty Python 道歉）。 ;-)

作为用户，什么名称对您来说最有意义？是否有一个特定的名称可以准确地说明该类的作用？ （如果合适的话，我不反对使用稍长的名称，例如 InsertionOrderDictionary。）

Edit:另一个很强的可能性（在我下面的回答中讨论）是索引字典。我不太喜欢“插入顺序”，因为如果允许用户在特定索引处插入键、对键重新排序等，那么它就没有意义。

我投票 OrderedDictionary，原因如下：

除了一个实例之外，Cocoa 类中从来不使用“Indexed”。它始终显示为名词（NSIndexSet、NSIndexPath、objectAtIndex: 等）。 “Index”作为动词出现时只有一种情况，即 NSPropertyDescription 的“indexed”属性：isIndexed 和 setIndexed。 NSPropertyDescription 大致类似于数据库中的表列，其中“索引”指的是优化以加快搜索时间。因此，随着 NSPropertyDescription 成为核心数据框架的一部分，“isIndexed”和“setIndexed”相当于 SQL 数据库中的索引，这是有道理的。因此，称其为“IndexedDictionary”似乎是多余的，因为数据库中的索引是为了加快查找时间而创建的，但是字典already查找时间为 O(1)。然而，称其为“IndexDictionary”也是用词不当，因为 Cocoa 中的“索引”指的是位置，而不是顺序。两者在语义上是不同的。

我理解您对“OrderedDictionary”的担忧，但 Cocoa 已经开了先例。当用户想要维护特定的顺序时，他们使用“ordered”：-[NSApplicationorderedDocuments]、-[NSWindoworderedIndex]、-[NSApplicationorderedWindows]等。所以，John Pirie的想法基本上是正确的。

但是，您不希望插入字典成为用户的负担。他们想要创建一本字典once然后让它保持适当的秩序。他们甚至不想按特定顺序请求对象。订单规范应在初始化期间完成。

因此，我建议将 OrderedDictonary 创建为一个类簇，其中包含 InsertionOrderDictionary 和 NaturalOrderDictionary 以及 CustomOrderDictionary 的私有子类。然后，用户只需创建一个 OrderedDictionary，如下所示：

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

对于 CustomOrderDictionary，您可以让他们为您提供一个比较选择器，甚至（如果他们运行的是 10.6）一个块。我认为这将为未来的扩展提供最大的灵活性，同时仍然保持适当的名称。