В .NET существует структура данных с именем NameObjectCollectionBase, которую я пытаюсь понять.
По сути, он позволяет вводить произвольные строки строка => ключ / значение объекта с возможностью того, что ключ и значение равны нулю. Ключ может использоваться несколькими объектами. Доступ предоставляется как на основе индекса, так и на основе строки, тогда как доступ на основе строки возвращает только первое значение с указанным ключом.
То, что они обещают, это
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> для ключей и List<Object> для значений в комбинации с Dictionary<string, int>, который указывает для каждого ключа на индекс первого значения, позволил бы оба типы доступа в O (1), но не позволят эффективно удалять, так как все индексы должны быть обновлены в хеш-таблице (возможно в O (n), но не кажется лучшим решением). Или есть более эффективный способ удалить запись?
Как можно реализовать такую структуру данных?