Мне нужен HashSet, который сохраняет порядок вставки, есть ли какие-либо реализации этого в структуре?
HashSet, сохраняющий порядок
Ответы (3)
Стандартные .NET HashSet
не сохраняют порядок вставки. Для простых тестов порядок вставки может быть сохранен из-за аварии, но это не гарантируется и не всегда будет работать таким образом. Чтобы доказать, что достаточно сделать несколько удалений между ними.
См. Этот вопрос для получения дополнительной информации об этом: Сохраняет ли HashSet порядок вставки?
Я вкратце реализовал HashSet
, который гарантирует порядок вставки. Он использует Dictionary
для поиска элементов и LinkedList
для сохранения порядка. Все три операции: вставка, удаление и поиск по-прежнему работают в O (1).
public class OrderedSet<T> : ICollection<T>
{
private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
private readonly LinkedList<T> m_LinkedList;
public OrderedSet()
: this(EqualityComparer<T>.Default)
{
}
public OrderedSet(IEqualityComparer<T> comparer)
{
m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
m_LinkedList = new LinkedList<T>();
}
public int Count => m_Dictionary.Count;
public virtual bool IsReadOnly => m_Dictionary.IsReadOnly;
void ICollection<T>.Add(T item)
{
Add(item);
}
public bool Add(T item)
{
if (m_Dictionary.ContainsKey(item)) return false;
var node = m_LinkedList.AddLast(item);
m_Dictionary.Add(item, node);
return true;
}
public void Clear()
{
m_LinkedList.Clear();
m_Dictionary.Clear();
}
public bool Remove(T item)
{
if (item == null) return false;
var found = m_Dictionary.TryGetValue(item, out var node);
if (!found) return false;
m_Dictionary.Remove(item);
m_LinkedList.Remove(node);
return true;
}
public IEnumerator<T> GetEnumerator()
{
return m_LinkedList.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public bool Contains(T item)
{
return item != null && m_Dictionary.ContainsKey(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
m_LinkedList.CopyTo(array, arrayIndex);
}
}
IEqualityComparer<T>
для перехода к той же перегрузке IDictionary<T>
. Ваш пример нестандартно проверяет равенство через ссылки на объекты (по крайней мере, для классов) и не предлагает никаких вариантов для изменения этого поведения. Однако я понимаю, что это простой пример.
- person Simon Belanger; 25.07.2013
m_LinkedList.Remove(node);
на самом деле не O (n)?
- person HimBromBeere; 07.08.2020
Вы можете легко получить эту функцию, используя KeyedCollection<TKey,TItem>
указав один и тот же аргумент типа для TKey и TItem:
public class OrderedHashSet<T> : KeyedCollection<T, T>
{
protected override T GetKeyForItem(T item)
{
return item;
}
}
Remove
, будет ли он вызывать _2 _ или Remove(TKey)
? Первый - O (n), второй - O (1).
- person Scott Chamberlain; 27.02.2014
Remove(TKey)
, потому что это один из наиболее производных классов. Однако вызов Remove (), когда коллекция приведена как Collection ‹T› или ICollection ‹T›, вызовет перегрузку Remove(T)
.
- person kcnygaard; 27.02.2014
Remove(T)
, и Remove(TKey)
равны O (n), потому что KeyedCollection<T, T>
использует список для хранения элементов.
- person kcnygaard; 27.02.2014
System.Collections.Generic.HashSet<T>
, это вызовет System.ArgumentException
при дублировании ключа вместо возврата false
.
- person MrLore; 05.10.2015
KeyedCollection<TKey, TIitem>
происходит от Collection<TItem>
, который реализует IList<TItem>
, то есть индексированный доступ. По сути, это список, который также обеспечивает доступ на основе ключей (по умолчанию через вспомогательный внутренний словарь).
- person mklement0; 28.01.2019
.Remove(TKey key)
метод: это операция O (n), где n - количество. Кажется, что внутренний словарь используется только для поиска на основе ключей, который напрямую возвращает связанный элемент, он также не хранит информацию об индексе этого элемента во внутреннем списке.
- person mklement0; 28.01.2019
Если вам нужна постоянная сложность Add
, Remove
, Contains
и сохранение порядка, то в .NET Framework 4.5 такой коллекции нет.
Если вас устраивает сторонний код, загляните в мой репозиторий (разрешающая лицензия MIT): https://github.com/OndrejPetrzilka/Rock.Collections
Есть OrderedHashSet<T>
коллекция:
- на основе классического
HashSet<T>
исходного кода (из .NET Core) - сохраняет порядок вставки и допускает изменение порядка вставки вручную
- функции обратное перечисление
- имеет такую же сложность операции, что и
HashSet<T>
- Операции
Add
иRemove
на 20% медленнее по сравнению сHashSet<T>
- потребляет на 8 байт больше памяти на элемент