25

遍历 Dictionary,你会几种方式?

 3 years ago
source link: https://segmentfault.com/a/1190000025148747
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一:背景

1. 讲故事

昨天在 StackOverflow 上看到一个很有趣的问题,说: 你会几种遍历字典的方式,然后跟帖就是各种奇葩的回答,挺有意思,马上就要国庆了,娱乐娱乐吧,说说这种挺无聊的问题:smile::smile::smile:。

二: 使用 foreach 遍历

为了方便演示,先上一段测试代码:

var dict = new Dictionary<int, string>()
            {
                [10] = "A10",
                [20] = "A20",
                [30] = "A30",
                [40] = "A40",
                [50] = "A50"
            };

1. 直接 foreach dict

如果要拿百分比说话,估计有 50%+ 的小伙伴用这种方式,为啥,简单粗暴呗,其他没什么好说的,直接上代码:

foreach (var item in dict)
            {
                Console.WriteLine($"key={item.Key},value={item.Value}");
            }

fURV7rE.png!mobile

这里的 item 是底层在 MoveNext 的过程中用 KeyValuePair 包装出来的,如果你不信的话,看下源码呗:

public bool MoveNext()
    {
        while ((uint)_index < (uint)_dictionary._count)
        {
            ref Entry reference = ref _dictionary._entries[_index++];
            if (reference.next >= -1)
            {
                _current = new KeyValuePair<TKey, TValue>(reference.key, reference.value);
                return true;
            }
        }
    }

2. foreach 中 使用 KeyPairValue 解构

刚才你也看到了 item 是 KeyValuePair 类型,不过:ox::nose:的是 netcore 对 KeyValuePair 进行了增强,增加了 Deconstruct 函数用来解构 KeyValuePair,代码如下:

public readonly struct KeyValuePair<TKey, TValue>
    {
        private readonly TKey key;

        private readonly TValue value;

        public TKey Key => key;

        public TValue Value => value;

        public KeyValuePair(TKey key, TValue value)
        {
            this.key = key;
            this.value = value;
        }

        public void Deconstruct(out TKey key, out TValue value)
        {
            key = Key;
            value = Value;
        }
    }

有了这个解构函数,你就可以在遍历的过程中直接拿到 key,value,而不是包装的 KeyValuePair,这在 netframework 中可是不行的哈,实现代码如下:

foreach ((int key, string value) in dict)
            {
                Console.WriteLine($"key={key},value={value}");
            }

ba63mef.png!mobile

3. foreach keys

前面的例子都是直接对 dict 进行 foreach,其实你还可以对 dict.keys 进行 foreach 遍历,然后通过遍历出的 key 对 dict 进行类索引器读取,代码如下:

foreach (var key in dict.Keys)
            {
                Console.WriteLine($"key={key},value={dict[key]}");
            }

MnQJna.png!mobile

说到这里,不知道你是否有一个潜意识,那就是 dict 只能通过 foreach 进行遍历,真相是不是这样的呢? 要寻找答案,还是回头看一下 foreach 是如何进行遍历的。

public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, IDisposable, IEnumerator, IDictionaryEnumerator
{
    public bool MoveNext()
    {
        while ((uint)_index < (uint)_dictionary._count)
        {
            ref Entry reference = ref _dictionary._entries[_index++];
            if (reference.next >= -1)
            {
                _current = new KeyValuePair<TKey, TValue>(reference.key, reference.value);
                return true;
            }
        }
        _index = _dictionary._count + 1;
        _current = default(KeyValuePair<TKey, TValue>);
        return false;
    }
}

仔细看这个 while 循环,你就应该明白,本质上它也是对 entries 数组进行遍历,那底层都用了 while,我是不是可以用 for 来替换然后循环 dict 呢?哈哈,反正就是模仿呗。

三:使用 for 遍历

为了把 MoveNext 中的代码模拟出来,重点在于这条语句: ref Entry reference = ref _dictionary._entries[_index++]; , 其实很简单,_entries 数组内容的提取可以用 Linq 的 ElementAt 方法,是不是~~~ ,改造后的代码如下:

for (int i = 0; i < dict.Count; i++)
            {
                (int key, string value) = dict.ElementAt(i);

                Console.WriteLine($"key={key},value={dict[key]}");
            }

ba63mef.png!mobile

接下来是不是很好奇这个 ElementAt 扩展方法是如何实现的,一起看看源码吧。

public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, int index)
    {
        IList<TSource> list = source as IList<TSource>;
        if (list != null)
        {
            return list[index];
        }
        if (index >= 0)
        {
            using (IEnumerator<TSource> enumerator = source.GetEnumerator())
            {
                while (enumerator.MoveNext())
                {
                    if (index == 0)
                    {
                        return enumerator.Current;
                    }
                    index--;
                }
            }
        }
    }

从上面代码可以看到,如果当前的 source 没有实现 IList 接口的话,那就是一个巨大的坑,每一次执行 ElementAt 方法,最坏时间复杂度都是 O(N),就拿刚才的 for循环来说,它的最坏时间复杂度就是 O(n!) ,是不是比你想象的要恐怖的多,教训就是多实践,多看看源码~

四:总结

这篇列举了 4 种遍历 dict 的方式,不知你会用到哪几种? 要注意的是最后 ElementAt 对 Source 判别上的大坑一定要明白,不要想当然的以为就是 O(N) ,好了,更多的 遍历方式 欢迎补充!

更多高质量干货:参见我的 GitHub: dotnetfly


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK