如何在Dictionary<ushort,ushort>中从指定索引查找连续2或4个可用键？

Great question! The straightforward loop you’ve got works for small datasets, but it can get sluggish if your dictionary has lots of occupied keys—especially if free gaps are few and far between. Let’s look at some cleaner, more performant approaches tailored to your use case.

Core Idea: Focus on Gaps, Not Every Index #

Instead of checking every possible starting index one by one, we can work with the occupied indices directly to identify gaps large enough for your float (2 slots) or double (4 slots) values. Here are two solid implementations:

1. Use a SortedSet for Fast Gap Detection #

First, convert your dictionary’s keys into a SortedSet<ushort>—this keeps the occupied indices sorted and lets us efficiently iterate through adjacent entries to spot gaps.

using System.Collections.Generic;
using System.Linq;

public ushort? FindNextFreeStartIndex(Dictionary<ushort, ushort> dict, int requiredSlots)
{
    const ushort StartIndex = 43001;
    const ushort MaxIndex = 65535;

    // Check if there's enough overall space left for the required slots
    if (MaxIndex - StartIndex + 1 < requiredSlots)
        return null;

    var occupied = new SortedSet<ushort>(dict.Keys);
    ushort currentCheck = StartIndex;

    // Case: No occupied indices at all
    if (occupied.Count == 0)
        return StartIndex;

    // Check the gap before the first occupied index
    if (occupied.Min > currentCheck && occupied.Min - currentCheck >= requiredSlots)
        return currentCheck;

    // Iterate through adjacent occupied indices to find valid gaps
    ushort previous = occupied.Min;
    foreach (ushort index in occupied)
    {
        if (index > previous)
        {
            int gapSize = index - previous;
            if (gapSize >= requiredSlots)
            {
                return (ushort)(previous + 1);
            }
        }
        previous = index;
    }

    // Check the gap after the last occupied index
    if (MaxIndex - previous >= requiredSlots)
        return (ushort)(previous + 1);

    // No valid contiguous gap found
    return null;
}

To use this for your types:

• For floats: Call FindNextFreeStartIndex(yourDict, 2)
• For doubles: Call FindNextFreeStartIndex(yourDict, 4)

2. Merge Occupied Intervals (Even Better for Large Datasets) #

If you have a huge number of occupied keys, merging them into contiguous intervals first can reduce the number of checks we need to do. This minimizes iterations and makes gap detection even faster.

using System.Collections.Generic;
using System.Linq;

public ushort? FindNextFreeStartIndexWithIntervals(Dictionary<ushort, ushort> dict, int requiredSlots)
{
    const ushort StartIndex = 43001;
    const ushort MaxIndex = 65535;

    if (MaxIndex - StartIndex + 1 < requiredSlots)
        return null;

    // Sort occupied keys to prepare for interval merging
    var sortedKeys = dict.Keys.OrderBy(k => k).ToList();
    if (sortedKeys.Count == 0)
        return StartIndex;

    // Merge occupied keys into contiguous (start, end) intervals
    var intervals = new List<(ushort start, ushort end)>();
    ushort currentStart = sortedKeys[0];
    ushort currentEnd = sortedKeys[0];

    foreach (ushort key in sortedKeys.Skip(1))
    {
        if (key == currentEnd + 1)
        {
            currentEnd = key;
        }
        else
        {
            intervals.Add((currentStart, currentEnd));
            currentStart = key;
            currentEnd = key;
        }
    }
    intervals.Add((currentStart, currentEnd));

    // Check gap before the first interval
    if (intervals[0].start > StartIndex && intervals[0].start - StartIndex >= requiredSlots)
        return StartIndex;

    // Check gaps between consecutive intervals
    for (int i = 1; i < intervals.Count; i++)
    {
        var prevInterval = intervals[i-1];
        var currInterval = intervals[i];
        int gapSize = currInterval.start - prevInterval.end - 1;
        if (gapSize >= requiredSlots)
        {
            return (ushort)(prevInterval.end + 1);
        }
    }

    // Check gap after the last interval
    if (MaxIndex - intervals.Last().end >= requiredSlots)
        return (ushort)(intervals.Last().end + 1);

    return null;
}

Why These Are Better Than the Naive Loop #

• Performance: Both methods run in O(K log K) time (where K is the number of occupied keys) instead of O(M) (where M is the number of indices checked until a gap is found). For sparse datasets, this is a massive speedup.
• Maintainability: The code is modular—you can easily adjust requiredSlots for other data types if needed.
• Edge Case Handling: Both implementations check for overall space availability, gaps at the start/middle/end of the index range, and return null if no valid gap exists.

Quick Optimization Tip #

If you’re repeatedly checking for gaps, consider keeping the SortedSet or merged intervals cached (instead of rebuilding them every time) to optimize further. This is especially useful if your dictionary doesn’t change often between gap checks.

内容的提问来源于stack exchange，提问作者Expressingx