Implementing hash table with both key and index-based access in O(1)

There is a data structure called NameObjectCollectionBase in .NET which I'm trying to understand.

Basically, it allows to enter arbitrary string => object key/value-pairs with both the possibility of the key and the value being null. A key may be used by multiple objects. Access is granted through both an index-based and a string-based access, whereas the string-based access returns only the first value with the specified key.

What they promise, is

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) 

Index-based access does have nothing to do with the insertion order. However, get(int) and getkey(int) have to line up with each other.

I'm wondering how the structure may be implemented. Allowing both index and key-based access at the same time in O(1) seems not trivial to implement. They state on the MSDN page that "The underlying structure for this class is a hash table." However, the C# Hash tables don't allow multiple values per key and alo not null-keys.

Implementing it as a Dictionary<string, List<object> does not seem to be the solution as get(string) would be O(1) but get(int) not since you have to traverse all keys to find out which key has how many items in it.

Implementing it as two separated lists where one is a simple List<string> for the keys and a List<Object> for the values in combination of a Dictionary<string, int> which points for each key to the index of the first value would allow both types of access in O(1) but would not allow removing in an efficient way since all indices would have to be updated in the hashtable (would be possible in O(n) but doesn't seem to be the best solution). Or would there be a more efficient way to remove an entry?

How could such a data structure be implemented?

---

NameObjectCollectionBase uses both a Hashtable and an Arraylist to manage the entries. Have a look for yourself!

Microsoft provides reference source code for .NET libraries and can be integrated into Visual Studio:

http://referencesource.microsoft.com/

You can even debug the .NET library:

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

Or you can grab a copy of dotPeek, a free decompiler:

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