按键删除字典并检索值

Question

有没有一种方法可以在同一步骤中通过Key删除Dictionary中的一个条目并检索其Value？

例如，我正在调用

Dictionary.Remove(Key);

但我也希望它同时返回值。该函数仅返回一个bool。

我知道我可以像下面这样做：

Value = Dictionary[Key];
Dictionary.Remove(Key);

但似乎这将搜索两次字典（一次获取值，另一次从字典中删除）。如果可能的话，我该如何同时完成这两个操作而不需要搜索两次字典？

- Mash

---

可能是重复的问题，参考链接：https://dev59.com/wmUo5IYBdhLWcg3wxBse。该帖子已有被采纳的答案。 - Kenneth

如果这也与性能有关，您可以在此处查看答案https://dev59.com/tHI-5IYBdhLWcg3wZ3jC，看看是否有所帮助。 - Silvermind

@Kenneth：所以，我猜在.NET中“内置”的字典类型无法完成这个任务？ - Mash

@Mash：假设你的“Key”缓存或者计算哈希码是微不足道的，那么双重查找的性能成本也是微不足道的。大多数字典具有O(1)的查找和删除。 - Guvante

据我所知，不行，但既然这是一个如此明显和合法的要求，我想肯定有人之前已经问过了。我猜唯一可能的方法就是实现自己的字典。不是要批评，但我怀疑它会更快 :) - Kenneth

Answer 1

从.NET Core 2.0开始，我们有：

public bool Remove (TKey key, out TValue value);

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.remove?view=netcore-2.0#System_Collections_Generic_Dictionary_2_Remove__0__1__

请注意，此 API 尚未包含在 .NET Standard 2.0 和 .NET Framework 4.7 中。

- vulcan raven

---

很好！感谢您提供这个参考。 - Mash

然而，它已经包含在.NET Standard 2.1（预览版）中。 - ElFik

现在，这应该是被接受的答案。 - Yennefer

@Yennefer 同意，已更新。 - Mash

Answer 2

因为它们都有我需要的缺失方法，所以我尝试了微软的ConcurrentDictionary和哥本哈根大学的C5 http://www.itu.dk/research/c5/，但是至少在我的用例中，它们比Dictionary慢得多（我指的是5倍到10倍）。我认为C5一直在对键和值进行排序，而Concurrent Dictionary则“过于担心”调用线程。我不是来讨论为什么这两个版本的Dictionary很慢的原因。 我的算法正在寻找和替换一些条目，其中第一个键将被删除，并添加新的键（某种队列）... 唯一剩下的事情就是修改原始的.Net mscorelib的Dictionary。我从Microsoft下载了源代码，并在我的源代码中包含了Dictionary类。为了编译，我还需要带上HashHelpers类和ThrowHelper类。所有剩下的就是注释掉一些行（例如[DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))]和一些资源获取）。显然，我必须向复制的类添加缺失的方法。另外，不要尝试编译Microsoft源代码，否则你将会花费数小时，我很幸运能够让它运行。

   public bool Remove(TKey key, out TValue value)
    {
        if (key == null)
        {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }

        if (buckets != null)
        {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int bucket = hashCode % buckets.Length;
            int last = -1;
            for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                {
                    if (last < 0)
                    {
                        buckets[bucket] = entries[i].next;
                    }
                    else
                    {
                        entries[last].next = entries[i].next;
                    }
                    entries[i].hashCode = -1;
                    entries[i].next = freeList;
                    entries[i].key = default(TKey);
                    value = entries[i].value;
                    entries[i].value = default(TValue);
                    freeList = i;
                    freeCount++;
                    version++;
                    return true;
                }
            }
        }
        value = default(TValue);
        return false;
    }

最后我修改了命名空间为System.Collection.Generic.My。在我的算法中，只有两行代码获取值，然后在下一行删除它。我用new方法替换了它，并获得了7％-10％的稳定性能提升。希望这对于这个使用案例以及任何其他不应该重新实现Dictionary的情况有所帮助。

- Dan M

---

基本上，修改微软的库。这个问题已经存在一段时间了，这个答案似乎是最好的解决方案，所以我会接受这个解决方案。谢谢！ - Mash

Answer 3

虽然这不是OP所要求的，但我忍不住要发一个修正后的扩展方法：

public static bool Remove<TKey, TValue>(this Dictionary<TKey, TValue> self, TKey key, out TValue target)
{
    self.TryGetValue(key, out target);
    return self.Remove(key);
}

- bavaza

Answer 4

ConcurrentDictionary 类有一个 TryRemove 方法，尝试从 System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue> 中删除并返回指定键的值。如果该键不存在，则返回 TValue 类型的默认值。

https://msdn.microsoft.com/en-us/library/dd287129(v=vs.110).aspx

- Prasanth Louis

Answer 5

你可以使用扩展方法来实现：

public static string GetValueAndRemove<TKey, TValue>(this Dictionary<int, string> dict, int key)
{
    string val = dict[key];
    dict.Remove(key);
    return val;    
}

static void Main(string[] args)
{
    Dictionary<int, string> a = new Dictionary<int, string>();
    a.Add(1, "sdfg");
    a.Add(2, "sdsdfgadfhfg");
    string value = a.GetValueAndRemove<int, string>(1);
}

- Jeremy Thompson

---

既然Remove是安全的，我建议先检查一下键是否存在，但无论如何都是个好主意 :) - Silvermind

谢谢您的回复，但是当我说“在同一步骤中”时，我应该更清楚。我真正的意思不是两次搜索字典。string val = dict[key]将会搜索一次字典，而dict.Remove(key)将再次搜索它。 - Mash

@Mash Dictionary非常快，因此在性能方面不应该是一个大问题。 - Silvermind

@Silvermind 我同意，这确实不是性能问题，只是在我编写代码时想到的一个想法。 - Mash

如果你深入研究哥本哈根大学通用集合库中的字典实现，你可能会发现相同的实现方式。不幸的是，你不能一步完成这个过程。 - Jeremy Thompson

@JeremyThompson 我还没有看过他们的代码，但我不愿意为了使用他们的字典而经历这么多麻烦，还是用微软的吧。你提供的能够一次性完成的方法很好，点赞！ - Mash

Answer 6

您可以扩展该类以添加该功能：

public class PoppableDictionary<T, V> : Dictionary<T, V>
{
    public V Pop(T key)
    {
        V value = this[key];
        this.Remove(key);
        return value;
    }
}

- mmutilva

---

这仍然需要两次查找。OP请求一种消除双重查找的方法。 - Kenneth

你是对的。我基于@Guvante的评论回答，他指出字典的访问操作是o(1)，因此在两次访问字典时没有显着的性能损失。 - mmutilva

@Toto 是的，我主要是想避免在字典中进行双重查找，但感谢您提供了一种可以在一个调用中完成的方法（点赞）。 - Mash