我需要一个保留插入顺序的 HashSet,框架中是否有任何实现?
问问题
26708 次
4 回答
40
标准 .NETHashSet
不保留插入顺序。
对于简单的测试,插入顺序可能会由于意外而被保留,但不能保证并且不会总是以这种方式工作。证明在两者之间进行一些删除就足够了。
有关详细信息,请参阅此问题: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);
}
}
于 2013-07-25T08:41:39.997 回答
23
KeyedCollection<TKey,TItem>
您可以使用为 TKey 和 TItem 指定相同的类型参数轻松获得此功能:
public class OrderedHashSet<T> : KeyedCollection<T, T>
{
protected override T GetKeyForItem(T item)
{
return item;
}
}
于 2014-02-26T21:27:03.990 回答
12
如果您需要保持、和 顺序的恒定复杂性Add
,那么 .NET Framework 4.5 中没有这样的集合。Remove
Contains
如果您对 3rd 方代码没问题,请查看我的存储库(许可 MIT 许可证): https ://github.com/OndrejPetrzilka/Rock.Collections
有OrderedHashSet<T>
收藏:
- 基于经典
HashSet<T>
源代码(来自 .NET Core) - 保留插入顺序并允许手动重新排序
- 特征反向枚举
- 具有相同的操作复杂性
HashSet<T>
Add
和Remove
操作相比,慢 20%HashSet<T>
- 每个项目多消耗 8 个字节的内存
于 2016-10-21T17:38:57.767 回答
0
您可以使用OrderedDictionary来保留插入顺序。但要注意移除项目的成本 (O(n))。
于 2022-03-05T01:13:48.917 回答