在字典或相关集合中查找“下一个可用”键

本文关键字：下一个 下一个可用 查找 字典 集合 | 更新日期: 2023-09-27 18:35:49

我想编写一个linq扩展（或自定义字典，排序列表列表或任何最好的解决方案），它将允许我向集合添加一个值，其键是"下一个可用"的集合。

例如：

int CreatedKey = IncrementDictionary.AddNext(myCustomer);

如果当前存在的密钥如下所示：

1
2
8
4
3

然后，它会将 myCustomer 添加到具有键 5 的字典中，并返回该键。

你觉得怎么样？

在字典或相关集合中查找“下一个可用”键

public static int AddNext(this Dictionary<int, string> dict)
{
    int min = dict.Keys.Min();
    int max = dict.Keys.Max();
    return Enumerable.Range(min, max-min).Except(dict.Keys).First();   
}

将其用作

int result = new Dictionary<int, string>(){ {1, "a"}, {2, "a"}, 
                                            {8, "a"}, {4, "a"}, 
                                                      {3, "a"}}.AddNext();

这里result是5。

您可以使用带有扩展方法的 SortedList 添加到下一个自动检索的键。

假设数据结构是任何对象，带有数字键，

以下是排序列表的扩展方法

public static class SortedListExtensions
{
    ///Add item to sortedList (numeric key) to next available key item, and return key
    public static int AddNext<T>(this SortedList<int, T> sortedList, T item)
    {
        int key = 1; // Make it 0 to start from Zero based index
        int count = sortedList.Count;
        int counter=0;
        do
        {
            if (count == 0) break;
            int nextKeyInList = sortedList.Keys[counter++];
            if (key != nextKeyInList) break;
            key = nextKeyInList +1;
            if (count == 1 || counter == count  ) break;

            if (key != sortedList.Keys[counter])
                break;
        } while (true);
        sortedList.Add(key, item);
        return key;
    }
}

它可以像下面一样使用

  SortedList<int, string> x = new SortedList<int, string>();
        x.Add(4, "BCD");
        x.Add(6, "BCD");
        x.AddNext("a");
        x.AddNext("b");
        x.AddNext("c");
        x.AddNext("d");
        x.AddNext("e");
        foreach (var item in x)
            Console.WriteLine(item.Key + " " + item.Value);

输出为 

        1 a
        2 b
        3 c
        4 BCD
        5 d
        6 BCD
        7 e

您可以使用字典或任何其他数据结构。在这种情况下，将需要双循环。在排序列表的情况下，搜索键时会保存一个循环。此循环由使用二进制搜索算法SortedList.Add函数内部使用。

二分搜索比循环所有元素更快（对于较大尺寸的数据）。

这是我的解决方案比第一个短的解决方案，但你可以从中得到一个想法。

        Dictionary<int, string> x = new Dictionary<int, string>();
        x.Add(1, "a");
        x.Add(2, "a");
        x.Add(3, "a");
        x.Add(4, "a");
        x.Add(8, "a");
        Console.WriteLine((x.Keys.Where(k => !x.Keys.Contains(k + 1)).Min() + 1).ToString());

您是否正在寻找这样的东西（它显然只能包含 1000 个元素）？可以有许多其他解决方案，但很难说出您到底想做什么。无论如何，这可能是一个起点。

public class IncrementDictionary : Dictionary<int, object>
{
    private bool[] usedKeys = new bool[1000];
    public new void Add(int key, object value)
    {
        base.Add(key, value);
        usedKeys[key] = true;
    }
    public new void Clear()
    {
        base.Clear();
        usedKeys = new bool[1000];
    }
    public new object this[int key] 
    {
        get
        {
            return base[key];
        }
        set
        {
            base[key] = value;
            usedKeys[key] = true;
        }
    }
    public new bool Remove(int key)
    {
        usedKeys[key] = false;
        return base.Remove(key);
    }
    public int AddNext(object anObj)
    {
        int newKey = -1;
        for (int i = 1; i < 1000; i++)
            if (!usedKeys[i])
            {
                newKey = i;
                break;
            }
        if (newKey > 0)
            this.Add(newKey, anObj);
        return newKey;
    }
}

嗯...这是一个老问题，但我想回答。

考虑到如果你有一个空集合，你必须指定你的最小值是什么，Nikhil Agrawal的代码可能会得到改进。所以代码变成：

 public static int FirstFree(Dictionary<int, Guid> dict, int minumum)
    {
        int min = dict.Count == 0
            ? minumum                       //use passed minimum if needed
            : dict.Keys.Min();              //use real minimum
        int max = dict.Count > 1
            ? dict.Keys.Max() + 2           //two steps away from maximum, avoids exceptions
            : min + 2;                      //emulate data presence
        return Enumerable.Range(min, max).Except(dict.Keys).First();
    }

但是，如果您在定义的范围内工作，则还应该知道是否有空间来存储值。这可以是这样：

public static int? FirstFree(Dictionary<int, Guid> dict, int min, int max)
    {
        if (max <= min)
            throw new Exception($"Specified range is invalid (must be max > min)");
        if (max - min + 1 == dict.Count)
            //no space left
            return null;
        return Enumerable.Range(min, max).Except(dict.Keys).First();
    }

如果您不喜欢 nullable-int，您可以检查结果是否是允许的最小值。显然，如果您指定 min=int，它不起作用。MinValue，我知道，但在这种情况下，问题是这种方法创建的大量集合！

public static int FirstFree(Dictionary<int, Guid> dict, int min, int max)
    {
        if (max <= min)
            throw new Exception($"Specified range is invalid (must be max > min)");
        if (max - min + 1 == dict.Count)
            //no space left
            return int.MinValue;
        return Enumerable.Range(min, max).Except(dict.Keys).First();
    }
实际上遇到了一个

奇怪的需要这样做。此解决方案比其他任何答案都更快、更直接。

public static void AddNext<T>(this IDictionary<int, T> dict, T item, int startIndex = 0, int maxIndex = Int32.MaxValue)
{
    for (int i = startIndex; i < maxIndex; i++)
    {
        if (!dict.ContainsKey(i))
        {
            dict[i] = item;
            break;
        }
    }
}

我在这里使用秒表测试了这个和其他两个答案，以及一个包含 1100 万个 GUID 字符串的集合，在 10m 索引处有一个孔。

我的花了 80 毫秒。

添加检查以包含具有 null 值的现有密钥将在 152ms 处出现。

Tilak的（接受的答案）花了256ms。这个答案使用排序列表，但问题是字典，这意味着不需要排序。

Nikhil的（大多数赞成票）花了709ms。此外，如果没有"漏洞"并且下一个可用索引位于末尾，它会引发异常。

一位评论者暗示，这个用例有更好的数据结构，但没有提到是哪些。很想了解更多。

相关文章：