.NET中的LinkedHashMap

Question

我想知道在.NET中是否有java.util.LinkedHashMap的对应物？（也就是说，如果我访问一个元素，它们会自动（重新）按顺序排列。（布尔访问顺序））。

- Roger

---

我想了解这样一种逻辑，即仅仅访问集合中的一个元素就被认为是一种修改，从而导致重新排序。 - Cerebrus

我不熟悉这个类，但也许是为了允许更快地访问最常访问的元素？ - Adam Ralph

你可以在http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html 上查看有关 LinkedHashMap 的详细信息。它解释了用法，以及何时使用它（LRU缓存）。 - Peter Štibraný

请查看 保留插入顺序的通用键值对集合。 - nawfal

我在https://dev59.com/ml4b5IYBdhLWcg3wZwu3#36961779中回答了这个问题，我提供了一个最小的、没有依赖关系的C#实现的LinkedHashMap。希望能对你有所帮助！（另外：我们能把这两个问题链接起来吗？它们似乎问的是差不多的事情）。 - N0thing

Answer 1

仅为读者澄清一下：LinkedHashMap只在使用特定的构造函数重载时才会表现出这种行为。通常，元素是以插入顺序维护的。（对我来说感觉有点奇怪，但没关系。）

我不认为.NET中有这样的类。使用一个元素的链表和一个从键到链表节点的字典，构建它不太困难。访问将包括获取链表节点、将其移动到头部并返回值。

如果您想要，我今晚或明天很乐意实现它 - 虽然可能没有完整的单元测试等。（完全测试集合是件费时的事情！）

- Jon Skeet

---

这样一个行为取决于构造函数的奇怪类有什么用处？ - configurator

@Vojislav：这不是“典型的优化”。LinkedHashMap不会将条目向桶的开头移动，它只是记住每个条目何时被使用，并将条目移动到“最近使用的条目”列表的开头。这仅影响迭代顺序，而不影响下一次搜索的查找速度。 - Peter Štibraný

这里介绍的是LinkedHashMap的美妙之处。它创建了一个由链表支持的HashMap。如果你传入已经排序好的信息，比如从resultSet中获取的数据，那么它会保持这个顺序。可以按照插入的顺序进行迭代，并且速度很快。如果我只能使用一个集合，那么我会选择它。 - WolfmanDragon

@configurator，有很多时候你需要快速查找和迭代原始插入顺序。 - Paul Draper

供日后参考：我使用了一个简单的数组，结合 Array.Copy() 作为快速解决方法。你也可以考虑使用（非泛型）OrderedDictionary。 - Jeroen Vannevel

Answer 2

通过一些谷歌搜索，似乎没有内置的C#等效于LinkedHashMap，但是有一些第三方选项可用。

- AdamRalph

Answer 3

我已经使用System.Collections.Specialized.OrderedDictionary作为LinkedHashMap的替代品，它对我来说是有效的。关于OrderedDictionary有什么我需要注意的吗？（是的，它不是泛型的，但它在.NET 2或更新版本中可用）

- Nico

---

在我看来，OrderedDictionary与LinkedHashMap在两个重要方面有所不同。1）LinkedHashMap条目在读取后向前移动。也就是说，顺序由插入和选择（访问）决定。2）LinkedHashMap具有重载方法removeEldestEntry。如果您想构建缓存，则这些功能都非常有价值。 - Stan Bashtavenko

Answer 4

这是我在论坛上找到的C#实现:

它没有文档，但确实有一些测试。然而，它不是通用的。至少我认为这是一些东西。

@Jon: 如果您能快速实现，我也会很感激。我想象中，在LinkedList上面使用Dictionary应该是最好的选择，但我听说LinkedList存在垃圾回收问题，会使事情变慢。

- biozinc

---

垃圾回收问题可以通过节点池来解决。但是您需要自定义双向链表实现。 - George Polevoy

Answer 5

NHibernate有一个NHibernate.Util.LinkedHashMap实现。

如果您已经在代码中使用它，就像我一样，它可能会很方便。

- Luiz Henrique Martins Lins Rol

Answer 6

我知道这是一个旧话题，但有一个很棒的开源项目可以在.NET中实现LinkedHashMapC5

这里是LinkedHashMap的源代码。

- D-Shih

Answer 7

