c# - 在 O(1) 中实现具有基于键和基于索引的访问的哈希表

Question

有一个数据结构叫做 NameObjectCollectionBase 在我试图理解的 .NET 中。

基本上，它允许输入任意字符串 => 对象键/值对，键和值都可能为空。一个键可以被多个对象使用。通过基于索引和基于字符串的访问授予访问权限，而基于字符串的访问仅返回具有指定键的第一个值。

他们 promise 的是

add(string, object)        O(1) if no relocation, O(n) otherwise
clear                      O(1)
get(int)                   O(1) corresponds to getkey(int)
get(string)                O(1) returns first object found with given key
getallkeys                 O(n) if objects share a key, it is returned that many times
getallvalues               O(n)
getallvalues(type)         O(n) returns only objects of a given type
getkey(int)                O(1) corresponds to get(int)
haskeys                    O(1) if there are objects with a non-null key
remove(string)             O(n) remove all objects of a given key
removeat(int)              O(n)
set(int, object)           O(1) 
set(string, object)        O(1) sets the value of the first found object with given key
getenumerator              O(1) enumerator over keys
copyto(array, int)         O(n) 

基于索引的访问与插入顺序无关。然而，get(int)和 getkey(int)必须互相排队。

我想知道如何实现该结构。在 O(1) 中同时允许基于索引和基于键的访问似乎实现起来并不容易。他们在 MSDN 页面上声明“此类的基础结构是哈希表”。但是，C# 哈希表不允许每个键有多个值，也不允许空键。

将其实现为 Dictionary<string, List<object>似乎不是解决方案，因为 get(string) 是 O(1) 而 get(int) 不是，因为您必须遍历所有键才能找出哪个键中有多少项。

将其实现为两个单独的列表，其中一个是简单的 List<string> key 和一个List<Object>对于 Dictionary<string, int> 组合的值每个键指向第一个值的索引将允许 O(1) 中的两种类型的访问，但不允许以有效的方式删除，因为所有索引都必须在哈希表中更新(在 O( n) 但似乎不是最佳解决方案)。或者是否有更有效的方法来删除条目？

如何实现这样的数据结构？

Answer 1

NameObjectCollectionBase 使用哈希表和数组列表来管理条目。你自己看看吧!

Microsoft 提供了 .NET 库的引用源代码，可以集成到 Visual Studio 中:

http://referencesource.microsoft.com/

您甚至可以调试 .NET 库:

http://msdn.microsoft.com/en-us/library/cc667410(VS.90).aspx

或者您可以下载一份免费的反编译器 dotPeek:

http://www.jetbrains.com/decompiler/