Почему я должен использовать HashSet над Словарем?

Question

Я пытаюсь реализовать список кэшированных путей по алгоритму A *. В настоящее время, кэшированные пути хранятся в виде списка, как это:

readonly List<CachedPath> _cachedPaths = new List<CachedPath>(); 

Операции, выполняемые над этого списка:

FirstOrDefault, чтобы получить элемент, который удовлетворяет определенным условиям

var cached = _cachedPaths.FirstOrDefault(p => p.From == from && p.To == target && p.Actor == self); 

Извлеките и элемент

_cachedPaths.Remove(cached); 

Дополнения

_cachedPaths.Add(new CachedPath { 
        From = from, 
        To = target, 
        Actor = self, 
        Result = pb, 
        Tick = _world.WorldTick 
       }); 

Примечание: Класс CachedPath имеет GetHashCode и Equals перекрываться только From, To и актера, так два экземпляра, которые имеют те же атрибуты имеют одинаковый хеш и равенство.

Учитывая, что быстрый поиск (содержит), вставки и удаления в «HashSet» - это O (1) (если я не ошибаюсь), я рассматривал использование «HashSet» для выполнения этих операций. Единственная проблема - FirstOrDefault, что я должен был перечислить всю коллекцию, чтобы получить ее.

Учитывая эту проблему, я считал также, используя словарь проиндексированы хэш From, To и Актер:

Dictionary<int, CachedPath> cachedPath 

Еще раз, если я не ошибаюсь, словарь также предлагает O (1) в вставки, удаления, а также поиск по ключу. Это заставляет меня думать, что словарь - это возможность поиска элементов HashSet + O (1).

Я что-то упустил? Действительно ли Словарь лучше, чем HashSet, в том смысле, что он поддерживает больше операций?

Заранее спасибо.

Answer 1

Dictionary не лучше, чем HashSet, это просто другое.

• Вы используете HashSet, когда вы хотите сохранить неупорядоченный набор элементов, и
• Вы используете Dictionary, когда вы хотите, чтобы связать набор элементов, называемых «ключами» с другой коллекцией предметов под названием «значение "

Можно было бы думать о HashSet как Dictionary без каких-либо связанных с ними ценностей (на самом деле, HashSet иногда реализуется с помощью Dictionary за кадром), но не надо думать об этом таким образом: мышление два из них полагаются разные вещи, отлично работает.

В вашем случае вы могли бы потенциально повысить производительность за счет создания словаря актером, как это:

Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor 

Таким образом, ваш линейный поиск будет быстро выбрать суб-список, основанный на актера, а затем искать линейно по цели:

var cached = _cachedPathsByActor[self].FirstOrDefault(p => p.From == from && p.To == target); 

или сделав компаратор равенства, который учитывает все три элемента, и используя Dictionary с CachedPath как оба ключа и значения, и что обычай IEqualityComparer<T> как ключевой компаратором:

class CachedPathEqualityComparer : IEqualityComparer<CachedPath> { 
    public bool Equals(CachedPath a, CachedPath b) { 
     return a.Actor == b.Actor 
      && a.From == b.From 
      && a.To == b.To; 
    } 
    public int GetHashCode(CachedPath p) { 
     return 31*31*p.Actor.GetHashCode()+31*p.From.GetHashCode()+p.To.GetHashCode(); 
    } 
} 
... 
var _cachedPaths = new Dictionary<CachedPath,CachedPath>(new CachedPathEqualityComparer()); 
... 
CachedPath cached; 
if (_cachedPaths.TryGetValue(self, out cached)) { 
    ... 
} 

Однако этот подход предполагает, что было бы в самый один элемент в словаре с одинаковым From, To и Actor.

Answer 2

Хешсет не будет генерировать исключение при выполнении добавления. Вместо этого он возвращает bool, отражающий успех добавления.

Также hashset не требует пары keyValue. Я использую хэшеты, чтобы гарантировать набор уникальных значений.