🧝🏽 👨🏽‍🎓 🙏🏾 开发加载的应用程序时使用Dictionary的某些方面 👩🏻‍🎤 👩🏻‍🚒 ➿

在写这篇简短的笔记时，最近几次面试促使我担任首席开发人员在公司的职位。事实证明，有些申请人不熟悉字典是什么类型的机制，以及如何使用它。我什至遇到了一个非常激进的观点：他们说字典工作非常缓慢，并且由于以下事实：当将字典立即放置在大对象堆（LOH）中时，它不能在代码中使用，最好使用LINQ过滤器将查询应用于常规集合！

当然，这些并不是完全正确的陈述。在构建高负载代码和实现业务逻辑中，都经常需要字典作为一种机制。开发人员必须想象字典的组织方式，它如何与内存一起使用，它有多昂贵，几代人将留下多少“痕迹”和LOH，从而对垃圾收集器造成不必要的负担；如何更好地进行初始化，在这种情况下，最好使用键-值对的集合，在排序后的集合中，等等。

在本文中，我们将尝试解决其中一些问题。

众所周知，Microsoft词典的实现基于哈希表机制。在某些情况下，这为其他算法无法实现插入，搜索和删除操作的理想恒定复杂度O（1）。在某些情况下，拒绝使用此机制会带来性能和内存消耗方面的重大问题。

该体系结构的一个重要功能是使用相同大小的两个阵列来组织数据存储：

    int[] _buckets = new int[size];
    Entry[] _entries = new Entry[size];

这些阵列存储有用的数据和服务元素，以便快速访问它们。数组以边距创建，也就是说，它们几乎总是空的。

包装每个键值对的Entry帮助器实体是重要的类型：

    private struct Entry
    {
        public uint hashCode;
        public int next;
        public TKey key;
        public TValue value;
    }

, , , _entries. , ConcurrentDictionary, . ( 64 16 8 ) , .

_entries Dictionary 85000 LOH (, , 64 3372 , 1932). , , .

Microsoft _entries , Entry? LOH (, , ). , , .

, . 12 (4 _buckets 4 hashCode next Entry). , , , 12 . ? .

Dictionary . . Dictionary<int, int> ( ). , – ( ). 500 . 13 . 500 .

, . , , , .

, _buckets _entries , «», . LOH, .
, 746 3 .

, Dictionary . , , , .NET Core TrimExcess, .

, EnsureCapacity. .
, 400 10. (80 ). new Dictionary<int, int>(10001000), 190. , , .
, Dictionary EnsureCapacity(capacity*), . , _buckets _entries . . , EnsureCapacity(0).
, ( ) , , Dictionary: . , . , ( ).
TrimExcess. LOH . .

Dictionary. , Dictionary<Key, Value>, :

    public class Key
    {
        public int Item { get; set; }
        public Key(int item)
        {
            Item = item;
        }
        public override bool Equals(object obj)
        {
            return Item.Equals(obj);
        }
        public override int GetHashCode()
        {
            return Item.GetHashCode();
        }
    }
    public class Value
    {
        public int Item { get; set; }
        public Value(int item)
        {
            Item = item;
        }
    }

64 (8 ) (8 ).
, , 8 «» .
Item Key Value 8 , , Item 4 .

20 76 .

( ), .
, . .

, . ? , ( 10-20-30 ) . ?

. , Dictionary<int, int>(int count) :

    struct Entry<TValue>
    {
        public int[] Keys;
        public TValue[] Values;
        public Entry(int count)
        {
            Keys = new int[count];
            Values = new TValue[count];
        }
        public bool TryGetValue(int key, out TValue value)
        {
            for (int j = 0; j < Keys.Length; ++j)
            {
                if (Keys[j] == key)
                {
                    value = Values[j];
                    return true;
                }
            }
            value = default(TValue);
            return false;
        }
    }

count – -, .
.

, 18 count=10 134 count=190 ( 50 . ). ( – 29 ), ( 150) , (, ).

, (, , Entry , ).
, (callvirt GetHashCode Equals). – . , , , (generic) . .

SortedList<int, int>.
.

, .

: , . .

在给出的所有示例中，都应记住，在测试配置中使用的是小数据；因此，服务信息的开销相对较高。
测试项目可以在这里找到。

开发加载的应用程序时使用Dictionary的某些方面

More articles: