自动字典键？

Question

我搜索了一段时间，发现能够创建一个包含变量及其对应唯一键的列表的最佳方法是使用 HashTable 或 Dictionary。但我没有找到任何可以生成自动键(整数类型)的方法。我想调用一个函数，将一个对象(作为参数传递)添加到字典中，并返回自动生成的键(int)，而且不会有任何键重复。我该如何实现这个功能？我完全无法解决这个问题！

编辑：为了澄清事情。这是一个服务器，我想为每个客户端分配一个唯一的键。如果我使用最大键值，这个值很快就会达到大型服务器上的 int 最大值。因为如果一个客户端连接然后断开连接，他留下一个未使用的值，应该重新使用它，以避免达到非常高的键最大值。

- None

---

只需编写一个类，该类包装了一个字典，并使用您描述的方法 - 我假设您知道如何从对象生成密钥？ - RB.

新的键是如何生成的？如果只是自动递增，那么你可以简单地包装一个 List<T>。 - Lee

使用列表 - 它会将项目保存在索引后面，这些索引通常是整数。 - Stefan Steinegger

如果删除了第一个对象@StefanSteinegger，所有其他键都会改变。我需要恒定的键值。 - None

如果您正在尝试为数据库生成键，则让数据库完成这项工作会比任何无法控制数据库的代码基础更好。如果您需要唯一的ID，则应忘记int型，而应选择GUID，因为这正是它们设计的目的。 - MikeT

Answer 1

以下代码可以实现并重复使用已释放的键：

internal class AutoKeyDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
    private readonly Dictionary<TKey, TValue> inner;
    private readonly Func<TKey, TKey> incrementor;
    private readonly Stack<TKey> freeKeys;
    private readonly TKey keySeed;
    private TKey currentKey;

    public AutoKeyDictionary(TKey keySeed, Func<TKey, TKey> incrementor) 
    {
        if (keySeed == null)
            throw new ArgumentNullException("keySeed");

        if (incrementor == null)
            throw new ArgumentNullException("incrementor");

        inner = new Dictionary<TKey, TValue>();
        freeKeys = new Stack<TKey>();
        currentKey = keySeed;
    }

    public TKey Add(TValue value) //returns the used key
    {
        TKey usedKey;

        if (freeKeys.Count > 0)
        {
            usedKey = freeKeys.Pop();
            inner.Add(usedKey, value);
        }
        else
        {
            usedKey = currentKey;
            inner.Add(usedKey, value);
            currentKey = incrementor(currentKey);
        }

        return usedKey;
    }

    public void Clear()
    {
        inner.Clear();
        freeKeys.Clear();
        currentKey = keySeed;
    }

    public bool Remove(TKey key)
    {
        if (inner.Remove(key))
        {
            if (inner.Count > 0)
            {
                freeKeys.Push(key);
            }
            else
            {
                freeKeys.Clear();
                currentKey = keySeed;
            }

            return true;
        }

        return false;
    }

    public bool TryGetValue(TKey key, out TValue value) { return inner.TryGetValue(key, out value); }
    public TValue this[TKey key] { get {return inner[key];} set{inner[key] = value;} }
    public bool ContainsKey(TKey key) { return inner.ContainsKey(key); }
    public bool ContainsValue(TValue value) { return inner.ContainsValue (value); }
    public int Count { get{ return inner.Count; } }
    public Dictionary<TKey,TValue>.KeyCollection Keys { get { return inner.Keys; } }
    public Dictionary<TKey, TValue>.ValueCollection Values { get { return inner.Values; } }
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { return inner.GetEnumerator(); }
    IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)inner).GetEnumerator(); }
}

免责声明：我没有测试过这段代码，可能存在一些微不足道的错误，但总体思路是正确的。

- InBetween

Answer 2

编写一个能够实现此功能的类。类似这样的内容：

class AutoIndexDictionary : IEnumerable<Whatever>
{
  private readonly Dictionary<int, Whatever> myDict = new Dictionary<int, Whatever>();

  private int currentIndex = 0;

  public int Add(Whatever item)
  {
    var myIndex = currentIndex 
    myDict.Add(myIndex, item);
    currentIndex ++;
    return myIndex;
  }

  public void Remove(int index)
  {
    myDict.Remove(index);
  }

  // implement IEnumerable, indexer etc.
  // ...
}

- Stefan Steinegger

---

我在这里写了相同的代码。编辑：你可以使当前索引可从外部读取：public int CurrentIndex { get; private set; } = 0;。 - Jeppe Stig Nielsen

Answer 3

创建一个方法，使用LINQ从字典中获取最大键值，将其加1，然后将其用作要添加的值的键，如下所示：

public void AddToMyDictionary(string value)
{
    int NextKey = MyDictionary.Keys.Max() + 1;
    MyDictionary.Add(NextKey, value);
}

显然，这假设你的字典是一个Dictionary<int, string>，但你可以根据自己的需要进行修改。

如果你想重复使用已经移除的键，当添加/删除某些内容时，请存储下一个索引。

private int NextKey = 0;

public int AddToMyDictionary(string value)
{
    int currentKey = NextKey;
    MyDictionary.Add(currentKey, value);
    NextKey = MyDictionary.Keys.Max() + 1;
    return currentKey;
}

public void RemoveFromMyDictionary(int key)
{
     MyDictionary.Remove(key);
     NextKey = key;
}

- sr28

---

这个程序的复杂度为O(n)，因此可能需要采用更专业的方法来优化。 - Lee

问题在于某些对象可能会被删除，因此我想在扩展更多内容之前使用那些未使用的值。因为这些数据将通过互联网发送。 - None

这与使用数组或 List<T> 并通过索引访问项有何不同？ - Richard Ev

如果从List<T>的开头/中间移除对象，则索引会发生变化。 - None

更准确地说，如果从集合中删除具有最大键的条目，则MyDictionary.Keys.Max() + 1表达式将生成曾经用于其他内容的键。 - Jeppe Stig Nielsen

Answer 4

这就是 int Object.GetHashCode() 的作用。

- Rik

---

就像@Stefan所说的那样 - None

Answer 5

根据您在编辑中提供的额外信息，我认为int不是适合您的正确数据类型，您不应该像您描述的那样重复使用ID，因为如果一个带有ID的客户端断开连接但没有意识到，则可能会有2个客户端使用1个ID。将数据类型更改为Guid，然后当您获得新客户端时，给它一个Guid.NewGuid()的键，重复键的机会尽可能接近0。

- MikeT

Answer 6

如果您只是需要一个“唯一的整数键”，而不需要额外的开销，那么使用 List 是否足够呢？在 List 的术语中，这就是所谓的“索引”。

如果您真的想要一个自定义函数，可以在一步中添加值和获取键，则可以从 List<T> 继承，像这样:

class MyCustomList<T> : List<T>
{
    //Not thread-safe
    public int AddAndGetKey(T valueToAdd)
    {
        Add(valueToAdd);
        return LastIndexOf(valueToAdd);
    }
}

我使用 LastIndexOf()，因为列表可能包含重复值，并且添加到列表始终添加到末尾。所以这应该有效，除非你遇到多线程的情况，其中你必须在一个原子操作中添加并获取索引。（或者也许你可以向 List<T> 添加扩展方法。）

使用 List 的优点是键中不会有空缺。另一方面，在中间移除一个项目将更改其后每个项目的键。但我想这取决于你要寻找什么样的行为。

- Arin

---

我本来想建议同样的事情，但是我突然意识到一个键不会在位置上改变，但是哈希集合可以做到这一点。 - MikeT

如果从列表中间移除一个对象，那么该值后面的所有对象的索引都会减少1。然而，我需要保持键值不变。 - None

Answer 7

我喜欢Stefan Steinegger的解决方案。这里有一个替代方案，它在后台使用List<>，但确保List<>永远不会被删除：

class AutoKeyDictionary<TValue> : IEnumerable<TValue> where TValue : class
{
  readonly List<TValue> list = new List<TValue>();

  public int Add(TValue val)
  {
    if (val == null)
      throw new ArgumentNullException(nameof(val), "This collection will not allow null values.");
    list.Add(val);
    return list.Count - 1;
  }

  public void RemoveAt(int key)
  {
    // do not remove ('list.Count' must never decrease), overwrite with null
    // (consider throwing if key was already removed)
    list[key] = null;
  }

  public TValue this[int key]
  {
    get
    {
      var val = list[key];
      if (val == null)
        throw new ArgumentOutOfRangeException(nameof(key), "The value with that key is no longer in this collection.");
      return val;
    }
  }

  public int NextKey => list.Count;

  public int Count => list.Count(v => v != null); // expensive O(n), Linq

  public bool ContainsKey(int key) => key >= 0 && key < list.Count && list[key] != null;

  public TValue TryGetValue(int key) => (key >= 0 && key < list.Count) ? list[key] : null;

  public void Clear()
  {
    for (var i = 0; i < list.Count; ++i)
      list[i] = null;
  }

  public IEnumerator<TValue> GetEnumerator() => list.Where(v => v != null).GetEnumerator(); // Linq

  IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

  public int FirstKeyOf(TValue val) => list.IndexOf(val);

  public IDictionary<int, TValue> ToDictionary()
  {
    var retColl = new SortedList<int, TValue>(list.Count);
    for (var i = 0; i < list.Count; ++i)
    {
      var val = list[i];
      if (val != null)
        retColl.Add(i, val);
    }
    return retColl;
  }

  // and so on...
}

显然不是线程安全的。

请注意，相同的值可以在集合中出现多次，但具有不同的键。

- Jeppe Stig Nielsen