我可能来晚了，但是我用C#实现了LinkedHashMap（Java）的等效物LinkedDictionary，代码如下：

    public class LinkedDictionary<K, V> : IDictionary<K, V>, ICollection<KeyValuePair<K, V>>, IEnumerable<KeyValuePair<K, V>>
    {

    private List<K> list = new List<K>();
    private Dictionary<K, V> dictionary = new Dictionary<K, V>();

    public LinkedDictionary()
    {

    }

    public V this[K key] {
        get {
            return this.dictionary[key];
        }
        set {
            this.dictionary[key] = value;
            if (!this.list.Contains(key))
            {
                this.list.Add(key);
            }
        }
    }
            
    public int Count => this.dictionary.Count;

    public bool IsReadOnly => false;

    ICollection<K> IDictionary<K, V>.Keys => this.list;

    ICollection<V> IDictionary<K, V>.Values
    {
        get
        {
            List<V> values = new List<V>(this.dictionary.Count);
            foreach(K key in this.list)
            {
                V value = default(V);
                this.dictionary.TryGetValue(key, out value);
                values.Add(value);
            }
            return values;
        }
    }

    public void Add(KeyValuePair<K, V> item)
    {
        this.dictionary.Add(item.Key, item.Value);
        if (!this.list.Contains(item.Key))
        {
            this.list.Add(item.Key);
        }
    }

    public void Add(K key, V value)
    {
        this.dictionary.Add(key, value);
        if (!this.list.Contains(key))
        {
            this.list.Add(key);
        }
    }

    public void Clear()
    {
        this.dictionary.Clear();
        this.list.Clear();
    }

    public bool Contains(KeyValuePair<K, V> item)
    {
        return this.dictionary.Contains(item);
    }

    public bool ContainsKey(K key)
    {
        return this.dictionary.ContainsKey(key);
    }

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

    public bool Remove(KeyValuePair<K, V> item)
    {
        if (this.Contains(item)){
            this.list.Remove(item.Key);
            return this.dictionary.Remove(item.Key);
        } else
        {
            return false;
        }
    }

    public bool Remove(K key)
    {
        if (this.dictionary.ContainsKey(key))
        {
            this.list.Remove(key);
            return this.dictionary.Remove(key);
        }
        else
        {
            return false;
        }
    }

     public bool TryGetValue(K key, [MaybeNullWhen(false)] out V value)
    {
        return this.dictionary.TryGetValue(key, out value);
    }

    public V Get(K key)
    {
        V value = default(V);
        this.dictionary.TryGetValue(key, out value);
        return value;
    }

    public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
    {
        foreach (K key in this.list){
            V value = default(V);
            this.dictionary.TryGetValue(key, out value);
            yield return new KeyValuePair<K, V>(key, value);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private class LinkedDictionaryIterator<K, V> : IEnumerator<V>
    {

        private int i;
        private readonly Dictionary<K, V> dictionary;
        private readonly List<K> list;
        
        public LinkedDictionaryIterator(Dictionary<K, V> dictionary, List<K> list)
        {
            this.dictionary = dictionary;
            this.list = list;
            this.i = 0;
        }

        public void Dispose()
        {
            
        }

        public bool MoveNext()
        {
            return this.i < this.dictionary.Count;
        }

        public void Reset()
        {
            this.i = 0;
        }

        public KeyValuePair<K, V> Current
        {
            get
            {
                int ii = this.i;
                ++this.i;
                V value = default(V);
                K key = this.list[ii];
                this.dictionary.TryGetValue(key, out value);
                return new KeyValuePair<K, V>(key, value);
            }
        }

        V IEnumerator<V>.Current
        {
            get
            {
                int ii = this.i;
                ++this.i;
                V value = default(V);
                K key = this.list[ii];
                this.dictionary.TryGetValue(key, out value);
                return value;
            }
        }

        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }
    }

还有一个简单的单元测试，我将其与字典进行比较

    class UnitTest_LinkedDictionary
    {
        [Test]
        public void Test00()
        {
            LinkedDictionary<string, int> d = new LinkedDictionary<string, int>();



            d.Add("1", 1);
            d.Add("2", 2);
            d.Add("3", 3);
            d.Remove("2");
            d.Add("4", 4);

            d.Select(i => $"{i.Key}: {i.Value}").ToList().ForEach(Console.WriteLine);

        }

        [Test]
        public void Test01()
        {
            Dictionary<string, int> d = new Dictionary<string, int>();

            d.Add("1", 1);
            d.Add("2", 2);
            d.Add("3", 3);
            d.Remove("2");
            d.Add("4", 4);

            d.Select(i => $"{i.Key} :{i.Value}").ToList().ForEach(Console.WriteLine);

        }

    }

由于它基于字典和列表，它至少增加了列表访问和字典访问的时间复杂度。

- botg

Answer 8

由于在C#中仍然没有LinkedHashMap，而我需要这个功能，在最新的net core（3.1）上实现了一个。https://github.com/idlerboris/LinkedHashMap/blob/master/CustomCollections/CustomCollections/LinkedHashMap.cs。它经过基本测试，看起来不错，但欢迎贡献/报告问题。

- Boris Parfenenkov