有人知道一个好的 LinkedDictionary/Hashed LinkedList 吗？

Question

我需要一个介于字典和链接列表之间的通用集合。我希望能够：

• 通过键访问元素
• 访问上一个和下一个元素

我已经查看了提供的通用集合以及专用集合。我还没有真正找到我要找的东西，最接近的集合是 OrderedDictionary 和 SortedDictionary。

快速 Google 发现了以下潜在集合：

• LinkedDictionary - http://www.glennslayden.com/code/c -sharp/linked-dictionary
• C5集合（支持哈希链表）- https://github.com/sestoft/C5/

每个似乎都很合适。不过，我想问问 SO 的专家们他们的建议是什么。

那么各位大师，你们有什么建议呢？您是否使用这些集合或其他集合来实现这些或相关目标？是否有一些明显明显的东西我应该注意但我却错过了？

Answer 1

我想你已经找到了自己的答案； C5 是一个很好的库，有你想要的东西，它有很棒的文档和测试。哦，它可以通过 Nuget 获得。

Answer 2

我自己写的。评论&欢迎建设性批评。

/// <summary>
/// A LinkedDictionary is a hybrid of a LinkedList and a Dictionary.
/// The LinkedDictionary can be traversed in four ways:
/// 1. Enumerated using .GetEnumerator() - which doesn't guarantee key order
/// 2. Indexed using .ElementAt() - risky, as the underlying dictionary doesn't guarantee order integrity
/// 3. Looked up by key like a regular Dictionary - slow due to hashing and binary-tree search overhead https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,bcd13bb775d408f1
/// 4. NEW WAY: crawled using .Next() or .Previous() - guarantees sequential order if values are added in key-sequential order
/// IT IS LINKED: Each node can be traversed back and forwards using Previous() and Next() like a LinkedList
/// IT IS OPTIONALLY SEQUENTIAL: if this flag is set, new values can only be added to at the end of the dictionary (keys are compared) to ensure index-sequence is preserved.
/// Partial inspiration from http://www.glennslayden.com/code/c-sharp/linked-dictionary
/// </summary>
public class LinkedDictionary<TKey, TValue>
    : Dictionary<TKey, LinkedDictionaryEntry<TValue>>,
        ILinkedDictionary<TKey, TValue>
    where TKey : IComparable
{
    #region Members

    ICollection<TKey> IDictionary<TKey, TValue>.Keys => base.Keys;
    ICollection<TValue> IDictionary<TKey, TValue>.Values => base.Values.Select(v => v.NodeValue).ToList();

    public new TValue this[TKey index]
    {
        // kludge for serialization error "InvalidOperationException: You must implement a default accessor because SerializableDictionary inherits from ICollection"
        // https://stackoverflow.com/questions/2331755/xmlserialize-exception
        // TODO: check this works!
        get
        {
            if (this.ContainsKey(index))
            {
                return base[index].NodeValue;
            }

            return default;
        }
        set => base[index] = new LinkedDictionaryEntry<TValue>(value);
    }


    public bool IsReadOnly => throw new NotImplementedException();

    public bool IsSequential { get; }

    #endregion Members

    #region Constructor

    public LinkedDictionary()
        : base()
    {
    }

    public LinkedDictionary(bool isSequential)
        : base()
    {
        this.IsSequential = isSequential;
    }

    public LinkedDictionary(bool isSequential,
                            SerializationInfo info,
                            StreamingContext  context)
        : base(info, context)
    {
        this.IsSequential = isSequential;
    }

    public LinkedDictionary(bool isSequential, IEqualityComparer<TKey> comparer)
        : base(comparer)
    {
        this.IsSequential = isSequential;
    }

    #endregion Constructor

    #region Methods

    #region Methods - Add
    /// <summary>
    /// Add new entry - check order if IsSequential flag is set
    /// </summary>
    /// <param name="key"></param>
    /// <param name="value"></param>
    public new void Add(TKey key, TValue value)
    {
        if (this.IsSequential)
        {
            // new item MUST have a key greater than the previous key; this is the optional Sequential character of this collection
            if (this.Count > 0)
            {
                int comparisonResult = key.CompareTo(base.Keys.Last());
                if (comparisonResult < 1)
                    throw new LoggedException("Cannot add new item.  Key must be greater than the last key.");
            }
        }

        // Create the new Linked entry
        LinkedDictionaryEntry<TValue> newEntry = new LinkedDictionaryEntry<TValue>(value);

        // Link the new value in IF there's something to link it to
        if (base.Values.Count > 0)
        {
            LinkedDictionaryEntry<TValue> existingLastValue = base.Values.Last();

            // Create forwards-looking link from the existing last entry to the new entry
            existingLastValue.Next = newEntry;

            // Create backwards-looking link from new entry to the existing last entry
            newEntry.Previous = existingLastValue;
        }

        base.Add(key, newEntry);
        ;
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        this.Add(item.Key, item.Value);
    }

    #endregion Methods - Add

    #region Methods - Get
    public bool TryGetValue(TKey key, out TValue value)
    {
        if (base.TryGetValue(key, out var theNode))
        {
            value = theNode.NodeValue;
            return true;
        }

        value = default(TValue);
        return false;
    }

    public TKey FirstKey() => this.Keys.First();

    public TKey LastKey() => this.Keys.Last();

    public ILinkedDictionaryEntry<TValue> FirstNode() => this.Values.First();

    public ILinkedDictionaryEntry<TValue> LastNode() => this.Values.Last();

    public TValue FirstValue() => this.Values.First().NodeValue;

    public TValue LastValue() => this.Values.Last().NodeValue;

    #endregion Methods - Get

    #region Methods - Remove
    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        return base.Remove(item.Key);
    }

    #endregion Methods - Remove

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        throw new NotImplementedException();
    }

    public new IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return base.GetEnumerator() as IEnumerator<KeyValuePair<TKey, TValue>>;
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    #endregion Methods
};


/// <summary>
/// LinkedDictionaryEntry
/// Base type for Values in LinkedDictionary<K, V>
/// </summary>
[DebuggerDisplay("_previous = {Previous} _next = {Next}")]
public class LinkedDictionaryEntry<TValue>
    : ILinkedDictionaryEntry<TValue>
{
    #region Members

    #region Members - Next

    public ILinkedDictionaryEntry<TValue> Next { get; set; }

    public ILinkedDictionaryEntry NextUntyped => this.Next;

    #endregion Members - Next

    #region Members - Previous

    public ILinkedDictionaryEntry<TValue> Previous { get; set; }

    public ILinkedDictionaryEntry PreviousUntyped => this.Previous;

    #endregion Members - Previous

    // VALUE
    public TValue NodeValue { get; }

    #endregion Members

    #region Constructor

    public LinkedDictionaryEntry(TValue nodeValue)
    {
        this.NodeValue = nodeValue;
    }

    #endregion Constructor

    #region Methods

    // Remove this item from a list by patching over it
    public void Unlink()
    {
        this.Previous.Next  = this.Next;
        this.Next.Previous = this.Previous;
        this.Next          = this.Previous = null;
    }

    // Insert this item into a list after the specified element
    public void InsertAfter(LinkedDictionaryEntry<TValue> e)
    {
        e.Next.Previous = this;
        this.Next       = e.Next;
        this.Previous    = e;
        e.Next          = this;
    }


    public void SetNext<TValue>(ILinkedDictionaryEntry<TValue> newEntry)
    {
        throw new NotImplementedException();
    }

    public override string ToString()
    {
        return this.NodeValue.ToString();
    }

    #endregion Methods
};


public interface ILinkedDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>
{
    TKey     LastKey();
    TKey     FirstKey();
    TValue   FirstValue();
    TValue   LastValue();
    new void Add(TKey key, TValue value);
    string ToString();
}


public interface ILinkedDictionaryEntry
{
    ILinkedDictionaryEntry PreviousUntyped { get; }
    ILinkedDictionaryEntry NextUntyped     { get; }
}

public interface ILinkedDictionaryEntry<TValue>
    : ILinkedDictionaryEntry
{
    ILinkedDictionaryEntry<TValue> Previous { get; set; }
    ILinkedDictionaryEntry<TValue> Next     { get; set; }

    TValue NodeValue { get; }

}