Словари C # - это простой способ узнать, существует ли что-то и т. Д. У меня есть вопрос, как они работают. Допустим, вместо словаря я использую ArrayList. Вместо использования ContainsKey
(или эквивалентного метода на другом языке) я перебираю ArrayList, чтобы проверить, существует ли там что-то (или выполняет двоичный поиск, если данные отсортированы или что-то подобное). Какая разница в эффективности? ContainsKey
Использует ли метод какой-то более эффективный способ, нежели циклический просмотр ключей и проверку, существует ли то, что я ищу?
Если, скажем, я создал определенную хеш-функцию, которая соответствует типу данных, которые у меня есть, и специально разработана для этого набора данных, то да, эта хеш-функция действительно быстрее, чем циклически проходить по данным. Но словари являются общими. Метод ContainsKey не является специфичным для данных, которые он получает, это общий метод поиска.
В основном то, что я спрашиваю. Словари полезны для программистов. Они включают методы, которые помогают во многих вещах, и объединяют строки с целыми числами (ключами и значениями) и многими другими. Но что касается эффективности, что они предлагают? Какая разница в том, dictionary
против ArrayList
изstructs(string,int)
источник
Data Structures
эта ссылка на вики может быть вам болееОтветы:
Вам нужно немного покопаться, чтобы увидеть, как словарь реализован в C # - он не так очевиден, как HashMap (хэш-таблица) или TreeMap (отсортированное дерево) (или ConcurrentSkipListMap - список пропуска ).
Если вы покопаетесь в разделе «Замечания»:
И там у нас это есть. Это хеш-таблица . Обратите внимание, что я связал там статью из Википедии - ее довольно хорошо читают. Вы можете прочитать раздел о разрешении коллизий. Можно получить патологический набор данных, в котором поиск переходит в O (N) (например, все, что вы вставляете, попадает в одно и то же хеш-значение или индекс в хеш-таблице, и у вас остается линейное зондирование ).
В то время как Словарь является решением общего назначения, вы не должны передавать конкретные типы (такие как Словарь) - вы должны передавать интерфейсы. В этом случае этот интерфейс
IDictionary
( документы ). Для этого вы вполне способны написать собственную реализацию словаря, которая оптимально подходит для ваших данных.Что касается эффективности различных поиска / содержит?
Для большинства людей хеш-таблица - это то, что они хотят.
Вы можете обнаружить, что вместо этого вам нужен SortedDictionary :
Хотя, опять же, если структура данных не идеально подходит для ваших данных, вам предоставляются инструменты (интерфейсы), чтобы иметь возможность написать структуру, которая лучше всего подходит для ваших данных.
Сам словарь является абстрактным типом данных . Вы даете мне словарь, и я знаю, что я могу с ним сделать, и все инструменты там для меня, чтобы использовать его по природе, как словарь. Если бы вы дали мне ArrayList, я бы написал свой собственный код для поиска, вставки или удаления элементов из списка. Это напрасно тратит мое время, а также означает, что вероятность ошибки увеличивается, поскольку я копирую код снова и снова с места на место.
источник